Combinatorial Identities via Bijections — Mathematics Knowledge System

Overview

A combinatorial proof establishes an identity between two counting expressions by showing that both sides count the exact same finite set of objects — either by exhibiting a direct bijection between two sets, or by computing the size of one set in two different ways (double counting). This style of proof is often more illuminating than an algebraic derivation because it reveals *why* an identity is true rather than just confirming that symbol manipulation happens to work out. Pascal's rule C(n,k) = C(n-1,k-1) + C(n-1,k) is the classic first example: both sides count size-k subsets of an n-element set, split by whether a fixed element is included or excluded. Vandermonde's identity, the hockey-stick identity, and the identity that the sum of all binomial coefficients in a row of Pascal's triangle equals 2ⁿ are all provable the same way — find a set two counting arguments both describe, and the algebra follows for free.

Intuition

Every binomial-coefficient identity is secretly a story about counting the same collection of objects two different ways. For Pascal's rule, imagine choosing a k-person committee from n people including a specific person, Alice: either Alice is on the committee (choose the remaining k−1 members from the other n−1 people: C(n−1,k−1) ways) or she isn't (choose all k members from the other n−1 people: C(n−1,k) ways) — these two cases are mutually exclusive and cover every possible committee, so their counts add up to the total C(n,k). The sum-of-row identity 2ⁿ counts all subsets of an n-set by summing subsets of each size k — but it's also just each of the n elements independently choosing 'in' or 'out,' giving 2 choices per element and 2ⁿ total, a bijection between binary strings of length n and subsets. Vandermonde's identity counts choosing k people from a group split into m men and n women by summing over how many men (i) are chosen: this is the same total as directly choosing k from the combined m+n people.

Formal Definition

Definition

A combinatorial proof of A = B exhibits a set S with |S| = A by one counting argument and |S| = B by another (or a bijection between a set of size A and one of size B). Key identities provable this way:

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Pascal's rule

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

Sum of a row of Pascal's triangle

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

Vandermonde's identity

\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}

Hockey-stick identity

Worked Examples

C(6,3) counts 3-person committees from 6 people, one of whom is Alice. Split by whether Alice is chosen.
$\binom{6}{3} = \binom{5}{2} + \binom{5}{3}$
If Alice is on the committee, choose 2 more from the remaining 5: C(5,2). If not, choose all 3 from the remaining 5: C(5,3).
$\binom{5}{2} = 10, \quad \binom{5}{3} = 10$
Add the two cases and compare to the direct count C(6,3).
$10 + 10 = 20 = \binom{6}{3}$

Answer: C(6,3) = 20 = C(5,2) + C(5,3) = 10 + 10, confirming Pascal's rule both combinatorially and numerically.

Practice Problems

Difficulty 3/10

Verify that the sum of row n=5 of Pascal's triangle equals 2^5.

Difficulty 4/10

Use the hockey-stick identity to compute Σᵢ₌₂⁶ C(i,2), i.e. C(2,2)+C(3,2)+C(4,2)+C(5,2)+C(6,2).

Difficulty 6/10

A committee of 4 people is chosen from a group of 10, one of whom is the group's founder. Using Pascal's rule as a combinatorial argument, express C(10,4) as a sum of two binomial coefficients based on whether the founder is included, and verify the numbers.

Quiz

Summary

A combinatorial proof shows two counting expressions are equal by demonstrating they count the same set of objects, either directly or via a bijection.
Pascal's rule C(n,k) = C(n-1,k-1) + C(n-1,k) follows from splitting subsets by whether a fixed element is included.
The identity Σ C(n,k) = 2ⁿ follows from a bijection between subsets of an n-set and binary strings of length n.
Vandermonde's identity C(m+n,k) = Σᵢ C(m,i)C(n,k−i) counts choosing k people from a combined group by splitting on how many come from each subgroup.
The hockey-stick identity Σ_{i=r}^{n} C(i,r) = C(n+1,r+1) and similar results all reduce to finding one set that two counting arguments both correctly describe.

References

WebsiteWikipedia — Combinatorial proof
WebsiteWikipedia — Pascal's rule
WebsiteWikipedia — Vandermonde's identity