Chu-Vandermonde Identity/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof

\(\displaystyle \sum_n \binom {r + s} n x^n\) \(=\) \(\displaystyle \paren {1 + x}^{r + s}\) Binomial Theorem
\(\displaystyle \) \(=\) \(\displaystyle \paren {1 + x}^r \paren {1 + x}^s\) Exponent Combination Laws
\(\displaystyle \) \(=\) \(\displaystyle \sum_k \binom r k x^k \sum_m \binom s m x^m\) Binomial Theorem
\(\displaystyle \) \(=\) \(\displaystyle \sum_k \binom r k x^k \sum_{n - k} \binom s {n - k} x^{n - k}\)
\(\displaystyle \) \(=\) \(\displaystyle \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.


Sources