Combinatorial Proof Technique

Intro to Proofs · Axiom Academy

LESSON Combinatorial Proof Techniques Prove an identity by counting one set of objects two different ways — if both counts describe the same set, the two expressions must be equal. The power of a combinatorial proof is that it is concrete. We tell a "counting story" for each side of an equation. If both stories count the same collection of objects , the equality holds automatically. 2. A Simple Example: 2n = n + n This is obvious algebraically, but watch how the counting argument works — it's the same machine we'll later point at harder identities. Picture a classroom of n girls and n boys, so 2n students in all. Tally the whole class in one pass: 2n students. Tally the girls ( n ), then the boys ( n ): n + n students. Both counts describe the very same students, so 2n = n + n . That equality of two honest counts is the proof. Now something with real content. We will prove, with no factorials at all: Ask one question two ways. From a group of n people, in how many ways can we pick a committee of k ? Choosing who is in automatically decides who is out . Pick the k people on the committee: ways. Pick the n-k people left off: ways. "Count two ways" has a close cousin. Instead of counting a set twice, a bijective proof pairs the elements of two sets so perfectly that they must be the same size. If you can exhibit such a pairing, then |A| = |B| without ever counting either set. The match itself is the proof.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.