Chu-Vandermonde Identity — Definition, Formula & Examples

The Chu-Vandermonde Identity states that a sum of products of two binomial coefficients equals a single binomial coefficient. It provides a way to break apart or combine choosing problems that draw from two separate groups.

For non-negative integers $m$ , $n$ , and $r$ with $r \leq m + n$ , the identity asserts $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ . Each term in the sum counts ways to choose $k$ items from one set of size $m$ and $r - k$ items from another of size $n$ , and the right side counts ways to choose $r$ items from the combined set.

Key Formula

\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}

Where:

$m$ = Size of the first group
$n$ = Size of the second group
$r$ = Total number of items chosen from both groups
$k$ = Number of items chosen from the first group (summation index)

How It Works

Think of a group of

m + n

objects split into two piles: one of size

m

and one of size

n

. To choose

r

objects total, you could take

k

from the first pile and

r - k

from the second. Summing over every valid value of

k

accounts for all possible splits, which must equal

\binom{m+n}{r}

. This combinatorial argument is often called a "committee-selection" proof. The identity is especially useful for simplifying sums involving products of binomial coefficients that appear in probability and generating-function calculations.

Worked Example

Problem: Verify the Chu-Vandermonde Identity for m = 3, n = 2, and r = 3.

Write out the sum: Expand the left side for k = 0, 1, 2, 3. Note that binomial coefficients with invalid arguments (choosing more than available) are zero.

\sum_{k=0}^{3} \binom{3}{k}\binom{2}{3-k}

Evaluate each term: k = 0: C(3,0)·C(2,3) = 1·0 = 0. k = 1: C(3,1)·C(2,2) = 3·1 = 3. k = 2: C(3,2)·C(2,1) = 3·2 = 6. k = 3: C(3,3)·C(2,0) = 1·1 = 1.

0 + 3 + 6 + 1 = 10

Compute the right side: Evaluate the single binomial coefficient on the right.

\binom{3+2}{3} = \binom{5}{3} = 10

Answer: Both sides equal 10, confirming the identity for m = 3, n = 2, r = 3.

Why It Matters

The Chu-Vandermonde Identity appears frequently in discrete mathematics and probability courses, particularly when working with hypergeometric distributions and convolutions of sequences. It also serves as a foundation for more advanced identities such as the Vandermonde–Chu generalization to real or complex upper parameters.

Common Mistakes

Mistake: Forgetting that binomial coefficients like C(n, k) equal zero when k > n or k < 0, and including incorrect nonzero terms in the sum.

Correction: Always treat C(n, k) as 0 whenever k < 0 or k > n. This naturally limits which terms in the summation are nonzero.