26-10 — Combinatorial Proofs

Phase: Combinatorics | Subject: 26-10 Prerequisites: 26-04-binomial-theorem-combinatorics.md, 26-06-inclusion-exclusion-principle.md Next subject: 27-01-introduction-to-differential-equations.md

Learning Objectives

By the end of this subject, you will be able to:

1. Construct combinatorial proofs by double-counting
2. Prove binomial identities without algebra
3. Use bijections to show two sets have the same size
4. Apply the method of "counting in two ways" to sums and identities
5. Recognize when a problem demands a combinatorial vs algebraic proof

Core Content

What Is a Combinatorial Proof?

A combinatorial proof shows that two expressions are equal by interpreting both as counting the same set of objects, but in two different ways.

Structure: 1. Define a set $S$ of combinatorial objects 2. Count $|S|$ using Expression A (one classification) 3. Count $|S|$ using Expression B (a different classification) 4. Conclude Expression A = Expression B

Double-Counting (Counting in Two Ways)

Count the elements of a set in two different ways. The counts must be equal.

Example: Prove $\binom{n}{k} = \binom{n}{n-k}$.

Proof: Let $S$ = all $k$-subsets of ${1, 2, \ldots, n}$. - Way 1: Choose $k$ elements to include. Count: $\binom{n}{k}$. - Way 2: Choose $n-k$ elements to EXCLUDE. Count: $\binom{n}{n-k}$. These count the same thing, so $\binom{n}{k} = \binom{n}{n-k}$.

Classic Identities via Combinatorial Proof

1. Pascal's Identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Proof: Let $S$ = $k$-subsets of ${1, \ldots, n}$. Partition $S$ into: - Subsets containing element $n$: choose $k-1$ from the first $n-1$ → $\binom{n-1}{k-1}$. - Subsets NOT containing element $n$: choose $k$ from the first $n-1$ → $\binom{n-1}{k}$.

2. Committee-Chair Identity: $k\binom{n}{k} = n\binom{n-1}{k-1}$

Proof: Count committees of size $k$ with a designated chair: - Left: choose $k$ members ($\binom{n}{k}$), then chair ($k$ choices). - Right: choose chair ($n$ choices), then remaining $k-1$ members ($\binom{n-1}{k-1}$).

3. Hockey-Stick Identity: $\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}$

Proof: Count $(r+1)$-subsets of ${0, 1, \ldots, n}$. Group by the largest element $k$. If largest is $k$, the remaining $r$ elements are chosen from ${0, \ldots, k-1}$. Summing over $k = r, r+1, \ldots, n$ gives $\sum \binom{k}{r}$.

Bijection Proofs

To prove $|A| = |B|$, construct a one-to-one correspondence (bijection) between the sets.

Example: Prove that the number of subsets of ${1,\ldots,n}$ with an even number of elements equals the number with an odd number of elements (for $n \geq 1$).

Proof: Pair each even subset $S$ with $S \triangle {1}$ (symmetric difference with {1}). This toggles element 1, so even→odd and odd→even. This is a bijection, so $|{S: |S| \text{ even}}| = |{S: |S| \text{ odd}}| = 2^{n-1}$.

Key Terms

• Combinatorial Proof
• Double-Counting
• Bijection
• Story Proof

Worked Examples

Example 1: Team-and-Captain Identity

Prove combinatorially: $\sum_{k=1}^{n} k\binom{n}{k} = n2^{n-1}$.

Solution: Right side: Choose a captain ($n$ ways), then any subset of the other $n-1$ players ($2^{n-1}$ ways). This counts all teams with a designated captain.

Left side: For each possible team size $k$, choose $k$ players ($\binom{n}{k}$), then choose a captain among those $k$ ($k$ ways). Sum over all $k$.

Example 2: Vandermonde's Identity

Prove combinatorially: $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$.

Solution: Choose $r$ people from a group of $m$ men and $n$ women. - Left: directly choose $r$ from $m+n$. - Right: for each $k$, choose $k$ men and $r-k$ women.

Example 3: Square Sum

Prove $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.

Solution: Choose $n$ people from $2n$ ($n$ men, $n$ women). - Right: $\binom{2n}{n}$ directly. - Left: for each $k$, choose $k$ men and $n-k$ women: $\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2$.

Quiz

Q1: What does the concept of Combinatorial Proof primarily refer to in this subject?

A) The definition and application of Combinatorial Proof B) A visual representation of Combinatorial Proof C) A historical anecdote about Combinatorial Proof D) A computational error related to Combinatorial Proof

Correct: A)

• If you chose A: Combinatorial Proof is defined as: the definition and application of combinatorial proof. The other options describe different aspects that are not the primary focus. Correct!
• If you chose B: This is incorrect. Combinatorial Proof is defined as: the definition and application of combinatorial proof. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Combinatorial Proof is defined as: the definition and application of combinatorial proof. The other options describe different aspects that are not the primary focus.
• If you chose D: This is incorrect. Combinatorial Proof is defined as: the definition and application of combinatorial proof. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) \binom{n}{k} = \binom{n}{n-k} B) A simplified version of \binom{n}{k} = \binom{n}{n-k... C) An unrelated formula from a different topic D) The inverse operation of the formula in question

Correct: A)

• If you chose A: The formula \binom{n}{k} = \binom{n}{n-k} is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula \binom{n}{k} = \binom{n}{n-k} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula \binom{n}{k} = \binom{n}{n-k} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula \binom{n}{k} = \binom{n}{n-k} is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Double-Counting?

A) It replaces all other methods in this domain B) It is used only in advanced research contexts C) It is used to double-counting in mathematical analysis D) It is primarily a historical notation system

Correct: C)

• If you chose A: This is incorrect. Double-Counting serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Double-Counting serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: Double-Counting serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose D: This is incorrect. Double-Counting serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Bijection is TRUE?

A) Bijection is not related to this subject B) Bijection is an advanced topic beyond this subject's scope C) Bijection is a fundamental concept covered in this subject D) Bijection is mentioned only as a historical footnote

Correct: C)

• If you chose A: This is incorrect. Bijection is a fundamental concept covered in this subject. This subject covers Bijection as part of its core content.
• If you chose B: This is incorrect. Bijection is a fundamental concept covered in this subject. This subject covers Bijection as part of its core content.
• If you chose C: Bijection is a fundamental concept covered in this subject. This subject covers Bijection as part of its core content. Correct!
• If you chose D: This is incorrect. Bijection is a fundamental concept covered in this subject. This subject covers Bijection as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) An unrelated numerical value B) Vandermonde's Identity C) The inverse of the correct answer D) A different result from a common mistake

Correct: B)

• If you chose A: This is incorrect. The worked examples show that the result is Vandermonde's Identity. The other options represent common errors.
• If you chose B: The worked examples show that the result is Vandermonde's Identity. The other options represent common errors. Correct!
• If you chose C: This is incorrect. The worked examples show that the result is Vandermonde's Identity. The other options represent common errors.
• If you chose D: This is incorrect. The worked examples show that the result is Vandermonde's Identity. The other options represent common errors.

Q6: How are Bijection and Story Proof related?

A) Bijection is the inverse of Story Proof B) Bijection and Story Proof are completely unrelated topics C) Bijection and Story Proof are closely related concepts D) Bijection is a special case of Story Proof

Correct: C)

• If you chose A: This is incorrect. Both Bijection and Story Proof are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both Bijection and Story Proof are covered in this subject as interconnected topics.
• If you chose C: Both Bijection and Story Proof are covered in this subject as interconnected topics. Correct!
• If you chose D: This is incorrect. Both Bijection and Story Proof are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with What Is A Combinatorial Proof??

A) What Is A Combinatorial Proof? is always computed the same way in all contexts B) A common mistake is confusing What Is A Combinatorial Proof? with a similar concept C) The main error with What Is A Combinatorial Proof? is using it when it is not needed D) What Is A Combinatorial Proof? has no common misconceptions

Correct: B)

• If you chose A: This is incorrect. Students often confuse What Is A Combinatorial Proof? with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: Students often confuse What Is A Combinatorial Proof? with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose C: This is incorrect. Students often confuse What Is A Combinatorial Proof? with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse What Is A Combinatorial Proof? with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Double-Counting (Counting In Two Ways)?

A) Use Double-Counting (Counting In Two Ways) only in pure mathematics contexts B) Avoid Double-Counting (Counting In Two Ways) unless explicitly instructed C) Apply Double-Counting (Counting In Two Ways) to solve problems in this subject's domain D) Double-Counting (Counting In Two Ways) is not practically useful

Correct: C)

• If you chose A: This is incorrect. Double-Counting (Counting In Two Ways) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. Double-Counting (Counting In Two Ways) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: Double-Counting (Counting In Two Ways) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose D: This is incorrect. Double-Counting (Counting In Two Ways) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Give a combinatorial proof of $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$.
   

   Click for answer

   The right side counts all subsets of an $n$-element set. The left side counts subsets by size: $\binom{n}{k}$ subsets of size $k$. Summing over all $k$ gives the total.

2. Prove combinatorially that $\binom{n}{2} = 1 + 2 + \cdots + (n-1)$.
   

   Click for answer

   Right side: number of 2-subsets of $\{1,\ldots,n\}$. Left side: for largest element $k$ (from 2 to $n$), the other element is from $\{1,\ldots,k-1\}$ ($k-1$ choices). Sum $1+2+\cdots+(n-1)$.

3. Find a bijection proof that the number of ways to choose a subset with an even number of elements equals $2^{n-1}$.
   

   Click for answer

   Toggle element 1: $S \mapsto S \triangle \{1\}$ pairs each even subset with an odd one. Since total subsets = $2^n$, each parity class has $2^{n-1}$.

4. Prove combinatorially: $\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m}$ for $0 \leq m \leq k \leq n$.
   

   Click for answer

   Left: choose $k$ from $n$ (a "large set"), then $m$ from those $k$ (a "small set"). Right: choose the $m$ "small set" members first ($\binom{n}{m}$), then the remaining $k-m$ from the other $n-m$ ($\binom{n-m}{k-m}$). Both count pairs $(S, T)$ where $T \subseteq S$, $|S|=k$, $|T|=m$.

5. Give a combinatorial proof of $\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)2^{n-2}$.
   

   Click for answer

   Count committees with a designated chair AND vice-chair (they can be the same person). Right: choose chair ($n$), choose vice-chair ($n$, maybe same person), remaining from $n-1$ or $n-2$. Left can also be derived from $\sum k\binom{n}{k} + \sum k(k-1)\binom{n}{k}$.

Summary

Key takeaways:

• Combinatorial proof = count the same set in two different ways
• Double-counting yields identities without algebra
• Bijections show two sets have equal size
• "Story proofs" are often more intuitive and reveal why identities are true
• Pascal, Vandermonde, Hockey-Stick, committee identities all have elegant combinatorial proofs

Pitfalls

• Confusing a combinatorial proof with an algebraic manipulation: A true combinatorial proof counts the same set of objects in two different ways — it should tell a "story" about what each side counts. Students often write "LHS = RHS" and then rearrange symbols algebraically, which is not a combinatorial proof. Every step must be justified in terms of counting, selection, or arrangement.
• Overlooking the partition in double-counting proofs: When proving an identity like $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$, the partition parameter $k$ must be clearly defined — here $k$ is the number of people chosen from the first group. A vague or missing definition of what the index of summation means causes the proof to collapse. Always state: "For each $k$, we count the objects where [condition involving $k$] holds."
• Miscounting when constructing bijections: Bijection proofs require both injectivity and surjectivity. A common error is constructing a mapping and claiming it's a bijection without verifying it's invertible. For example, the map $S \mapsto S \triangle {1}$ toggles element 1 — you must confirm applying it twice returns the original set (involution), which proves it's its own inverse and therefore a bijection.
• Forgetting the range of summation indices in "Hockey-Stick" style proofs: In $\sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1}$, the largest element $k$ of the $(r+1)$-subset ranges from $r$ to $n$. A common error is starting the sum at $k=r+1$ or ending at $n-1$, which shifts the result. Always verify that the smallest possible largest element is $r$ (all elements $0,1,\ldots,r$) and the largest possible is $n$.
• Believing every combinatorial identity has an obvious combinatorial proof: Some identities (like those involving alternating sums or generating functions) genuinely require more machinery. Don't force a combinatorial proof where it doesn't fit — recognizing when a binomial identity is best proved algebraically (e.g., via induction or generating functions) is also an important skill.

Next Steps

Next up: 27-01-introduction-to-differential-equations.md — beginning the ODE phase.