What is the convolution here?

Question

I'm reading Knuth/Graham/Patashnik's: Concrete Mathematics.

• In here, it's not clear to me what is the convolution, is it the act of writing as this?

• Is this convolution somehow related to this? I tried to read it but I couldn't go far.

Answer 1

There are several related notions of convolution in mathematics. This one is the convolution of two sequences. Suppose that

$$A=\langle a_n:n\in\Bbb N\rangle=\langle a_0,a_1,a_2,\ldots\rangle$$

and

$$B=\langle b_n:n\in\Bbb N\rangle=\langle b_0,b_1,b_2,\ldots\rangle$$

are two sequences of real or complex numbers. The convolution of $A$ and $B$ is a new sequence

$$C=\langle c_n:n\in\Bbb N\rangle=\langle c_0,c_1,c_2,\ldots\rangle$$

defined as follows:

$$c_n=\sum_{k=0}^na_kb_{n-k}\;.$$

Thus,

$$C=\langle a_0b_0,a_0b_1+a_1b_0,a_0b_2+a_1b_1+a_2b_0,\ldots\rangle\;.$$

If we use $*$ to represent the operation of convolution, we have $C=A\mathop{*}B$.

Each of these sequences has an associated power series:

$$\begin{align*} g_A(x)&=\sum_{n\ge 0}a_nx^n\tag{1}\\ g_B(x)&=\sum_{n\ge 0}b_nx^n\tag{2}\\ \end{align*}$$

The point of that passage in Concrete Mathematics is that if you multiply the summations $(1)$ and $(2)$ as if they were ordinary polynomials, you get the power series associated with $A\mathop{*}B$:

$$\begin{align*} \left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)&=(a_0+a_1x+a_2x^2+\ldots)(b_0+b_1x+b_2x^2+\ldots)\\\\ &=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\ldots\\\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n\;. \end{align*}$$

The most relevant Wikipedia link is probably this one, for the Cauchy product of series.

Answer 2

Given two sequences $(a_n)$ and $(b_n)$, we can form their convolution which is a new sequence $(c_n)$ given by $$c_n = \sum_{k=0}^na_kb_{n-k}.$$ This definition is such that the following formal manipulation of power series holds:

$$\left(\sum_{n=0}^{\infty}a_nz^n\right)\left(\sum_{n=0}^{\infty}b_nz^n\right) = \sum_{n=0}^{\infty}c_nz^n.$$

The main concern in the linked article is the convolution of functions. The convolution that you're considering here is often referred to as discrete convolution as the very same article mentions.