1
$\begingroup$

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.

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

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

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.