# Show that $\sum\limits_{p = 0}^k\sum\limits_{r = 0}^{k-p} a_{k-p-r}b_rc_p = \sum\limits_{r = 0}^ka_{k-r}\sum\limits_{s = 0}^rb_{r-s}c_s$

How does one prove that $$\sum\limits_{p = 0}^k\sum\limits_{r = 0}^{k-p} a_{(k-p)-r}b_rc_p = \sum\limits_{r = 0}^ka_{k-r}\sum\limits_{s = 0}^rb_{r-s}c_s$$ is true for any $k$?

This is the same as saying that $$\sum\limits_{p+q = k}\sum\limits_{r+s = p}a_rb_sc_q = \sum\limits_{r+w = k}\sum\limits_{s+q = w}a_rb_sc_q$$ but I want to give a formal proof, rather than an intuitive argument, perhaps one by induction.

• I think $c_q$ in LHS should be $c_p$. – GAVD Aug 29 '17 at 4:28
• Both sums are simply $$\sum_{r,s,t\geqslant0}a_rb_sc_t\,[r+s+t=k]$$ – Did Aug 29 '17 at 11:47

We start with the left-hand side and obtain \begin{align*} \color{blue}{\sum_{p=0}^k\sum_{r=0}^{k-p}a_{k-p-r}b_rc_p}&=\sum_{s=0}^k\sum_{r=0}^{k-s}a_{k-r-s}b_rc_s\tag{1}\\ &=\sum_{s=0}^k\sum_{r=s}^ka_{k-r}b_{r-s}c_s\tag{2}\\ &=\sum_{0\leq s\leq r\leq k}a_{k-r}b_{r-s}c_s\tag{3}\\ &\color{blue}{=\sum_{r=0}^k\sum_{s=0}^ra_{k-r}b_{r-s}c_s}\tag{4} \end{align*} and the claim follows.

Comment:

• In (1) we rename $p$ with $s$.

• In (2) we shift the index of the inner sum and start with $r=s$.

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

• In (4) we exchange the order of the summation.

For any $0 \leq m \leq k$, consider the coefficients of $a_m$. For LHS the coefficient is the sum of $b_{p-m}c_{k-p}$s (since $r+s=q=k-p$), which is $\sum_{m\leq p \leq k}b_{p-m}c_{k-p}=\sum_{x+y=k-m}b_xc_y$. For RHS the coefficient is the sum of $b_sc_q$s with $s+q=k-m$ (since $w=k-m$), which is $\sum_{s+q=k-m}b_sc_q=\sum_{x+y=k-m}b_xc_y$. Thus they are same. In other words, you can write both sums as following: $\sum_{0\leq m \leq k} \sum_{x+y=k-m} a_mb_xc_y$.