Counting & ProbabilityDifficulty 45-950 tagged problems

Combinatorial Identities

Combinatorial Identities is the habit of proving binomial identities by counting one set two different ways. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

No tagged problems yet We are still curating launch-ready practice for this technique.

The Key Result

$$\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1} \quad (\text{hockey-stick identity})$$

Summing a fixed lower-index column of Pascal's triangle (the 'handle') gives a single binomial one row down and one column over (the 'blade') — provable by counting the same subsets two ways.

Why It Works

1
Count $(r+1)$-element subsets of $\{1, 2, \ldots, n+1\}$; there are $\binom{n+1}{r+1}$ of them.
2
Classify each subset by its largest element. If the largest is $i+1$, the remaining $r$ elements are chosen from $\{1, \ldots, i\}$, giving $\binom{i}{r}$ subsets.
3
As $i+1$ ranges over the possible largest values $r+1, r+2, \ldots, n+1$, the index $i$ ranges over $r, r+1, \ldots, n$.
4
Summing the disjoint cases counts every subset exactly once: $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$.

Worked Examples

Example 1

Evaluate $\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2}$ using a combinatorial identity.

1
This is the hockey-stick sum $\sum_{i=2}^{5}\binom{i}{2}$ with $r = 2$ and $n = 5$.
2
By the identity it equals $\binom{n+1}{r+1} = \binom{6}{3}$.
3
Compute the blade: $\binom{6}{3} = \dfrac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$.
4
Verify the handle directly: $1 + 3 + 6 + 10 = 20$. Match.

Answer:

$20$

Warm-up

Evaluate $\displaystyle\sum_{k=0}^{n}\binom{n}{k}$ and explain why, using a counting argument.

1
The left side counts subsets of an $n$-element set grouped by size: $\binom{n}{k}$ subsets of size $k$, summed over all $k$.
2
Together these count EVERY subset exactly once, and the total number of subsets is $2^n$ (include or exclude each element).
3
So $\sum_{k=0}^{n}\binom{n}{k} = 2^n$. (Equivalently set $x = 1$ in the binomial theorem $(1+x)^n = \sum_k \binom{n}{k}x^k$.)

Answer:

$2^n$

Contest level

Prove Pascal's rule $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ by a counting argument, then use it to express $\binom{10}{4}$ as a sum of two binomials.

1
Count the $k$-subsets of $\{1, 2, \ldots, n\}$; there are $\binom{n}{k}$ of them.
2
Split by whether element $n$ is included. If it is, choose the other $k-1$ from the first $n-1$: $\binom{n-1}{k-1}$ subsets. If not, choose all $k$ from the first $n-1$: $\binom{n-1}{k}$ subsets.
3
These cases are disjoint and exhaustive, so $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.
4
Apply with $n = 10, k = 4$: $\binom{10}{4} = \binom{9}{3} + \binom{9}{4} = 84 + 126 = 210$.

Answer:

$\binom{10}{4} = \binom{9}{3} + \binom{9}{4} = 210$

Olympiad / Challenge

Prove the identity $\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$ by a counting argument.

1
Count the $n$-element subsets of a $2n$-element set split into two halves: a 'left' group of $n$ and a 'right' group of $n$. There are $\binom{2n}{n}$ such subsets.
2
Classify each $n$-subset by how many elements $k$ it takes from the left group; then it takes $n - k$ from the right group.
3
The number of ways is $\binom{n}{k}\binom{n}{n-k}$, and since $\binom{n}{n-k} = \binom{n}{k}$, this is $\binom{n}{k}^2$.
4
Summing over $k = 0, \ldots, n$ counts every $n$-subset once: $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$. (This is the $m = n,\, r = n$ case of Vandermonde's identity.)

Answer:

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

Going Deeper

The binomial coefficients obey a rich algebra: the binomial theorem $(x+y)^n = \sum_k \binom{n}{k}x^k y^{n-k}$, Pascal's rule, the symmetry $\binom{n}{k} = \binom{n}{n-k}$, Vandermonde $\sum_k \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$, the hockey-stick $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$, and the absorption identity $k\binom{n}{k} = n\binom{n-1}{k-1}$. Most have one-line combinatorial (count two ways) and one-line generating-function proofs.
These identities are the toolbox for AMC/AIME sums of binomials, for collapsing telescoping or column sums in Pascal's triangle, and for evaluating expressions that look intractable until the right identity reframes them. The 'committee with a leader' and 'split into two halves' counting stories are the templates behind absorption and Vandermonde.
Pitfall: a combinatorial proof must count the SAME set both ways with no asymmetry — name one counted object precisely, then verify each side enumerates exactly it (the Vandermonde-squared proof relies on $\binom{n}{n-k} = \binom{n}{k}$, which is easy to drop). For alternating-sign identities like $\sum_k (-1)^k\binom{n}{k} = 0$, a pure count fails; use a sign-reversing involution or set $x = -1$ in the binomial theorem instead.

Spot the Signal

Use it when a sum of binomial coefficients needs a closed form, like hockey-stick or Vandermonde.
You can describe the hard part as proving binomial identities by counting one set two different ways, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by interpreting both sides as counts of the same committees and equating them.
Name the relation that makes Combinatorial Identities legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Grinding algebra when a one-line double-count is cleaner and harder to get wrong.
Applying Combinatorial Identities because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Count the same thing two ways; the identity falls out for free.

Try it on:

Establish or apply a binomial identity in a contest problem.

Back to techniques

Counting & ProbabilityDifficulty 45-950 tagged problems

Combinatorial Identities

No tagged problems yet We are still curating launch-ready practice for this technique.

The Key Result

$$\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1} \quad (\text{hockey-stick identity})$$

Summing a fixed lower-index column of Pascal's triangle (the 'handle') gives a single binomial one row down and one column over (the 'blade') — provable by counting the same subsets two ways.

Why It Works

1
Count $(r+1)$-element subsets of $\{1, 2, \ldots, n+1\}$; there are $\binom{n+1}{r+1}$ of them.
2
Classify each subset by its largest element. If the largest is $i+1$, the remaining $r$ elements are chosen from $\{1, \ldots, i\}$, giving $\binom{i}{r}$ subsets.
3
As $i+1$ ranges over the possible largest values $r+1, r+2, \ldots, n+1$, the index $i$ ranges over $r, r+1, \ldots, n$.
4
Summing the disjoint cases counts every subset exactly once: $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$.

Worked Examples

Example 1

Evaluate $\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2}$ using a combinatorial identity.

1
This is the hockey-stick sum $\sum_{i=2}^{5}\binom{i}{2}$ with $r = 2$ and $n = 5$.
2
By the identity it equals $\binom{n+1}{r+1} = \binom{6}{3}$.
3
Compute the blade: $\binom{6}{3} = \dfrac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$.
4
Verify the handle directly: $1 + 3 + 6 + 10 = 20$. Match.

Answer:

$20$

Warm-up

Evaluate $\displaystyle\sum_{k=0}^{n}\binom{n}{k}$ and explain why, using a counting argument.

1
The left side counts subsets of an $n$-element set grouped by size: $\binom{n}{k}$ subsets of size $k$, summed over all $k$.
2
Together these count EVERY subset exactly once, and the total number of subsets is $2^n$ (include or exclude each element).
3
So $\sum_{k=0}^{n}\binom{n}{k} = 2^n$. (Equivalently set $x = 1$ in the binomial theorem $(1+x)^n = \sum_k \binom{n}{k}x^k$.)

Answer:

$2^n$

Contest level

Prove Pascal's rule $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ by a counting argument, then use it to express $\binom{10}{4}$ as a sum of two binomials.

1
Count the $k$-subsets of $\{1, 2, \ldots, n\}$; there are $\binom{n}{k}$ of them.
2
Split by whether element $n$ is included. If it is, choose the other $k-1$ from the first $n-1$: $\binom{n-1}{k-1}$ subsets. If not, choose all $k$ from the first $n-1$: $\binom{n-1}{k}$ subsets.
3
These cases are disjoint and exhaustive, so $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.
4
Apply with $n = 10, k = 4$: $\binom{10}{4} = \binom{9}{3} + \binom{9}{4} = 84 + 126 = 210$.

Answer:

$\binom{10}{4} = \binom{9}{3} + \binom{9}{4} = 210$

Olympiad / Challenge

Prove the identity $\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$ by a counting argument.

1
Count the $n$-element subsets of a $2n$-element set split into two halves: a 'left' group of $n$ and a 'right' group of $n$. There are $\binom{2n}{n}$ such subsets.
2
Classify each $n$-subset by how many elements $k$ it takes from the left group; then it takes $n - k$ from the right group.
3
The number of ways is $\binom{n}{k}\binom{n}{n-k}$, and since $\binom{n}{n-k} = \binom{n}{k}$, this is $\binom{n}{k}^2$.
4
Summing over $k = 0, \ldots, n$ counts every $n$-subset once: $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$. (This is the $m = n,\, r = n$ case of Vandermonde's identity.)

Answer:

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

Going Deeper

The binomial coefficients obey a rich algebra: the binomial theorem $(x+y)^n = \sum_k \binom{n}{k}x^k y^{n-k}$, Pascal's rule, the symmetry $\binom{n}{k} = \binom{n}{n-k}$, Vandermonde $\sum_k \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$, the hockey-stick $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$, and the absorption identity $k\binom{n}{k} = n\binom{n-1}{k-1}$. Most have one-line combinatorial (count two ways) and one-line generating-function proofs.
These identities are the toolbox for AMC/AIME sums of binomials, for collapsing telescoping or column sums in Pascal's triangle, and for evaluating expressions that look intractable until the right identity reframes them. The 'committee with a leader' and 'split into two halves' counting stories are the templates behind absorption and Vandermonde.
Pitfall: a combinatorial proof must count the SAME set both ways with no asymmetry — name one counted object precisely, then verify each side enumerates exactly it (the Vandermonde-squared proof relies on $\binom{n}{n-k} = \binom{n}{k}$, which is easy to drop). For alternating-sign identities like $\sum_k (-1)^k\binom{n}{k} = 0$, a pure count fails; use a sign-reversing involution or set $x = -1$ in the binomial theorem instead.

Spot the Signal

Use it when a sum of binomial coefficients needs a closed form, like hockey-stick or Vandermonde.
You can describe the hard part as proving binomial identities by counting one set two different ways, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by interpreting both sides as counts of the same committees and equating them.
Name the relation that makes Combinatorial Identities legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Grinding algebra when a one-line double-count is cleaner and harder to get wrong.
Applying Combinatorial Identities because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Count the same thing two ways; the identity falls out for free.

Try it on:

Establish or apply a binomial identity in a contest problem.