Chu-Vandermonde Identity

From ProofWiki
Jump to navigation Jump to 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 $\dbinom r k$ is a binomial coefficient.


Extended Chu-Vandermonde Identity

Let $r, s, \alpha, \beta \in \C$ be complex numbers.


Then:

$\displaystyle \sum_{k \mathop \in \Z} \dbinom r {\alpha + k} \dbinom s {\beta - k}$

where $\dbinom r {\alpha + k}$ denotes a binomial coefficient.


Proof 1

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


Proof 2

This is a 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:

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

throughout.

$\blacksquare$


Proof 3 (Informal)

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

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

$\blacksquare$


Proof 4

From Sum over $k$ of $\dbinom {r - t k} k \dbinom {s - t \left({n - k}\right)} {n - k} \dfrac r {r - t k}$:


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

Then:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \left({n - k}\right)} {n - k} \frac r {r - t k} = \binom {r + s - t n} n$


where $r, s, t \in \R, n \in \Z$.


Setting $t = 0$:

$\displaystyle \sum_{k \mathop \ge 0} \binom r k \binom s {n - k} = \binom {r + s} n$

which is the result required.

$\blacksquare$


Also known as

When $r$ and $s$ are integers, it is more commonly known as Vandermonde's identity, Vandermonde's convolution.

Sometimes it is seen referred to as the Chu-Vandermonde formula, or Vandermonde's theorem.


Source of Name

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


Historical Note

The Chu-Vandermonde Identity first appeared in Chu Shih-Chieh's The Precious Mirror of the Four Elements in $1303$.

It was rediscovered by Alexandre-Théophile Vandermonde and published in $1772$.


Sources