# Chu-Vandermonde Identity/Proof 1

## Theorem

$\displaystyle \sum_k \binom r k \binom s {n - k} = \binom {r + s} n$

## Proof

 $\ds \sum_n \binom {r + s} n x^n$ $=$ $\ds \paren {1 + x}^{r + s}$ Binomial Theorem $\ds$ $=$ $\ds \paren {1 + x}^r \paren {1 + x}^s$ Exponent Combination Laws $\ds$ $=$ $\ds \sum_k \binom r k x^k \sum_m \binom s m x^m$ Binomial Theorem $\ds$ $=$ $\ds \sum_k \binom r k x^k \sum_{n - k} \binom s {n - k} x^{n - k}$ $\ds$ $=$ $\ds \sum_n \paren {\sum_k \binom r k \binom s {n - k} } x^n$

As this has to be true for all $x$, we have that:

$\displaystyle \binom {r + s} n = \sum_k \binom r k \binom s {n - k}$

$\blacksquare$

## Source of Name

This entry was named for Alexandre-Théophile Vandermonde and Chu Shih-Chieh.