Chu-Vandermonde Identity/Proof 1

From ProofWiki
Jump to navigation Jump to search


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


\(\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}$


Source of Name

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