Math Core

Sums of binomial coefficients show up all over the AIME, sometimes in plain sight and sometimes hidden inside a counting or probability problem. The strongest way to handle them is to prove identities by counting one set in two ways: if two expressions count the same thing, they're equal, and you never have to push algebra around.

Double counting

To prove $\text{LHS} = \text{RHS}$ , find a set of objects and a question about it so that one way of answering gives the left side and another way gives the right side.

For example, $\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ : both sides count the subsets of an $n$ -element set. The right side decides "in or out" for each element; the left side sorts subsets by their size $k$ .

The identities to know

Pascal: $\dbinom{n}{k} = \dbinom{n-1}{k} + \dbinom{n-1}{k-1}$ (is element $n$ chosen?).
Hockey stick: $\displaystyle\sum_{j=r}^{n} \binom{j}{r} = \binom{n + 1}{r + 1}$ (sort by the largest element chosen).
Vandermonde: $\displaystyle\sum_{k} \binom{m}{k}\binom{n}{r - k} = \binom{m + n}{r}$ (choose $r$ people from $m$ boys and $n$ girls).
Committee with a chair: $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ , so $\displaystyle\sum_k k\binom{n}{k} = n \cdot 2^{n-1}$ .
Subset of a subset: $\dbinom{n}{k}\dbinom{k}{m} = \dbinom{n}{m}\dbinom{n - m}{k - m}$ , so $\displaystyle\sum_k \binom{n}{k}\binom{k}{m} = \binom{n}{m}2^{n - m}$ .

Why the hockey stick works

Count the $(r + 1)$ -element subsets of $\{1, 2, \dots, n + 1\}$ . There are $\dbinom{n+1}{r+1}$ of them. Now sort them by their largest element. If the largest element is $j + 1$ , the other $r$ elements come from $\{1, \dots, j\}$ , in $\dbinom{j}{r}$ ways. Adding over $j = r, \dots, n$ gives the left side.

Why Vandermonde works

Count the ways to choose $r$ people from a group of $m$ boys and $n$ girls: $\dbinom{m + n}{r}$ . Sorting by the number of boys $k$ gives $\dbinom{m}{k}\dbinom{n}{r - k}$ for each $k$ . A common special case uses $\dbinom{n}{k} = \dbinom{n}{n - k}$ :

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

Common mistake

Vandermonde needs the lower indices to add to a constant. In $\sum_k \binom{a}{k}\binom{b}{k + s}$ , first rewrite $\binom{a}{k} = \binom{a}{a - k}$ . Now the lower indices add to $a + s$ , and the sum is $\binom{a + b}{a + s}$ .

Turning powers of $k$ into binomials

Sums like $\sum k \binom{n}{k}$ or $\sum k(k+1)(k+2)$ become easy once the polynomial in $k$ is written with binomial coefficients:

$k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ and $k(k - 1)\dbinom{n}{k} = n(n - 1)\dbinom{n-2}{k-2}$ .
$k(k + 1)(k + 2) = 6\dbinom{k + 2}{3}$ , which is ready for the hockey stick.
$\dfrac{1}{k + 1}\dbinom{n}{k} = \dfrac{1}{n + 1}\dbinom{n + 1}{k + 1}$ .

Worked example: Hockey stick

Find $\dbinom{3}{3} + \dbinom{4}{3} + \dots + \dbinom{10}{3}$ .

By the hockey stick identity, the sum is $\dbinom{11}{4} = 330$ .

Worked example: Vandermonde

Find $\displaystyle\sum_{k=0}^{5} \binom{5}{k}\binom{7}{k}$ .

Rewrite $\dbinom{7}{k} = \dbinom{7}{7 - k}$ . Now the lower indices add to $7$ , so the sum is $\dbinom{12}{7} = 792$ . (Choose $7$ of $12$ people, sorting by how many of the first $5$ are chosen.)

Worked example: Counting committees with a chair

Find $\displaystyle\sum_{k=0}^{8} k\binom{8}{k}$ .

Count pairs (committee, chair) from $8$ people. Choosing the committee first gives the sum. Choosing the chair first ( $8$ ways) and then any subset of the other $7$ people gives $8 \cdot 2^7 = 1024$ .

Worked example: Subsets of subsets

Find $\displaystyle\sum_{k=0}^{6}\binom{6}{k}\binom{k}{2}$ .

Count pairs $(S, T)$ with $T \subseteq S \subseteq \{1, \dots, 6\}$ and $|T| = 2$ . Choosing $S$ first gives the sum. Choosing $T$ first ( $\binom{6}{2} = 15$ ways), each of the other $4$ elements is in $S$ or not: $2^4 = 16$ . The sum is $15 \cdot 16 = 240$ .

Tip

Check any identity on a tiny case. For $\sum_k \binom{n}{k}^2 = \binom{2n}{n}$ with $n = 2$ : $1 + 4 + 1 = 6 = \binom{4}{2}$ . A thirty-second check catches most index errors.