TAOCP 1.2.6 Exercise 15

Exercise 15. [M15] Prove the binomial formula, Eq. (13).

Verified: yes
Solve time: 42s

Solution

We prove Eq. (13) by induction on $r$.

When $r=0$, the right-hand side contains only the term with $k=0$, since $\binom{0}{k}=0$ for $k\ne0$. Therefore

$$ \sum_k \binom{0}{k}x^ky^{-k} = \binom{0}{0} = 1 = (x+y)^0. $$

Hence Eq. (13) is true for $r=0$.

Assume that

$$ (x+y)^r=\sum_k\binom{r}{k}x^ky^{r-k}, \qquad r\ge0. $$

Then

$$ (x+y)^{r+1} =(x+y)\sum_k\binom{r}{k}x^ky^{r-k}. $$

Distributing the factor $(x+y)$ gives

$$ (x+y)^{r+1} =\sum_k\binom{r}{k}x^{k+1}y^{r-k} +\sum_k\binom{r}{k}x^ky^{r+1-k}. $$

In the first sum, replace $k$ by $k-1$. This yields

$$ \sum_k\binom{r}{k-1}x^ky^{r+1-k}. $$

Hence

$$ (x+y)^{r+1} =\sum_k\left(\binom{r}{k-1}+\binom{r}{k}\right)x^ky^{r+1-k}. $$

By the addition formula (9),

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

Therefore

$$ (x+y)^{r+1} =\sum_k\binom{r+1}{k}x^ky^{r+1-k}. $$

This is Eq. (13) with $r$ replaced by $r+1$. The induction is complete.

This completes the proof.

∎