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

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?

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.$$

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\}$$.