TAOCP 1.2.3 Exercise 13

Exercise 13. [10] Using Eq. (15) and assuming that $m \le n$, evaluate $\sum_{j=m}^n j$.

Verified: yes
Solve time: 37s

We begin by expressing the sum in a form suitable for applying Eq. (15):

$\sum_{j=m}^n j = \sum_{0 \le j \le n} j - \sum_{0 \le j \le m-1} j. \eqno(1)$

By Eq. (15), we have

$\sum_{0 \le j \le n} j = 0 \cdot (n+1) + \tfrac{1}{2} \cdot 1 \cdot n(n+1) = \tfrac{1}{2} n(n+1),$

and

$\sum_{0 \le j \le m-1} j = 0 \cdot m + \tfrac{1}{2} \cdot 1 \cdot (m-1)m = \tfrac{1}{2} m(m-1).$

Substituting these into (1) gives

$\sum_{j=m}^n j = \frac{1}{2} n(n+1) - \frac{1}{2} m(m-1) = \frac{n(n+1) - m(m-1)}{2}.$

Expanding the numerator, we obtain

$n(n+1) - m(m-1) = n^2 + n - m^2 + m = (n^2 - m^2) + (n + m) = (n-m)(n+m) + (n+m) = (n-m+1)(n+m).$

Hence

$\sum_{j=m}^n j = \frac{(n-m+1)(n+m)}{2}.$

The final result is

$\boxed{\sum_{j=m}^n j = \frac{(n-m+1)(n+m)}{2}}.$

This completes the proof.

∎