Vandermonde's Identity (Convolution of Binomial Coefficients)

The identity

Whenever you meet a sum of products of two binomial coefficients in which the two lower indices always add up to the same fixed number $n$, the whole sum collapses to a single binomial. This is Vandermonde's identity:

$\sum_{k=0}^{n}\binom{m}{k}\binom{p}{\,n-k\,}=\binom{m+p}{n}.$

The pattern to recognize: in every term the top numbers $m,p$ are fixed, while the bottom numbers are $k$ and $n-k$ — they slide but always sum to $n$. Such a sum is a convolution of the two binomial rows, and the answer is just the binomial of the summed tops choose the common bottom.

Why it holds (combinatorial proof)

To choose $n$ objects from a combined set of $m+p$ items, first split the items into a group of $m$ and a group of $p$. Any selection takes some number $k$ from the first group and the remaining $n-k$ from the second; there are $\binom{m}{k}\binom{p}{n-k}$ ways to do that for a fixed $k$. Summing over all admissible $k$ counts every $n$-subset exactly once, so the total equals $\binom{m+p}{n}$. (Terms with $k>m$ or $n-k>p$ are automatically $0$, so the range $0\le k\le n$ is safe.)

How to apply (recipe)

1. Spot the shape. Confirm the summand is $\binom{m}{k}\binom{p}{n-k}$ with $m,p,n$ constant and the lower indices summing to $n$.
2. Read off $m+p$ and $n$. The two top numbers add; the common bottom $n$ stays.
3. Replace the sum by $\binom{m+p}{n}$.
4. Evaluate that single binomial.

Useful special case (the central identity)

Set $m=p=n$ and use $\binom{n}{n-k}=\binom{n}{k}$:

$\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}.$

Worked mini-example

Evaluate $\displaystyle\sum_{k=0}^{4}\binom{5}{k}\binom{3}{\,4-k\,}$.

Here the tops are $m=5$ and $p=3$, and the common bottom is $n=4$. By the identity,

$\sum_{k=0}^{4}\binom{5}{k}\binom{3}{4-k}=\binom{5+3}{4}=\binom{8}{4}=70.$

No term-by-term grind needed — recognizing the convolution turns a four-term sum into one lookup.

Exam trick: The lower indices must sum to a constant. If a term reads $\binom{m}{k}\binom{p}{n-k}$, you are done — add the tops, keep the bottom. Watch for the disguised central case $\sum_k\binom{n}{k}^2=\binom{2n}{n}$ (one factor is rewritten via $\binom{n}{k}=\binom{n}{n-k}$), and remember out-of-range binomials are $0$, so a stated range like $k=0..n$ never overcounts.