How Do We Find the Convolution of Two Sequences?

Convolutions can be a little confusing at first, so let’s work through a concrete example.

Consider the two sequences

$$p_0=1,\quad p_1=3,\quad p_2=5,\quad p_3=7,\dots$$

and

$$q_0=2,\quad q_1=4,\quad q_2=8,\quad q_3=16,\dots$$

The first contains the odd numbers, while the second contains powers of $2$.

More generally,

$$p_n=2n+1$$

and

$$q_n=2^{n+1}.$$

First: What the Convolution is NOT

It is tempting to multiply matching terms:

$$p_0q_0=2,\quad p_1q_1=12,\quad p_2q_2=40,\quad p_3q_3=112.$$

But this is not the convolution!

It is just the term-by-term, or pointwise, product of the two sequences.

The Convolution

Let the convolution have terms

$$r_0,\quad r_1,\quad r_2,\quad r_3,\dots$$

The general rule is

$$r_n=p_0q_n+p_1q_{n-1}+p_2q_{n-2}+\dots+p_nq_0.$$

So $r_n$ contains all products whose indices add up to $n$.

For example, let’s find $r_2$. The pairs of indices which add up to $2$ are

$$0+2,\quad 1+1,\quad 2+0.$$

So,

$$r_2=p_0q_2+p_1q_1+p_2q_0$$

and hence

$$r_2=1\times8+3\times4+5\times2=30.$$

The first few terms are:

Notice that, to find $r_n$, we need to use all the terms up to index $n$, but no later ones.

We can write the same rule more compactly as

$$r_n=\sum_{k=0}^n p_kq_{n-k}.$$

The important thing to remember is that we do not simply multiply terms with the same index (though these may be involved).

Rather, to find $r_n$, we multiply terms whose indices add up to $n$, then add all those products together.

Background:

• Summing Two Random Variables – Convolutions