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*}


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.