Combinatorial Proofs Summary

Intro to Proofs · Axiom Academy

A recap of how counting arguments deliver elegant proofs, the pigeonhole principle guarantees existence, and generating functions turn counting into algebra. Multiple perspectives: the same quantity can be counted many ways, and each way reveals a different insight. Existence vs. construction: the pigeonhole principle proves something exists without finding it explicitly — the power of non-constructive reasoning. Algebra from counting: many algebraic identities have combinatorial interpretations that make them obvious rather than mysterious. Recurrence to formula: generating functions systematically convert recursive definitions into closed-form formulas. Proof beauty: a combinatorial proof often reveals the real reason an identity holds, making it intuitive and memorable. Core Concept Combinatorial Proof Prove two expressions are equal by showing they both count the same set in different ways. If you count one collection by two methods, the answers must agree — no algebra required. Double counting: count the same set two ways; both totals are forced equal. Story proof: phrase it as choosing committees, arranging objects, or distributing items to make the logic concrete. Why it wins: usually shorter and more intuitive than algebra, and it shows why an identity is true. To show two sets have the same size, build a one-to-one correspondence pairing each element of A with exactly one element of B , and vice versa.

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