TAOCP 1.2.6 Exercise 17

Exercise 17. [M18] Prove the Chu--Vandermonde formula (21) from Eq. (15), using the idea that $(1+x)^{r+s} = (1+x)^r(1+x)^s$.

Verified: yes
Solve time: 1m08s

Solution

Equation (15) is the generalized binomial theorem,

$$ (1+x)^r=\sum_{j\ge0}\binom{r}{j}x^j. \tag{15} $$

We compute $(1+x)^{r+s}$ in two ways. First, by Eq. (15),

$$ (1+x)^{r+s} =\sum_{n\ge0}\binom{r+s}{n}x^n. \tag{1} $$

Second,

$$ (1+x)^{r+s} =(1+x)^r(1+x)^s. $$

Applying Eq. (15) to each factor gives

$$ (1+x)^r(1+x)^s = \left(\sum_{j\ge0}\binom{r}{j}x^j\right) \left(\sum_{k\ge0}\binom{s}{k}x^k\right). $$

Multiplying the series, the coefficient of $x^n$ is

$$ \sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}. $$

Hence

$$ (1+x)^{r+s} = \sum_{n\ge0} \left( \sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k} \right)x^n. \tag{2} $$

The power series in (1) and (2) are equal; therefore the coefficients of $x^n$ are equal for every integer $n\ge0$. Thus

$$ \boxed{ \sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n} }. \tag{21} $$

This is the Chu-Vandermonde formula.

This completes the proof.

∎