Chu-Vandermonde Identity

From ProofWiki
Jump to: navigation, search

Theorem

Let $r, s \in \R, n \in \Z$.

Then:

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

where $\displaystyle \binom r k$ is a binomial coefficient.


Proof 1

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \sum_n \binom {r + s} n x^n\) \(=\) \(\displaystyle \) \(\displaystyle \left({1 + x}\right)^{r + s}\) \(\displaystyle \) \(\displaystyle \)          Binomial Theorem          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({1 + x}\right)^r \left({1 + x}\right)^s\) \(\displaystyle \) \(\displaystyle \)          Exponent Combination Laws          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \sum_k \binom r k x^k \sum_m \binom s m x^m\) \(\displaystyle \) \(\displaystyle \)          Binomial Theorem          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \sum_k \binom r k x^k \sum_{n-k} \binom s {n - k} x^{n - k}\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \sum_n \left({\sum_k \binom r k \binom s {n-k} }\right) x^n\) \(\displaystyle \) \(\displaystyle \)                    

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$


Proof 2

Special case of Gauss's Hypergeometric Theorem:

${}_2F_1 \left({a, b; c; 1}\right) = \dfrac{\Gamma \left({c}\right) \Gamma \left({c - a - b}\right)} {\Gamma \left({c - a}\right) \Gamma \left({c - b}\right)}$

where:

${}_2F_1$ is the Hypergeometric Series
$\Gamma \left({n + 1}\right) = n!$ is the Gamma function.


One regains the Chu-Vandermonde Identity by taking $a = -n$ and applying Negated Upper Index of Binomial Coefficient:

$\displaystyle \binom n k = (-1)^k \binom {k-n-1} k$

throughout.

$\blacksquare$


Also known as

When $r$ and $s$ are integers, it is more commonly known as Vandermonde's Identity or Vandermonde's Convolution.


Notes

This can be interpreted as follows.

The RHS can be thought of as the number of ways to select $n$ people from among $r$ men and $s$ women.

Each term in the LHS is the number of ways to choose $k$ of the men and $n - k$ of the women.


Source of Name

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

It appeared in Chu Shih-Chieh's The Precious Mirror of the Four Elements in 1303.

It was published by Vandermonde in 1772.


Sources