# 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.

## 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

- Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(1968) $\S 1.2.6 \ \text{I} \ (21)$ - Murray R. Spiegel:
*Mathematical Handbook of Formulas and Tables*(1968)... (previous)... (next): $\S 3$: The Binomial Formula and Binomial Coefficients: $3.13$