Find the formula for the convolution of the sequences (generating functions)

Question

Find the formula for the convolution of the sequences:

$a_n=\begin {cases} 1 & 0\leq n \leq 4 \\ 0 & n \geq 5 \end{cases} $

$b_n = 1$ $\forall n \in \mathbb{N}$

What I've been doing:

In other words:

$a_n = 1,1,1,1,1,0,0,...$ and $b_n=1,1,1,1,...$

So that means that their generating functions are:

$a(x)=1+x+x^2+x^3+x^4=\sum _{i=0} ^{4} x^i$

$b(x)=1+x+x^2+x^3+...=\sum _{j=0} ^{\infty} x^i$

So using the convolution formula i.e: $b(x)a(x)=\sum _{j=0} ^{\infty}(\sum _{i=0} ^{4}a_ib_{j-i})x^4=\sum _{j=0} ^{\infty}(\sum _{i=0} ^{4}x^i(x^{i-j}))x^4=\sum _{j=0} ^{\infty}(\sum _{i=0} ^{4}x^{2i-j})x^4$

And I can't get past that nor do I know if what I did was correct... Can someone guide me?

Answer 1

One approach is to simplify the generating functions $a(x)$ and $b(x)$, multiply them, and manipulate the resulting generating function for the convolution, as follows:

$$\begin{align} a(x) &= \sum_{i=0}^4 x^i = 1+x+x^2+x^3+x^4 \\ b(x) &= \sum_{j=0}^\infty x^j = \frac{1}{1-x} \\ \sum_{k=0}^\infty \left(\sum_{i=0}^k a_i b_{k-i}\right) x^k &= a(x) b(x) \\ &= \frac{1+x+x^2+x^3+x^4}{1-x} \\ &= -4 - 3 x- 2 x^2 -x^3 + \frac{5}{1 - x} \\ &= -4 - 3 x- 2 x^2 -x^3 + 5\sum_{k=0}^\infty x^k \\ &= 1 +2 x+3 x^2 +4x^3 + 5\sum_{k=4}^\infty x^k \\ &= \sum_{k=0}^\infty \min(k+1,5) x^k. \end{align}$$

So $$\sum_{i=0}^k a_i b_{k-i}= \min(k+1,5).$$

More generally, convolution of an arbitrary sequence $(a_i)_{i=0}^\infty$ with the constant 1 sequence yields the sequence of cumulative sums $(\sum_{i=0}^k a_i)_{k=0}^\infty$. You can use the same generating function approach as above or just compute directly: $$ \sum_{i=0}^k a_i b_{k-i} = \sum_{i=0}^k a_i \cdot 1 = \sum_{i=0}^k a_i. $$

Answer 2

The usage of the convolution formula is not correct. Recalling the general case we have \begin{align*} a(x)b(x)&=\left(\sum_{i=0}^\infty a_ix^i\right)\left(\sum_{j=0}^\infty b_jx^j\right)\\ &=\sum_{n=0}^\infty\left(\sum_{{i+j=n}\atop{i,j\geq 0}}a_ib_j\right)x^n\tag{1}\\ &=\sum_{n=0}^\infty\left(\sum_{i=0}^na_ib_{n-i}\right)x^n \end{align*}

Applying the convolution to the current problem, we obtain

\begin{align*} \color{blue}{a(x)b(x)}&=\left(\sum_{i=0}^4 x^i\right)\left(\sum_{j=0}^\infty x^j\right)\\ &=\sum_{n=0}^\infty\left(\sum_{{i+j=n}\atop{0\leq i\leq 4; j\geq 0}}1\right)x^n\tag{2}\\ &=\sum_{n=0}^\infty\left(\sum_{i=0}^{\min\{n,4\}}1\right)x^n\tag{3}\\ &\,\,\color{blue}{=\sum_{n=0}^\infty\min\{n+1,5\}x^n} \end{align*}

Comment:

• In (2) we do the same step as in (1). We respect the upper limit $4$ of the series representation of $a(x)$ by explicitly setting the index range of $i$ to $0\leq i\leq 4$.

• In (3) we consequently set the upper limit to $\min\{n,4\}$.