TAOCP 1.2.6 Exercise 13

Section 1.2.6: Binomial Coefficients

Exercise 13. [M13] Prove the summation formula, Eq. (10).

Verified: yes
Solve time: 38s

Solution

Equation (10) states that

$$ \sum_{k=0}^{n}\binom{r+k}{k} = \binom{r+n+1}{n}, \qquad \text{integer } n\ge 0. $$

We prove this formula by induction on $n$.

When $n=0$, the left-hand side is

$$ \sum_{k=0}^{0}\binom{r+k}{k} = \binom{r}{0} = 1 $$

by equation (4). The right-hand side is

$$ \binom{r+0+1}{0} = \binom{r+1}{0} = 1. $$

Hence the formula holds for $n=0$.

Assume that for some integer $n\ge 0$,

$$ \sum_{k=0}^{n}\binom{r+k}{k} = \binom{r+n+1}{n}. \tag{*} $$

Then

$$ \sum_{k=0}^{n+1}\binom{r+k}{k} = \sum_{k=0}^{n}\binom{r+k}{k} + \binom{r+n+1}{n+1}. $$

Applying the induction hypothesis $(*)$ gives

$$ \sum_{k=0}^{n+1}\binom{r+k}{k} = \binom{r+n+1}{n} + \binom{r+n+1}{n+1}. $$

By the addition formula (9),

$$ \binom{r+n+2}{n+1} = \binom{r+n+1}{n+1} + \binom{r+n+1}{n}. $$

Therefore

$$ \sum_{k=0}^{n+1}\binom{r+k}{k} = \binom{r+n+2}{n+1}. $$

This is equation (10) with $n+1$ in place of $n$. Hence the formula holds for all integers $n\ge 0$.

This completes the proof.

∎