Discrete Math › Section D · Counting › Topic D.6
Combinatorial proofs
If two expressions both count the same collection of things, they must be equal. Combinatorial proofs turn that simple observation into short, convincing proofs of identities that would be tedious to prove with algebra.
Two ways to prove an identity
Pascal's triangle is full of patterns, and each pattern is an identity waiting to be proved. One way is algebra: substitute the formula \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\) from "Combinations and permutations" and manipulate the fractions until both sides match. That works, but it rarely explains why the identity holds. The other way is to tell a counting story. Find a question, show that the left side answers it, show that the right side also answers it, and conclude that the two sides are equal, because a collection has only one size. Such an argument is called a combinatorial proof, and it often fits in a few sentences.
The recipe
Every combinatorial proof has the same four parts. 1. The question: describe one specific set of objects, such as "the 3-person committees that can be formed from 9 people". 2. Answer one: explain carefully why the left side counts that set. 3. Answer two: explain why the right side counts the same set, usually by splitting it into cases or building it in a different order. 4. The conclusion: both sides count the same set, so they are equal. The proof is only as good as the two explanations. Each must account for every object exactly once, so the sum principle, the product principle and the quotient principle all need their conditions checked.
Worked example: in or out
Prove that \(\binom{n}{k} = \binom{n}{n-k}\). 1. Question: how many ways are there to choose a team of \(k\) players from \(n\) people? 2. Answer one: choose the \(k\) players directly, in \(\binom{n}{k}\) ways. 3. Answer two: instead choose the \(n - k\) people who are left out, in \(\binom{n}{n-k}\) ways. Each choice of who sits out produces exactly one team, and each team arises from exactly one such choice. 4. Both sides count teams, so they are equal. The algebraic proof also works, since swapping \(k\) and \(n - k\) leaves \(\frac{n!}{k!(n-k)!}\) unchanged, but the story explains why each row of the triangle is symmetric.
Worked example: Pascal's rule
Prove that \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) for \(1 \le k \le n - 1\). 1. Question: how many \(k\)-person committees can be formed from \(n\) people, one of whom is Priya? 2. Answer one: \(\binom{n}{k}\). 3. Answer two: split by Priya. Committees that include her need \(k - 1\) more members from the other \(n - 1\) people: \(\binom{n-1}{k-1}\). Committees without her take all \(k\) members from those \(n - 1\): \(\binom{n-1}{k}\). The cases are disjoint and cover every committee, so the sum principle adds them. 4. Conclusion: the identity holds. With \(n = 10\) and \(k = 3\): \(120 = 36 + 84\).
Row sums revisited
Prove that \(\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n\). Question: how many subsets does a set of \(n\) elements have? Answer one: sort the subsets by size. There are \(\binom{n}{k}\) subsets of size \(k\), and every subset has exactly one size from 0 to \(n\), so the sum principle gives the left side. Answer two: build a subset by deciding in or out for each element, two options \(n\) times, which gives \(2^n\). The same identity followed from the binomial theorem in "Pascal's triangle and the binomial theorem" by setting \(x = y = 1\). Having two different proofs is common, and the counting proof shows what the sum means.
Worked example: a committee and its chair
Prove that \(k\binom{n}{k} = n\binom{n-1}{k-1}\) for \(1 \le k \le n\). 1. Question: how many ways can a \(k\)-person committee with a named chair be chosen from \(n\) people? 2. Answer one: choose the committee, \(\binom{n}{k}\), then pick its chair from the \(k\) members: \(k\binom{n}{k}\). 3. Answer two: choose the chair first from all \(n\) people, then the other \(k - 1\) members from the remaining \(n - 1\): \(n\binom{n-1}{k-1}\). 4. Both count chaired committees, so they are equal. With \(n = 11\) and \(k = 4\): \(4 \cdot 330 = 1320 = 11 \cdot 120\), matching the count found in "Combinations and permutations".
Worked example: the hockey stick
Prove that
1. Question: how many \((k+1)\)-element subsets does \(\{1, 2, \ldots, n+1\}\) have? 2. Answer one: \(\binom{n+1}{k+1}\). 3. Answer two: sort the subsets by their largest element \(m\). If the largest element is \(m\), the other \(k\) elements come from the \(m - 1\) numbers below it, in \(\binom{m-1}{k}\) ways, and \(m\) runs from \(k + 1\) to \(n + 1\). Adding the cases gives the left side. 4. Check with \(k = 2\), \(n = 5\): \(1 + 3 + 6 + 10 = 20 = \binom{6}{3}\). On the triangle, the terms form a diagonal line with the total just below its end, like a hockey stick.
Worked example: sum of squares
Prove that
1. Question: a group has \(n\) women and \(n\) men; how many \(n\)-person committees can it form? 2. Answer one: \(\binom{2n}{n}\), choosing from all \(2n\) people. 3. Answer two: sort by the number of women \(k\). Choose them in \(\binom{n}{k}\) ways and the \(n - k\) men in \(\binom{n}{n-k}\) ways, which equals \(\binom{n}{k}\) by symmetry. So case \(k\) contributes \(\binom{n}{k}^2\), and the cases add up to the left side. 4. Check with \(n = 4\): \(1 + 16 + 36 + 16 + 1 = 70 = \binom{8}{4}\).
Common mistakes to avoid
First, telling two different stories, one per side, about two different sets: both answers must count exactly the same collection. Second, splitting into cases that overlap or miss something, so the sum principle does not apply; check that every object lands in exactly one case. Third, building objects in stages where some objects can be built in more than one way, which overcounts. Fourth, skipping the numerical check: testing small values, such as \(n = 4\), catches most errors before they reach the final proof. Fifth, writing only the question and the formulas without explaining why each side counts it.
Key takeaways
A combinatorial proof shows that two expressions are equal by showing that both count the same set. State the question, justify each side's count, and conclude. Choosing who is in or who is out proves symmetry; splitting on one special element proves Pascal's rule; counting subsets by size or by in-or-out choices proves the row sums. Naming a chair, sorting by the largest element and sorting by the number of women prove the chair identity, the hockey stick and the sum of squares. Always test the identity on small numbers.
Flashcards
Flashcard
Show both sides count the same set
Test your understanding
Question 1 of 5
Which counting question has both C(n, k) and C(n, n − k) as correct answers?
Question 2 of 5
By the hockey stick identity, C(3, 3) + C(4, 3) + C(5, 3) + C(6, 3) equals which single coefficient?
Question 3 of 5
In the committee proof of Pascal's rule, which term counts the k-person committees that do NOT include the fixed person?
Question 4 of 5
Counting k-person committees with a named chair in two orders proves which identity?
Question 5 of 5
What is C(3, 0)² + C(3, 1)² + C(3, 2)² + C(3, 3)²?
