Summation Manipulation Problem

Question

Is the following statement true: $$\sum^k_{j=0} \left(\sum^j_{i=0}a_i b_{j-i}\right) d_{k-j} = \sum^k_{j=0} \left(\sum^j_{i=0}b_i d_{j-i}\right) a_{k-j}$$

I'm not sure if this is true as I've been unable to prove this directly. However, I think this is true.

If we fix $k$ and then $j$, we have fixed the subscript of $d$. So, there is a term $a_m b_n d_o$ on the LHS such that $m + n + o = k$.

However on the RHS, if we fix the same value of $k$ as above and strategically fix a different value of $j$ so that the subscript of $a$ is $m$, then we can find a particular $i$ such that we also have $a_m b_n d_o$. That is, the subscript of $b$ plus the subscript of $d$ on the RHS is equal to $j$, so we can find an $n$ and $o$ such that $n+o = k - m = j$.

If it is true, is there a more direct (or different) proof of this? If not, why is it not true?

Answer 1

We obtain \begin{align*} \color{blue}{\sum^k_{j=0} \left(\sum^j_{i=0}a_i b_{j-i}\right) d_{k-j}} &=\sum_{0\leq i\leq j \leq k}a_i b_{j-i} d_{k-j}\tag{1}\\ &=\sum_{i=0}^k\sum_{j=i}^ka_i b_{j-i} d_{k-j}\tag{2}\\ &=\sum_{i=0}^k\sum_{j=0}^{k-i}a_i b_{j} d_{k-j-i}\tag{3}\\ &=\sum_{j=0}^k\sum_{i=0}^{k-j}a_j b_{i} d_{k-i-j}\tag{4}\\ &\,\,\color{blue}{=\sum_{j=0}^k\left(\sum_{i=0}^{j} b_{i} d_{j-i}\right)a_{k-j}}\tag{5}\\ \end{align*} and the claim follows.

Comment:

• In (1) we write the index region somewhat more conveniently as preparation for the next step.

• In (2) we exchange the order of summation by exchanging the sums.

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

• In (4) we exchange the notation $i\to j$ and $j\to i$.

• In (5) we exchange the order of summation of the outer sum $j\to k-j$ and factor out $a_{k-j}$ from the inner sum.

Answer 2

Both sides equalize: $$\sum_{m+n+o=k}a_mb_nd_o$$ where $m,n,o$ denote nonnegative integers.

The expression: $$\sum_{m+n+o=k}a_mb_nd_o$$ abbreviates: $$\sum_{\langle m,n,o\rangle\in S}a_mb_nd_o$$ where $S=\{\langle m,n,o\rangle\in\mathbb N\mid m+n+o=k\}$ and $\mathbb N=\{0,1,2,\dots\}$.

Further $|S|=\binom{k+2}2$ (which can be found with stars and bars).

Answer 3

Hint:

With $k=2$,

$$(a_0b_0)d_2+(a_0b_1+a_1b_0)d_1+(a_0b_2+a_1b_1+a_2b_0)d_0$$

vs.

$$(d_0b_0)a_2+(d_0b_1+d_1b_0)a_1+(d_0b_2+d_1b_1+d_2b_0)a_0.$$

All terms are matching. There are indeed $k(k+1)/2$ of them (triangular number), such that the sum of indices is $k$.