TAOCP 1.2.7 Exercise 10

Exercise 10. [M20] (Summation by parts.) Prove the general formula

$$ \sum_{1 \le k < n}(a_{k+1}-a_k)b_k = a_nb_n - a_1b_1 - \sum_{1 \le k < n}a_{k+1}(b_{k+1}-b_k). $$

Verified: no
Solve time: -

Solution

Let

$$ S=\sum_{1 \le k < n}(a_{k+1}-a_k)b_k. $$

Expand the sum:

$$ S = (a_2-a_1)b_1+(a_3-a_2)b_2+\cdots+(a_n-a_{n-1})b_{n-1}. $$

Distribute each factor:

$$ S = a_2b_1-a_1b_1+a_3b_2-a_2b_2+\cdots+a_nb_{n-1}-a_{n-1}b_{n-1}. $$

Group terms according to the coefficients of the $a_k$'s:

$$ S = a_nb_{n-1}-a_1b_1 +\sum_{k=2}^{n-1}a_k(b_{k-1}-b_k). $$

Reindex the sum by replacing $k$ with $k+1$:

$$ S = a_nb_{n-1}-a_1b_1 +\sum_{1 \le k < n-1}a_{k+1}(b_k-b_{k+1}). $$

Since $b_k-b_{k+1}=-(b_{k+1}-b_k)$,

$$ S = a_nb_{n-1}-a_1b_1 -\sum_{1 \le k < n-1}a_{k+1}(b_{k+1}-b_k). $$

Now add and subtract $a_nb_n$:

$$ a_nb_{n-1} = a_nb_n-a_n(b_n-b_{n-1}). $$

Substituting this into the previous equation gives

$$ S = a_nb_n-a_1b_1 -\sum_{1 \le k < n-1}a_{k+1}(b_{k+1}-b_k) -a_n(b_n-b_{n-1}). $$

Combine the final term with the summation:

$$ S = a_nb_n-a_1b_1 -\sum_{1 \le k < n}a_{k+1}(b_{k+1}-b_k). $$

Therefore

$$ \sum_{1 \le k < n}(a_{k+1}-a_k)b_k = a_nb_n-a_1b_1 -\sum_{1 \le k < n}a_{k+1}(b_{k+1}-b_k). $$

This completes the proof.

∎