Vandermonde's Identity

Combinatorics · Axiom Academy

A beautiful combinatorial identity with elegant proofs and powerful applications Vandermonde's Identity states that for non-negative integers m, n, and r: This remarkable formula says that we can express a single binomial coefficient as a sum of products of binomial coefficients. The sum runs from k = 0 to k = r, where we interpret C(m,k) = 0 if k > m. 2. Combinatorial Proof: The Committee Interpretation Imagine we have m men and n women, and we want to form a committee of r people. We can count this in two ways: Method 1 (Right side): Choose r people from all m + n people: C(m+n, r) Method 2 (Left side): For each k from 0 to r, choose k men and r-k women: Σ C(m,k)C(n,r-k) 3. Special Case: When m = n = r A particularly beautiful special case occurs when we set m = n = r: This tells us that the sum of the squares of the binomial coefficients in row n equals the central binomial coefficient in row 2n! For example, when n = 3: 4. Applications and Why It's Useful Simplifying Sums: Vandermonde's Identity lets us convert complex sums of products into simpler single binomial coefficients. Probability Theory: In the hypergeometric distribution, this identity helps compute probabilities when sampling without replacement. Generating Functions: The identity corresponds to the coefficient of x^r in (1+x)^m × (1+x)^n = (1+x)^(m+n)

This is the written version of the interactive lesson above. See the full Combinatorics course.