Recipe

Write a combinatorial proof of a counting identity

Use when: you need to prove an identity between two counting expressions holds for every valid input, not just check it for one number

Goal: a proof that both sides of the identity count the exact same collection, so they must be equal

Taught in Combinatorial proof

1. 1

   Look for a single, concrete collection, such as subsets of a set, committees with a role, or orderings of a group, that both sides of the identity could plausibly be counting.

   Example

   For n\binom{n-1}{k-1}=k\binom{n}{k}, both sides can be read as counting the same thing: a size-k committee from n people, with one member designated chair.

   Why: a combinatorial proof only works when a genuine shared counting question exists; an identity that happens to be numerically true is not automatically provable this way.

2. 2

   Explain, in plain counting language, why that side of the identity is exactly the number of ways to build the chosen collection.

   Example

   \binom{n}{k} chooses the k-person committee first, then k chooses the chair from within it, giving k\binom{n}{k}.

   Why: this half establishes that the collection's true count really is the value one side of the identity claims.

3. 3

   Split the same collection into cases and add, or pair its members one-to-one with another counted set, so the other side's expression falls out.

   Example

   n chooses the chair first from everyone, then \binom{n-1}{k-1} fills the remaining k-1 committee spots from the other n-1 people, giving n\binom{n-1}{k-1}.

   • the natural argument builds the collection in stages, or splits it by a feature such as a largest element or a distinguished chair — use a direct, case-based count.
   • the natural argument matches each object counted by one side to exactly one object counted by the other, with no formula in between — use a bijective count instead.

   Why: proving both sides count the identical collection, not two collections that merely have equal size, is what makes the identity self-evident once both counts are stated.

4. 4

   Since both expressions count the same collection, state that they must be equal, with no further algebra needed.

   Why: this is the entire payoff of a combinatorial proof, an equality reached without expanding a single factorial.