Chu-Vandermonde Identity/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \sum_{k \mathop = 0}^n \binom r k \binom s {n - k} = \binom {r + s} n$


Proof

\(\ds \sum_{n \mathop = 0}^{r + s} \binom {r + s} n x^n\) \(=\) \(\ds \paren {1 + x}^{r + s}\) Binomial Theorem - Integral Index
\(\ds \) \(=\) \(\ds \paren {1 + x}^r \paren {1 + x}^s\) Exponent Combination Laws
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 0}^r \binom r k x^k \sum_{k \mathop = 0}^s \binom s k x^k\) Binomial Theorem - Integral Index
\(\ds \) \(=\) \(\ds \sum_{n \mathop = 0}^{r + s} \paren {\sum_{k \mathop = 0}^n \binom r k \binom s {n - k} } x^n\) Product of Absolutely Convergent Series

Therefore:

$\ds \binom {r + s} n = \sum_{k \mathop = 0}^n \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

Retrieved from "https://proofwiki.org/w/index.php?title=Chu-Vandermonde_Identity/Proof_1&oldid=603932"