MGU Mathematics Series — Combinatorics
Part III: Advanced Counting and Combinatorial Proof
Algebraic Proof · Combinatorial Proof · Double Counting · Bijections · Identities
Chapter 9 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 9:
Combinatorial Identities
and Proof

Algebraic proof, combinatorial proof, double counting, bijections, Pascal's identity, Vandermonde's identity, the Hockey-Stick identity, Binomial Theorem substitutions, and recurrence-based arguments

■ Math Level: Combinatorics ■

■ 14 Sections  •  Part III of 5 ■

Part III: Advanced Counting and Combinatorial Proof  ·  Follows Chapter 8: Pigeonhole Principle  ·  Prepares for Chapter 10: Recurrence Relations

Chapter 9 — Front Matter

Purpose and Overview

This chapter teaches one of the deepest and most satisfying skills in combinatorics: proving that a counting formula is correct, not by calculation alone, but by understanding what the formula means. A combinatorial identity is an equation involving counts, and a combinatorial proof is an argument that explains why both sides of that equation count the same thing.

By the end of this chapter, you will be able to prove identities involving binomial coefficients, factorials, and counting expressions using several strategies: algebraic manipulation, double counting, bijective argument, and recurrence. You will also see that combinatorial proof is different in character from the mechanical derivation of formulas — it is an act of interpretation, a way of reading an equation as a statement about finite structures.

Opening Question

Here is an identity you may have seen in Chapter 5:

\[\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\]

You can verify this numerically for small values of \(n\). For \(n = 3\):

\[\binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 1 + 3 + 3 + 1 = 8 = 2^3\]

But why is it true? Can you explain it not just by calculation, but by meaning? What does \(\binom{n}{k}\) count? What does \(2^n\) count? Is there a structure that both sides describe? This chapter answers that question — and then asks many more like it.

Why This Chapter Matters

Combinatorial proof is important in algorithms and computer science, where proving a count ensures a formula gives the right output size or complexity bound. In probability, many formulas rest on counting identities. In cryptography and coding theory, encoding and decoding processes depend on exact counts — proofs ensure structural reliability. In data science, understanding why a formula counts what it claims helps analysts avoid errors. And in pure mathematics, combinatorial proof is an entry point into proof-based thinking more generally.

14Sections
10Objectives
10Key Terms
15+Worked Examples

Learning Objectives

  1. 1Explain what a combinatorial identity is and what it means for one to be proved.
  2. 2Prove simple identities using algebraic manipulation of factorials and binomial coefficients.
  3. 3Explain the strategy of double counting and use it to prove identities.
  4. 4Explain what a bijective proof is and construct simple bijections.
  5. 5Prove Pascal's identity using both algebraic and combinatorial arguments.
  6. 6State and interpret Vandermonde's identity.
  7. 7State and prove the Hockey-Stick identity.
  8. 8Derive identities from the Binomial Theorem by substituting specific values.
  9. 9Use recurrence relations to verify or prove counting statements.
  10. 10Write clear, complete combinatorial arguments.
Chapter 9 — Contents

Sections at a Glance

Sections 9.1 – 9.2
What Identities Are and Algebraic Proof
Definitions · Proof vs. Verification · Factorial Manipulation · Symmetry · Pascal's Identity
Section 9.1

What a Combinatorial Identity Is

A combinatorial identity is an equation that relates two or more counting expressions and holds for all values of its variables in the appropriate range. The simplest examples are equations involving binomial coefficients, factorials, sums of combinations, or products of counting formulas. Here are four central identities this chapter will prove:

\[\binom{n}{k} = \binom{n}{n-k}\]
\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n\]
\[\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}\]
Verification Is Not Proof

Checking that an identity holds for \(n = 1, 2, 3, 4\) does not prove it for all \(n\). A proof requires an argument that works for every valid value of the variables. Use numerical checks to test your reasoning, not to replace it.

Five Proof Strategies Covered in This Chapter

Algebraic proof — Manipulate one side symbolically until it equals the other side.

Combinatorial proof — Describe a set or count that both sides represent, then argue they must be equal.

Double counting — Count the same set or relationship in two ways and set the results equal.

Bijective proof — Build an explicit pairing between two sets to show they have the same size.

Recurrence-based proof — Use the recursive structure of a formula with base cases and inductive steps.

Section 9.2

Algebraic Proofs of Identities

An algebraic proof works by manipulating the symbolic definitions of the expressions involved. For binomial coefficients, the key definition is:

\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

Using this definition, expand and simplify one side until it equals the other. Guidelines: start with the more complicated side; expand using factorial formulas; factor, cancel, or regroup until you reach the simpler side; track what values the variables must take at each step.

Example 9.2.1
Algebraic proof of the symmetry identity
  • ProblemProve that \(\binom{n}{k} = \binom{n}{n-k}\) for all integers \(n \geq 0\) and \(0 \leq k \leq n\).
  • ThinkStart with the right side and expand using the factorial definition. Then simplify and show it equals the left side.
  • Analyze \[\binom{n}{n-k} = \frac{n!}{(n-k)!\bigl(n-(n-k)\bigr)!} = \frac{n!}{(n-k)!\,k!}\] Since \(k!(n-k)! = (n-k)!\,k!\), this equals \(\dfrac{n!}{k!(n-k)!} = \binom{n}{k}\).
  • CheckThe step is valid whenever \(0 \leq k \leq n\), which is the stated range.
  • InterpretChoosing \(k\) objects to include is algebraically identical to choosing \(n-k\) objects to leave out. The formula \(\dfrac{n!}{k!(n-k)!}\) is symmetric in \(k\) and \(n-k\).
Proved: \(\binom{n}{k} = \binom{n}{n-k}\) for \(0 \leq k \leq n\).
Example 9.2.2
Algebraic proof of Pascal's identity
  • ProblemProve that \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) for \(n \geq 1\) and \(1 \leq k \leq n-1\).
  • RepresentExpand each term on the right side: \[\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}, \qquad \binom{n-1}{k} = \frac{(n-1)!}{k!(n-1-k)!}\]
  • AnalyzeFind a common denominator of \(k!(n-k)!\) and add: \[\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!\cdot k + (n-1)!\cdot(n-k)}{k!(n-k)!} = \frac{(n-1)!\cdot n}{k!(n-k)!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}\]
  • CheckValid for \(n \geq 1\) and \(1 \leq k \leq n-1\). Boundary cases hold by convention (\(\binom{n-1}{-1} = 0\) and \(\binom{n-1}{n} = 0\)).
Proved: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) algebraically. A combinatorial proof follows in Section 9.7.
Sections 9.3 – 9.6
Combinatorial Proof, Double Counting, and Bijections
Identify · Count Both Sides · Double Counting · Row Sum · Bijective Proofs
Section 9.3

Combinatorial Proofs

A combinatorial proof does not manipulate symbols. Instead, it identifies a finite set and counts it in two ways. The structure is always:

Structure of a Combinatorial Proof

Step 1 — Identify a set that both sides of the identity count.

Step 2 — Count from the left: explain why the left-hand side counts that set correctly.

Step 3 — Count from the right: explain why the right-hand side counts that set correctly, using a different method or decomposition.

Step 4 — Conclude: since both counts describe the same set, they must be equal.

Example 9.3.1
Combinatorial proof of the symmetry identity
  • ProblemGive a combinatorial proof that \(\binom{n}{k} = \binom{n}{n-k}\).
  • Think\(\binom{n}{k}\) counts \(k\)-element subsets of an \(n\)-element set. \(\binom{n}{n-k}\) counts \((n-k)\)-element subsets of the same set. Is there a natural relationship between them?
  • RepresentLet \(S\) be a set of \(n\) distinct elements. Let \(\mathcal{A}\) be all \(k\)-element subsets of \(S\), and let \(\mathcal{B}\) be all \((n-k)\)-element subsets of \(S\).
  • AnalyzeEvery \(k\)-element subset \(A \in \mathcal{A}\) has a complement \(S \setminus A\), which is an \((n-k)\)-element subset in \(\mathcal{B}\). The map \(A \mapsto S \setminus A\) is a bijection: every subset of size \(n-k\) arises as the complement of exactly one subset of size \(k\).
  • ConcludeBecause there is a bijection between \(\mathcal{A}\) and \(\mathcal{B}\), they have the same size, so \(\binom{n}{k} = \binom{n}{n-k}\).
  • InterpretChoosing \(k\) elements to include is the same as choosing \(n-k\) elements to exclude. This is the combinatorial meaning behind the symmetry of binomial coefficients.
Proved combinatorially: inclusion and exclusion are mirror operations.
Section 9.4

Double Counting

Double counting is a proof technique in which you count the same quantity in two different ways. You choose a set or a collection of ordered pairs and count its size from two directions. Because both counts describe the same quantity, they must be equal. Setting them equal gives the identity.

Double counting is especially powerful when counting relationships between two groups — for example, (student, committee) pairs, counted either by students or by committees.

Example 9.4.1
Double counting to prove a sum identity
  • ProblemProve that \(\displaystyle\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}\).
  • ThinkThe left side involves \(k \cdot \binom{n}{k}\), suggesting we count a pair: a subset and a distinguished element inside it. The right side \(n \cdot 2^{n-1}\) suggests choosing a distinguished element first and then building a subset around it.
  • RepresentLet \(S = \{1, 2, \ldots, n\}\). Count ordered pairs \((T, x)\) where \(T\) is a subset of \(S\) and \(x \in T\) is a designated "leader" from \(T\).
  • Count 1Group by the size of \(T\). If \(|T| = k\), there are \(\binom{n}{k}\) ways to choose \(T\) and then \(k\) ways to choose the leader. Summing over all sizes: \[\text{Total} = \sum_{k=0}^{n} k \binom{n}{k}\] (The \(k = 0\) term contributes zero since an empty set has no leader.)
  • Count 2Choose the leader \(x\) first: \(n\) choices. Then decide, for each remaining \(n-1\) element, whether it belongs to \(T\): \(2^{n-1}\) subsets. So the total is \(n \cdot 2^{n-1}\).
  • CheckFor \(n = 3\): Left side = \(0 + 3 + 6 + 3 = 12\). Right side = \(3 \cdot 4 = 12\). ✓
  • ConcludeBoth counts describe the same collection of (subset, leader) pairs, so \(\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}\).
Proved: whether you group by subset size or choose the leader first, both methods yield the same total.
Section 9.5

Counting the Same Set Two Ways

Example 9.5.1
Combinatorial proof of the row sum identity
  • ProblemProve that \(\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n\).
  • RepresentLet \(S = \{1, 2, \ldots, n\}\). Let \(\mathcal{P}\) be the power set of \(S\) — the set of all subsets of \(S\).
  • Count LeftPartition \(\mathcal{P}\) by subset size. For each \(k\) from \(0\) to \(n\), there are \(\binom{n}{k}\) subsets of \(S\) with exactly \(k\) elements. Since every subset has some size between \(0\) and \(n\), these sizes partition \(\mathcal{P}\): \[|\mathcal{P}| = \sum_{k=0}^{n} \binom{n}{k}\]
  • Count RightBuild a subset by deciding, independently for each element \(i \in S\), whether to include it. There are 2 choices per element and \(n\) elements, giving \(2^n\) total subsets.
  • Conclude\[\sum_{k=0}^{n} \binom{n}{k} = |\mathcal{P}| = 2^n\]
  • InterpretThe number of subsets can be counted by summing over sizes, or by making \(n\) independent binary decisions. Both perspectives yield the same total.
Proved: \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\) via two ways of counting all subsets of an \(n\)-element set.
Section 9.6

Bijective Proofs

A bijective proof establishes that two sets have the same size by constructing an explicit bijection — a one-to-one, onto function — between them. The key task is: (1) define the two sets explicitly; (2) define the function from one to the other; (3) verify it is one-to-one and onto.

Example 9.6.1
Bijective proof of the symmetry identity
  • ProblemProve \(\binom{n}{k} = \binom{n}{n-k}\) by constructing a bijection.
  • RepresentLet \(S = \{1, \ldots, n\}\). Let \(\mathcal{A}\) = all \(k\)-element subsets of \(S\). Let \(\mathcal{B}\) = all \((n-k)\)-element subsets of \(S\).
  • DefineDefine \(f : \mathcal{A} \to \mathcal{B}\) by \(f(A) = S \setminus A\) (the complement of \(A\) in \(S\)).
  • VerifyWell-defined: If \(|A| = k\), then \(|S \setminus A| = n-k\), so \(f(A) \in \mathcal{B}\). One-to-one: If \(f(A) = f(A')\), then \(S \setminus A = S \setminus A'\), so \(A = A'\). Onto: For any \(B \in \mathcal{B}\), let \(A = S \setminus B\); then \(f(A) = B\).
  • Conclude\(f\) is a bijection, so \(|\mathcal{A}| = |\mathcal{B}|\), meaning \(\binom{n}{k} = \binom{n}{n-k}\).
Proved via an explicit complement bijection.
Example 9.6.2
Bijection between binary strings and subsets
  • ProblemProve that the number of binary strings of length \(n\) equals the number of subsets of \(\{1, 2, \ldots, n\}\).
  • RepresentLet \(\mathcal{S}\) = binary strings \(s_1 s_2 \cdots s_n\) with \(s_i \in \{0,1\}\). Let \(\mathcal{P}\) = all subsets of \(\{1, \ldots, n\}\).
  • DefineFor a binary string \(s\), define \(f(s) = \{i : s_i = 1\}\) — the subset of positions where the string has a 1.
  • VerifyWell-defined: \(f(s)\) is always a subset of \(\{1,\ldots,n\}\). One-to-one: If \(f(s) = f(t)\), the positions of 1s match, so \(s = t\). Onto: For any subset \(A\), define \(s_i = 1\) if \(i \in A\) and \(s_i = 0\) otherwise; then \(f(s) = A\).
  • InterpretThis bijection is fundamental: it explains why the formula \(2^n\) appears in both contexts. Choosing a subset and choosing a binary string are structurally identical operations.
Proved: there are exactly as many binary strings of length \(n\) as subsets of \(\{1, \ldots, n\}\), both equal to \(2^n\).
Sections 9.7 – 9.11
Pascal, Vandermonde, Hockey-Stick, and Binomial Identities
Pascal's Identity · Vandermonde · Hockey-Stick · Binomial Substitutions · Recurrence-Based Proofs
Section 9.7

Proving Pascal's Identity

Pascal's identity is \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). We proved this algebraically in Section 9.2. Now we prove it combinatorially by partitioning all \(k\)-element subsets based on whether they contain a designated element.

Example 9.7.1
Combinatorial proof of Pascal's identity
  • ProblemGive a combinatorial proof of \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) for \(n \geq 1\) and \(1 \leq k \leq n-1\).
  • RepresentLet \(S = \{1, 2, \ldots, n\}\). Count all \(k\)-element subsets of \(S\). Focus on element \(n\) and consider whether it belongs to the subset.
  • Case 1The subset contains \(n\). We must choose the remaining \(k-1\) elements from \(\{1, \ldots, n-1\}\): there are \(\binom{n-1}{k-1}\) ways.
  • Case 2The subset does not contain \(n\). We choose all \(k\) elements from \(\{1, \ldots, n-1\}\): there are \(\binom{n-1}{k}\) ways.
  • ConcludeThese two cases are disjoint (a subset either contains \(n\) or it does not) and exhaustive (every \(k\)-element subset falls into one case). By the sum rule: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\).
  • InterpretPascal's identity means: any \(k\)-element subset either includes the "new" element \(n\) or it doesn't. This is also why Pascal's Triangle is built the way it is — each entry is the sum of the two above it, because each subset is formed by including or excluding the newest element.
Proved: Pascal's identity follows from a partition of subsets by inclusion or exclusion of element \(n\).
Diagram Description — Pascal's Triangle and Pascal's Identity

In Pascal's Triangle, each entry \(\binom{n}{k}\) is the sum of the two entries directly above it: \(\binom{n-1}{k-1}\) to the upper-left and \(\binom{n-1}{k}\) to the upper-right. Draw arrows from both upper entries pointing down to the lower entry. This visualizes the recursive structure: each subset in row \(n\) comes from either including or excluding the new element relative to row \(n-1\).

Section 9.8

Vandermonde's Identity as an Introduction

Vandermonde's identity states:

\[\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}\]

It says: the number of ways to choose \(r\) objects from a combined group of \(m + n\) objects equals the sum over all ways to split the \(r\) choices between the two groups.

Example 9.8.1
Combinatorial proof of Vandermonde's identity
  • ProblemGive a combinatorial proof of Vandermonde's identity.
  • RepresentLet \(A\) be a set of \(m\) elements and \(B\) a separate set of \(n\) elements, with \(A \cap B = \emptyset\). Count \(r\)-element subsets of \(A \cup B\).
  • Count Left\(A \cup B\) has \(m + n\) elements. The number of \(r\)-element subsets is \(\binom{m+n}{r}\).
  • Count RightSuppose the \(r\)-element subset contains exactly \(k\) elements from \(A\) and \(r-k\) elements from \(B\), for \(0 \leq k \leq r\). The count is \(\binom{m}{k} \cdot \binom{n}{r-k}\). Summing over all valid \(k\): \[\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}\] (Terms where \(k > m\) or \(r-k > n\) contribute zero.)
  • ConcludeBoth expressions count \(r\)-element subsets of \(A \cup B\), so they are equal.
  • InterpretThe identity partitions a combined selection by how many items come from each group. It appears in probability when studying the hypergeometric distribution, and in generating functions as a product formula.
Proved: Vandermonde's identity follows from partitioning an \(r\)-element selection by group origin.
MGU Library Connection
  • Vandermonde's identity reappears in Probability and Statistics when studying the hypergeometric distribution
  • Chapter 11 (Generating Functions) recovers Vandermonde's identity as a product of two generating functions
  • The Combinatorial Proof Strategy Guide contains additional examples and practice problems for Vandermonde's identity
Section 9.9

Hockey-Stick Identity

The Hockey-Stick identity is:

\[\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}\]

The name comes from its shape in Pascal's Triangle. The sum of a diagonal sequence of entries (the "handle") equals the entry one step to the right and below the last handle entry (the "blade"). Together, they form an L-shape resembling a hockey stick.

Diagram Description — The Hockey-Stick Pattern

In Pascal's Triangle, locate the entry \(\binom{n+1}{k+1}\) — the "blade" of the hockey stick. Follow the diagonal upward and to the left: \(\binom{n}{k}, \binom{n-1}{k}, \ldots, \binom{k+1}{k}, \binom{k}{k}\) — these are the "handle" entries. The Hockey-Stick identity says the sum of the handle equals the blade. In a textbook diagram, draw the handle as a descending diagonal and the blade as a single entry to the right at the bottom, with an arrow indicating the equality.

Example 9.9.1
Combinatorial proof of the Hockey-Stick identity
  • ProblemProve that \(\displaystyle\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}\).
  • ThinkThe right side counts \((k+1)\)-element subsets of \(\{1, 2, \ldots, n+1\}\). Find a partition of these subsets that produces the left side.
  • RepresentGroup \((k+1)\)-element subsets of \(\{1, \ldots, n+1\}\) by their largest element.
  • AnalyzeThe largest element must be at least \(k+1\) and at most \(n+1\). If the largest element is \(i+1\) (for \(i\) from \(k\) to \(n\)), the remaining \(k\) elements must be chosen from \(\{1, \ldots, i\}\): \(\binom{i}{k}\) choices. These cases are disjoint and exhaustive: \[\binom{n+1}{k+1} = \sum_{i=k}^{n} \binom{i}{k}\]
  • CheckFor \(k=1, n=4\): Left side = \(\binom{1}{1}+\binom{2}{1}+\binom{3}{1}+\binom{4}{1} = 1+2+3+4 = 10\). Right side = \(\binom{5}{2} = 10\). ✓
  • InterpretThe Hockey-Stick identity counts the same collection of subsets in two ways: by total count, and by grouping according to the maximum element.
Proved: the Hockey-Stick identity follows from partitioning subsets by their largest element.
Section 9.10

Identities from Binomial Expansion

The Binomial Theorem states:

\[(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k\]

By substituting specific values for \(x\) and \(y\), we can derive a wide variety of identities. This is a powerful algebraic technique: the Binomial Theorem becomes a machine for generating equations about binomial coefficients.

Example 9.10.1
Deriving the row sum identity
  • ProblemDerive \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\) from the Binomial Theorem.
  • AnalyzeSet \(x = y = 1\): \[(1+1)^n = \sum_{k=0}^{n}\binom{n}{k}\cdot 1^{n-k}\cdot 1^k = \sum_{k=0}^{n}\binom{n}{k}\] So \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\).
Setting \(x = y = 1\) in the Binomial Theorem immediately yields the row sum identity.
Example 9.10.2
Deriving the alternating sum identity
  • ProblemProve that \(\displaystyle\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n} = 0\) for \(n \geq 1\).
  • AnalyzeSet \(x = 1, y = -1\): \[(1+(-1))^n = \sum_{k=0}^{n}\binom{n}{k}(-1)^k\] For \(n \geq 1\), \(0^n = 0\), so \(\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0\).
  • InterpretFor a set of \(n \geq 1\) elements, the number of subsets of even size equals the number of subsets of odd size. The positive and negative terms cancel exactly.
Setting \(x = 1, y = -1\) gives the alternating sum identity; even-size and odd-size subsets are equally numerous.
Example 9.10.3
Deriving a weighted identity
  • ProblemProve that \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n\).
  • AnalyzeSet \(x = 1, y = 2\): \[(1+2)^n = \sum_{k=0}^{n}\binom{n}{k}\cdot 1^{n-k}\cdot 2^k = \sum_{k=0}^{n}\binom{n}{k}2^k\] Since \(3^n = (1+2)^n\), we have \(\sum_{k=0}^{n}\binom{n}{k}2^k = 3^n\).
  • InterpretThis identity counts three-choice decisions: for each of \(n\) elements, choose to include as type A, include as type B, or exclude. The expansion partitions these \(3^n\) outcomes by how many type-B inclusions occur.
Setting \(x = 1, y = 2\): \(\sum_{k=0}^{n}\binom{n}{k}2^k = 3^n\).
Section 9.11

Recurrence-Based Proofs

A recurrence-based proof verifies or derives a counting identity by using the recursive structure of the quantities involved. The key steps are: identify the recursive structure; verify base cases; show that the recurrence together with the base cases forces the identity to hold. This approach is closely connected to mathematical induction.

Example 9.11.1
Proving the row sum by recurrence and induction
  • ProblemUse Pascal's identity and induction to prove \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\).
  • Base CaseFor \(n = 0\): \(\binom{0}{0} = 1 = 2^0\). ✓
  • Inductive StepAssume \(\sum_{k=0}^{n-1}\binom{n-1}{k} = 2^{n-1}\). Apply Pascal's identity to each interior term: \[\sum_{k=0}^{n}\binom{n}{k} = \sum_{k=0}^{n}\binom{n-1}{k-1} + \sum_{k=0}^{n}\binom{n-1}{k}\] Each sum on the right equals \(2^{n-1}\) by the inductive hypothesis (boundary terms with negative or out-of-range indices are zero by convention), so: \[\sum_{k=0}^{n}\binom{n}{k} = 2^{n-1} + 2^{n-1} = 2^n\]
  • ConcludeBy induction, \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\) for all \(n \geq 0\).
Proved by induction, using Pascal's identity to reduce row \(n\) to row \(n-1\).
Example 9.11.2
Telescoping proof of the Hockey-Stick identity
  • ProblemProve \(\displaystyle\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}\) using a telescoping argument based on Pascal's identity.
  • ThinkPascal's identity gives \(\binom{i+1}{k+1} - \binom{i}{k+1} = \binom{i}{k}\). This means the Hockey-Stick sum telescopes.
  • Analyze \[\sum_{i=k}^{n}\binom{i}{k} = \sum_{i=k}^{n}\left[\binom{i+1}{k+1} - \binom{i}{k+1}\right]\] This is a telescoping sum — most terms cancel — leaving: \[= \binom{n+1}{k+1} - \binom{k}{k+1} = \binom{n+1}{k+1} - 0 = \binom{n+1}{k+1}\] (Using \(\binom{k}{k+1} = 0\) since \(k+1 > k\).)
  • ConcludeThe Hockey-Stick identity follows from a telescoping argument based on Pascal's identity.
Proved by telescoping: \(\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}\).
Sections 9.12 – 9.14
Writing Arguments, Common Mistakes, and Looking Ahead
Complete Proof Structure · Eight Common Errors · Bridge to Recurrence Relations
Section 9.12

Writing Clear Combinatorial Arguments

A combinatorial proof should be written so that a careful reader can follow every step. Here are the essential components.

Components of a Complete Combinatorial Argument

State the identity. Write it clearly at the start. Define any notation that may be unfamiliar.

Identify the set. Say explicitly what you are counting — subsets? paths? ordered pairs? The set should be described in plain language before any formula is used.

Count from both sides independently. Do not let the two explanations blur together. Each count stands on its own.

State your cases clearly. If the argument involves cases, state them explicitly. Verify that cases are disjoint and exhaustive.

Check with small values. Verify the identity holds numerically for \(n = 2, 3, 4\). This does not prove the identity but catches proof errors.

Conclude clearly. End with: "Because both sides count [the set], and each count is correct, the two expressions must be equal."

Example 9.12.1
A complete combinatorial proof
  • ProblemProve that \(\binom{n}{2} = \binom{n-1}{2} + (n-1)\) for all \(n \geq 2\).
  • SetLet \(S = \{1, 2, \ldots, n\}\). Count all 2-element subsets of \(S\). The left side counts these directly: \(\binom{n}{2}\).
  • Case 1\(n\) is in the subset. The other element is chosen from \(\{1, \ldots, n-1\}\): there are \(n-1\) choices.
  • Case 2\(n\) is not in the subset. Both elements come from \(\{1, \ldots, n-1\}\): there are \(\binom{n-1}{2}\) subsets.
  • ConcludeCases are disjoint and exhaustive. By the sum rule: \(\binom{n}{2} = (n-1) + \binom{n-1}{2}\).
  • CheckFor \(n = 5\): \(\binom{5}{2} = 10\) and \(\binom{4}{2} + 4 = 6 + 4 = 10\). ✓
Proved: \(\binom{n}{2} = \binom{n-1}{2} + (n-1)\) by partitioning 2-element subsets on whether they contain the element \(n\).
Section 9.13

Common Combinatorial Proof Mistakes

Mistake 1 — Verifying Instead of Proving
Checked n = 1, 2, 3, 4, therefore true for all n.

Checking finitely many cases does not prove an identity for all \(n\). A proof requires an argument that works in general. Use numerical checks to catch errors in reasoning, not to replace reasoning.

Mistake 2 — Describing the Set Vaguely
"Both sides count arrangements of elements."

This is not specific enough. You must say exactly what is being counted: subsets of what size? Ordered pairs between what sets? Functions from what domain? The set must be clearly defined.

Mistake 3 — Confusing the Two Counts
Writing one explanation and implicitly applying it to both sides.

In a combinatorial proof, each side must be explained independently. Write the left-side count, stop, then write the right-side count as a separate argument. They must be distinguishable.

Mistake 4 — Not Checking Cases Are Disjoint and Exhaustive
Dividing into cases without verifying no object falls into two cases or zero cases.

Cases must be mutually exclusive (no object is in two cases) and collectively exhaustive (every object is in some case). Without both properties, the sum rule cannot be applied.

Mistake 5 — Applying the Binomial Theorem Without Stating x and y
Writing a sum identity without specifying which values were substituted.

State explicitly what values you are using for \(x\) and \(y\) in the Binomial Theorem and why. Do not simply write a sum and claim it follows from the theorem.

Mistake 6 — Assuming a Bijection Without Verifying It
Defining a function f and declaring "f is clearly a bijection."

You must verify that \(f\) is one-to-one (no two inputs give the same output) and onto (every output is achieved). Both properties must be checked separately and explicitly.

Mistake 7 — Mixing Both Sides in an Algebraic Proof
Starting in the middle of an equation and working outward in both directions simultaneously.

An algebraic proof should start from one side and arrive at the other. Choose the more complicated side and transform it step by step into the simpler side.

Mistake 8 — Assuming a General Identity Is Obvious from Special Cases
"It's clear for k = 0 and k = n, so it must be true in general."

Clarity in special or boundary cases does not imply truth in the general case. What is obvious for \(k = 0\) or \(k = n\) often requires genuine argument for arbitrary \(k\).

Section 9.14

Preparing for Recurrence Relations

This chapter focused on identities: equations that hold in general and must be proved rather than just checked. In Chapter 10, we shift to a related but different kind of structure: recurrence relations, which define sequences by expressing each term in terms of earlier terms.

The connection is close. Pascal's identity, \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\), is both an identity and a recurrence: it shows how each binomial coefficient is built from the previous row. In Chapter 10, we will study recurrences as standalone objects — not just tools for proving identities, but models for counting problems whose structure builds from smaller cases.

Many of the ideas you practiced here carry forward: double counting connects to finding two formulas for the same sequence; algebraic manipulation connects to solving recurrences in closed form; bijective reasoning connects to understanding when two recurrences count the same structure; and clear case structure connects to defining the recursive step correctly.

Before moving to Chapter 10, make sure you can write a complete combinatorial proof from start to finish: identify the set, count from both sides, check that any cases are disjoint and exhaustive, and conclude clearly.

MGU Library Connection
  • Chapter 10 (Recurrence Relations) builds directly on the recurrence-based proof strategy from Section 9.11
  • Chapter 11 (Generating Functions) uses Vandermonde's identity and the row sum identity as working examples
  • Discrete Mathematics chapters on mathematical induction formalize the inductive proof structure used in Section 9.11
  • The Combinatorial Proof Strategy Guide (Appendix L) provides a full reference for all major proof methods from this chapter
  • Probability and Statistics chapters return to Vandermonde's identity in the context of the hypergeometric distribution
Chapter 9 — Back Matter

Chapter Summary

Key Terms Review

combinatorial identity
An equation involving counts, binomial coefficients, or sums that holds for all valid values of its variables.
algebraic proof
A proof that derives one side of an identity from the other using symbolic manipulation of factorial formulas.
combinatorial proof
A proof that explains why both sides of an identity count the same finite structure, using two independent counting methods.
double counting
A proof technique that counts the same set or collection of pairs in two different ways, then sets the two counts equal.
bijection
A function between two sets that is one-to-one (no two inputs share an output) and onto (every output is achieved).
bijective proof
A proof that two sets have equal size by constructing an explicit bijection between them.
Pascal's identity
\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). Each binomial coefficient equals the sum of two from the row above, corresponding to including or excluding a fixed element.
Vandermonde's identity
\(\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}\). Counts \(r\)-element selections from two groups by partitioning the \(r\) choices between them.
Hockey-Stick identity
\(\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}\). The sum of a diagonal in Pascal's Triangle equals the entry one step to the right and below the diagonal's end.
recurrence-based proof
A proof using the recursive structure of a formula, together with base cases and inductive steps, to verify a counting identity.

Concept Review Questions

Answer in complete sentences. These questions test understanding, not computation.

  1. What is the difference between verifying an identity and proving one? Give a concrete example of each.
  2. Describe in your own words what a combinatorial proof does. How is it different from an algebraic proof?
  3. What does it mean for two cases to be "disjoint and exhaustive"? Why do both conditions matter?
  4. In a bijective proof, what two properties must the function \(f\) satisfy? What does each property guarantee?
  5. Explain the combinatorial meaning of Pascal's identity. What does each term on the right side represent?
  6. Explain the combinatorial meaning of \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\). What does the left side count? The right side?
  7. In the double-counting proof of \(\sum k\binom{n}{k} = n \cdot 2^{n-1}\), what are the two ways of counting the same collection of pairs? Why must they give the same total?
  8. Why does substituting \(x = 1, y = -1\) into the Binomial Theorem produce an alternating sum identity?
  9. What is the Hockey-Stick identity? Describe what it looks like in Pascal's Triangle using the words "handle" and "blade."
  10. What is the key idea behind a telescoping argument in a recurrence-based proof?

Identity Practice

Compute both sides and verify numerically for the given values.

  1. Verify \(\binom{8}{3} = \binom{7}{2} + \binom{7}{3}\)
  2. Verify \(\binom{10}{4} = \binom{10}{6}\)
  3. Verify \(\sum_{k=0}^{5}\binom{5}{k} = 2^5 = 32\)
  4. Verify \(\sum_{i=2}^{5}\binom{i}{2} = \binom{6}{3}\)
  5. Verify Vandermonde's identity for \(m=3, n=2, r=3\)
  6. Verify the alternating sum for \(n = 4\): \(\sum_{k=0}^{4}(-1)^k\binom{4}{k}\)
  7. Verify \(\sum_{k=0}^{4}\binom{4}{k}2^k = 3^4\)
  8. Verify \(\sum_{k=0}^{5}k\binom{5}{k} = 5 \cdot 2^4 = 80\)

Algebraic Proof Practice

Write a complete algebraic proof for each identity. Start from the more complicated side. Use \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\).

  1. Prove \(\binom{n}{1} = n\)
  2. Prove \(k\binom{n}{k} = n\binom{n-1}{k-1}\) for \(k \geq 1\)
  3. Prove \(\binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}\) for \(0 \leq j \leq k \leq n\)
  4. Prove \(\binom{n+1}{k+1} = \frac{n+1}{k+1}\binom{n}{k}\)
  5. Prove \(\binom{2n}{2} = 2\binom{n}{2} + n^2\)

Double Counting Practice

Write a complete double-counting proof. Identify the set or pairs being counted, count in two ways, and conclude.

  1. Prove \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\) using a double-counting argument involving subsets.
  2. Prove that if a graph has \(n\) vertices and every vertex has degree \(d\), then the number of edges is \(\frac{nd}{2}\). (Count (vertex, incident edge) pairs two ways.)
  3. Prove that the number of ordered pairs \((A,B)\) with \(A \subseteq B \subseteq \{1,\ldots,n\}\) is \(3^n\). (Count by deciding the status of each element.)
  4. Explain how \(\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}\) follows from Vandermonde's identity with \(m = n\) and \(r = n\).

Bijective Proof Practice

Define the two sets explicitly, define the bijection, and verify one-to-one and onto.

  1. Prove that the number of subsets of \(\{1,\ldots,n\}\) containing element 1 equals the number not containing element 1. Construct an explicit bijection.
  2. Prove that the number of binary strings of length \(n\) with exactly \(k\) ones is \(\binom{n}{k}\). Construct a bijection between such strings and \(k\)-element subsets.
  3. Describe explicitly the bijection between ordered pairs \((A,B)\) of disjoint subsets of \(\{1,\ldots,n\}\) with \(|A|+|B| = n\) and partitions of \(\{1,\ldots,n\}\) into a labeled pair of sets.

Proof and Reasoning Problems

  1. Give a combinatorial proof of Pascal's identity using a different set or a different "special element" than element \(n\).
  2. Give a combinatorial proof that \(\binom{n}{2} = 1 + 2 + 3 + \cdots + (n-1)\) for \(n \geq 2\). (Hint: count pairs by their larger element.)
  3. Use the Binomial Theorem to prove that \(\sum_{k=0}^{n}(-1)^k\binom{n}{k}3^{n-k} = 2^n\).
  4. Give a proof of the Hockey-Stick identity using the telescoping approach from Section 9.11. Write each step clearly.
  5. Prove that the number of 3-element subsets of \(\{1,\ldots,n\}\) containing at least one element less than 4 equals \(\binom{n}{3} - \binom{n-3}{3}\) for \(n \geq 6\). Use complementary counting and give both an algebraic and a combinatorial interpretation.

Applications

  1. Tournament Scheduling. A round-robin tournament has \(n\) teams; each pair plays exactly once. Use the identity \(\binom{n}{2} = 1 + 2 + \cdots + (n-1)\) to explain how the total number of games can be counted by how many "later" teams each "earlier" team still has to play.
  2. Probability. In a group of \(n\) people, each independently attends an event with equal probability. Relate the identity \(\sum k\binom{n}{k} = n \cdot 2^{n-1}\) to the expected number of attendees by explaining what the left side counts and how dividing by \(2^n\) gives the expected value.
  3. Coding Theory. A binary code uses strings of length 8. Use the row sum identity to explain why the total \(2^8 = 256\) code words equals the sum of strings with exactly \(k\) ones for \(k = 0, 1, \ldots, 8\).
  4. Combinatorial Modeling. A committee of \(n\) members must choose a subcommittee and designate one of its members as chair. Verify that the total number of (subcommittee, chair) pairs equals \(n \cdot 2^{n-1}\) using the identity from Section 9.4.

Error Analysis

Each argument below contains an error. Identify and explain the error.

Problem 1
"We verified \(\binom{10}{3} = \binom{9}{3} + \binom{9}{2} = 84 + 36 = 120\). Since both sides are 120, the identity is proved."

What is wrong with this argument? How does it differ from a genuine proof?

Problem 2
"Both sides count subsets of size k from \(\{1,\ldots,n\}\), so they are equal." (Claimed proof of \(\binom{n}{k} = \binom{n}{n-k}\).)

What is incomplete about this argument? What is actually being compared?

Problem 3
Define \(f(A) = A \cup \{1\}\) as a bijection from subsets not containing 1 to subsets containing 1.

Why is this bijection proof flawed? Which condition is not verified?

Problem 4
"Substitute \(x = -1\) into \((x+1)^n\) to prove \(\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0\)."

What value should \(y\) be assigned in the Binomial Theorem? What is the correct substitution to make?

Problem 5
"Since \(\binom{n}{k}\) counts size-\(k\) subsets and \(\binom{n}{n-k}\) counts size-\((n-k)\) subsets, and \(k \neq n-k\) for most \(k\), these are different things, so the identity \(\binom{n}{k} = \binom{n}{n-k}\) must be false."

What is the logical error? What does the identity actually assert?

Chapter 9 Checkpoint

Chapter 9 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 9
Part A — Vocabulary and Concepts
  1. What is the difference between an algebraic proof and a combinatorial proof of an identity?
  2. What two things must you verify about a function to call it a bijection?
  3. State the Hockey-Stick identity using sigma notation. What does it look like in Pascal's Triangle?
Part B — Algebraic Proof
  1. Prove algebraically that \(\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}\). (This is Pascal's identity with shifted indices.)
  2. Use the Binomial Theorem to prove that \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}3^k = 4^n\).
Part C — Combinatorial Proof
  1. Give a combinatorial proof that \(\binom{n}{2} + n = \binom{n+1}{2}\). Identify the set, count it two ways, and conclude.
  2. Give a combinatorial proof of Vandermonde's identity for the special case \(r = 2\): \[\binom{m+n}{2} = \binom{m}{2} + mn + \binom{n}{2}\] Identify two groups and partition selections by how many elements come from each group.
Part D — Bijective Proof
  1. Let \(A\) = all subsets of \(\{1,\ldots,n\}\) containing element 1, and let \(B\) = all subsets not containing element 1. Define an explicit bijection from \(A\) to \(B\). Verify it is one-to-one and onto.
Part E — Reflection
  1. Consider the identity \(\sum_{k=0}^{n}k\binom{n}{k} = n \cdot 2^{n-1}\). Which proof method do you find most illuminating — algebraic, double counting, or recurrence? Write one paragraph explaining your reasoning. Refer to the specific method and what it reveals about the structure of the identity.

Answers may be placed in the answer key.

Looking Ahead
Chapter 10: Recurrence Relations

Chapter 9 gave you the tools to prove that counting formulas are correct by understanding what they mean. Chapter 10 shifts focus to a different kind of structure: recurrence relations — equations that define sequences by expressing each term in terms of earlier ones. Pascal's identity is the prototype: it says each binomial coefficient is built from the row above. Chapter 10 generalizes this idea to counting problems whose structure grows naturally from smaller cases. You will study first-order and second-order recurrences, arithmetic and geometric patterns, Fibonacci-type sequences, and connections to algorithms and data structures. Every proof technique from this chapter — algebraic manipulation, clear case structure, and the habit of checking by substitution — carries forward directly into the analysis of recurrences.

MGU Library Connections
  • Appendix L: Combinatorial Proof Strategy Guide — full reference for all proof methods from this chapter
  • Appendix C: Factorial and Binomial Coefficient Reference — formulas used in algebraic proofs
  • Appendix H: Binomial Theorem Reference — the algebraic foundation for Section 9.10
  • Chapter 10 (Recurrence Relations) — the natural sequel to this chapter's recurrence-based proofs
  • Chapter 11 (Generating Functions) — Vandermonde's identity and row sums reappear as product formulas
  • Discrete Mathematics chapters on mathematical induction — formalizes the induction structure of Section 9.11
  • Probability and Statistics — hypergeometric distribution connects directly to Vandermonde's identity
  • MGU Dictionary entries: combinatorial identity, bijection, double counting, Pascal's identity, Vandermonde's identity, Hockey-Stick identity