TAOCP 1.2.3 Exercise 19

Exercise 19. [20] What is $\sum_{j=m}^n (a_j - a_{j-1})$?

Verified: yes
Solve time: 2m02s

Solution

We compute the sum directly.

By linearity of summation,

$$ \sum_{j=m}^n (a_j-a_{j-1}) = \sum_{j=m}^n a_j - \sum_{j=m}^n a_{j-1}. $$

Using the change of index $k=j-1$ in the second sum, Eq. (6) gives

$$ \sum_{j=m}^n a_{j-1} = \sum_{k=m-1}^{,n-1} a_k. $$

Hence

$$ \sum_{j=m}^n (a_j-a_{j-1}) = \sum_{j=m}^n a_j - \sum_{k=m-1}^{,n-1} a_k. $$

Writing the sums out explicitly,

$$ \sum_{j=m}^n a_j = a_m+a_{m+1}+\cdots+a_{n-1}+a_n, $$

and

$$ \sum_{k=m-1}^{,n-1} a_k = a_{m-1}+a_m+a_{m+1}+\cdots+a_{n-1}. $$

Subtracting, all common terms cancel:

$$ (a_m+a_{m+1}+\cdots+a_{n-1}+a_n) - (a_{m-1}+a_m+a_{m+1}+\cdots+a_{n-1}) = a_n-a_{m-1}. $$

Therefore

$$ \boxed{\sum_{j=m}^n (a_j-a_{j-1}) = a_n-a_{m-1}}. $$

This is the telescoping-sum identity.