How to prove that convolution of sequences is associative?

Question

Let {$a_n$} and {$b_n$} be finite real sequences with $n\ge0$. Convolution ($\ast$) of two sequences defined as $$ \{a_n\}\ast\{b_n\}=\{\sum_{i=0}^{n} a_ib_{n-i}\}. $$ The convolution of three sequences is: $$ (\{a_n\}\ast\{b_n\})\ast\{c_n\}=(\{\sum_{i=0}^{n} a_ib_{n-i}\})\ast\{c_n\}=\{\sum_{j=0}^{n}\sum_{i=0}^{j} a_ib_{j-i}c_{n-j}\} $$ $$ \{a_n\}\ast(\{b_n\}\ast\{c_n\})=\{a_n\}\ast(\{\sum_{k=0}^{n} b_kc_{n-k}\})=\{\sum_{l=0}^{n}\sum_{k=0}^{n-l} a_lb_kc_{n-l-k}\}. $$ I'm not sure how to show both of the double sum is same. can anyone give me advice?

Answer 1

We start with the second double sum and do some transformations to obtain the first double sum.

We obtain \begin{align*} \color{blue}{\sum_{l=0}^n\sum_{k=0}^{n-l}a_lb_kc_{n-l-k}} &=\sum_{l=0}^n\sum_{k=0}^la_{n-l}b_{k}c_{l-k}\tag{1.1}\\ &=\sum_{l=0}^n\sum_{k=0}^la_{n-l}b_{l-k}c_k\tag{1.2}\\ &=\sum_{k=0}^n\sum_{l=k}^na_{n-l}b_{l-k}c_k\tag{1.3}\\ &=\sum_{k=0}^n\sum_{l=0}^{n-k} a_{n-l-k}b_lc_k\tag{1.4}\\ &=\sum_{k=0}^n\sum_{l=0}^k a_{k-l}b_lc_{n-k}\tag{1.5}\\ &\,\,\color{blue}{=\sum_{k=0}^n\sum_{l=0}^ka_lb_{k-l}c_{n-k}}\tag{1.6} \end{align*} and the claim follows.

Comment:

• In (1.1) we change the order of summation of the outer sum $l\to n-l$.

• In (1.2) we change the order of summation of the inner sum $k\to l-k$.

• In (1.3) we exchange inner and outer sum according to $\sum_{0\leq k\leq l\leq n}a_{n-l}b_{l-k}c_k$.

• In (1.4) we shift the index of the inner sum to start with $l=0$.

• In (1.5) we change the order of summation of the outer sum $k\to n-k$.

• In (1.6) we change the order of summation of the inner sum $l\to k-l$.