TAOCP 1.2.6 Exercise 19

Exercise 19. [M18] Prove Eq. (23) by induction.

Verified: yes
Solve time: 38s

Solution

Equation (23) is

$$ \sum_k (-1)^{r-k}\binom{r}{k}\binom{s+k}{n} = \binom{s}{n-r}, \qquad \text{integer } r \ge 0. \tag{23} $$

We prove this identity by induction on $r$.

For the basis, let $r=0$. Since $\binom{0}{k}=0$ for $k\ne 0$ and $\binom{0}{0}=1$, the sum reduces to a single term:

$$ \sum_k (-1)^{-k}\binom{0}{k}\binom{s+k}{n} = \binom{0}{0}\binom{s}{n} = \binom{s}{n}. $$

On the other hand,

$$ \binom{s}{n-0} = \binom{s}{n}. $$

Hence Eq. (23) holds when $r=0$.

Assume now that Eq. (23) holds for some integer $r\ge0$; we prove it for $r+1$. Consider

$$ \sum_k (-1)^{r+1-k}\binom{r+1}{k}\binom{s+k}{n}. $$

By the addition formula (9),

$$ \binom{r+1}{k} = \binom{r}{k} + \binom{r}{k-1}. $$

Substituting this into the sum gives

$$ \sum_k (-1)^{r+1-k} \left( \binom{r}{k} + \binom{r}{k-1} \right) \binom{s+k}{n}. $$

Splitting into two sums,

$$= \sum_k (-1)^{r+1-k}\binom{r}{k}\binom{s+k}{n} + \sum_k (-1)^{r+1-k}\binom{r}{k-1}\binom{s+k}{n}.$$

In the second sum, replace $k$ by $k+1$:

$$= - \sum_k (-1)^{r-k}\binom{r}{k}\binom{s+k}{n} + \sum_k (-1)^{r-k}\binom{r}{k}\binom{s+k+1}{n}.$$

Combining the sums,

$$= \sum_k (-1)^{r-k}\binom{r}{k} \left( \binom{s+k+1}{n} - \binom{s+k}{n} \right).$$

By Eq. (9),

$$ \binom{s+k+1}{n} = \binom{s+k}{n} + \binom{s+k}{n-1}, $$

hence

$$ \binom{s+k+1}{n} - \binom{s+k}{n} = \binom{s+k}{n-1}. $$

Therefore

$$ \sum_k (-1)^{r+1-k}\binom{r+1}{k}\binom{s+k}{n} = \sum_k (-1)^{r-k}\binom{r}{k}\binom{s+k}{n-1}. $$

The induction hypothesis applies with $n-1$ in place of $n$, so

$$= \binom{s}{(n-1)-r} = \binom{s}{n-r-1}.$$

Since

$$ n-r-1=n-(r+1), $$

this becomes

$$ \sum_k (-1)^{r+1-k}\binom{r+1}{k}\binom{s+k}{n} = \binom{s}{n-(r+1)}. $$

Thus Eq. (23) holds for $r+1$, completing the induction.

This completes the proof.

∎