Chu-Vandermonde Identity

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.

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

Proof

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

Alternative Proof

Special case of Gauss's Hypergeometric Theorem:

$\displaystyle {}_2F_1(a,b;c;1) = \frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)}$

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

One regains the Chu-Vandermonde identity by taking $a = -n$ and applying the identity

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

liberally.

Comment

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

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968) $\S 1.2.6 \ \text{I} \ (21)$, Exercise $17$
• Murray R. Spiegel: Mathematical Handbook of Formulas and Tables (1968): $3.13$