combinatorics - Show that $sumlimits_{p = 0}^ksumlimits_{r = 0}^{k-p} a_{k-p-r}b_rc_p = sumlimits_{r = 0}^ka_{k-r}sumlimits_{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.

Answer

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.