Why Does a Recursive Construction Work for Every Size?
In Chapter 1, we used invariants like parity and coloring to prove that certain board tilings are mathematically impossible. Now we turn to a constructive question: How can a single, finite recursive recipe generate a valid tiling for an infinite family of board sizes?
To explore this, we introduce a classic puzzle involving a basic geometric tile called an L-tromino.
The Defective Board Tiling Problem
An L-tromino is a polyomino made of 3 unit squares forming a $2 \times 2$ block with one corner square removed. Suppose we take a square board whose side length is a power of two ($2^n \times 2^n$) and remove any single square (leaving a "defective" board of area $2^{2n} - 1$). Can the remaining board always be tiled perfectly by L-trominoes without overlaps or gaps?
For the smallest non-trivial board ($2 \times 2$), removing 1 square leaves exactly 3 squares—which is already the exact shape of an L-tromino! But how do we scale this up to a $4 \times 4$, $8 \times 8$, or an arbitrarily large $2^n \times 2^n$ board?
The Divide-and-Conquer Reduction
A $4 \times 4$ board contains 16 squares. Removing 1 square leaves 15 squares to tile ($\frac{15}{3} = 5$ trominoes needed). Rather than guessing placements by trial and error, we apply a recursive divide-and-conquer strategy:
- Divide: Partition the $4 \times 4$ board into four equal $2 \times 2$ quadrants.
- Identify Defect: The original removed square lies in one of these four quadrants (making that quadrant a defective $2 \times 2$ board already).
- The Central Magic Trick: Place a single "central" L-tromino right at the intersection of the four quadrants, covering exactly one corner of each of the other three non-defective quadrants.
- Reduce: Now, every single one of the four quadrants has exactly one missing square! The problem for a $4 \times 4$ board is completely reduced to solving four independent $2 \times 2$ base-case problems.
From Recursive Construction to Mathematical Induction
Drawing a working tiling for a $4 \times 4$ or $8 \times 8$ board is an excellent demonstration, but it does not constitute a rigorous proof for every integer $n \ge 1$. To prove that this finite recipe works infinitely, we must fulfill three obligations:
- Base Case ($n=1$): Confirm that the smallest board ($2^1 \times 2^1 = 2 \times 2$) with 1 missing square can always be tiled.
- Inductive Reduction Step ($n = k-1 \implies n = k$): Prove that any $2^k \times 2^k$ board can be subdivided into four $2^{k-1} \times 2^{k-1}$ boards, and placing one central tromino reduces the task to 4 smaller valid subproblems.
- Seamless Combination: Ensure that the solutions to the four smaller boards combine without leaving overlaps or untiled gaps.
Mathematical Induction turns those obligations into an airtight proof. The recursive algorithm gives us the physical construction; the Induction Hypothesis mathematically guarantees that the smaller subproblems are guaranteed to be solvable.
Step-by-Step Execution on a $4 \times 4$ Board
Take a $4 \times 4$ board with rows and columns numbered 1 to 4, and remove square $(1,1)$ in the upper-left corner.
Split the board between rows 2 & 3 and columns 2 & 3. Its four quadrants are distinct $2 \times 2$ sub-boards.
The upper-left quadrant already contains its missing square $(1,1)$, so it is ready to be tiled by 1 tromino.
Place 1 central L-tromino on squares $(2,3)$, $(3,2)$, and $(3,3)$—one square in each of the other three intact quadrants.
Each of the 4 quadrants now has exactly 3 uncovered squares forming an L-shape. Place 1 tromino in each quadrant.
Area formula check: $\frac{16 - 1}{3} = 5$ trominoes. The math matches perfectly!
Question to Revisit as You Read Chapter 2:
Why must the Induction Hypothesis allow the missing square to be located anywhere on the board, rather than restricting it to a convenient corner square?
2.1 Weak Induction: The Domino Principle of Proof
Let $P(n)$ be a mathematical statement indexed by an integer $n$. To prove that $P(n)$ is true for every integer $n \ge n_0$, weak induction (also called ordinary induction) establishes an infinite chain of truth through two essential steps.
The Two Pillars of Ordinary Induction
- Base Case: Prove that the initial statement $P(n_0)$ is explicitly true.
- Inductive Step: For an arbitrary fixed integer $k \ge n_0$, assume $P(k)$ holds, and use this assumption to prove that $P(k+1)$ must also hold.
Understanding the Induction Hypothesis
The assumption $P(k)$ is called the induction hypothesis. We use it conditionally: if the statement holds at stage $k$, the logical argument carries it to stage $k+1$. The base case provides the initial push that sets the entire infinite domino chain in motion.
Sum of the First $n$ Positive Integers
We claim that for every integer $n \ge 1$:
Step-by-Step Proof by Weak Induction:
1. Base Case ($n = 1$)
• Left-Hand Side (LHS): $1$
• Right-Hand Side (RHS): $\frac{1(1+1)}{2} = \frac{2}{2} = 1$
LHS = RHS. The base case $P(1)$ holds!
2. Inductive Hypothesis
Assume $P(k)$ holds for an arbitrary integer $k \ge 1$:
3. Inductive Step ($P(k) \implies P(k+1)$):
We must evaluate the sum up to $k+1$. Express the sum as the previous sum plus the new $(k+1)$ term:
Factor out the common term $(k+1)$:
This matches the original formula with $n$ replaced by $k+1$. Thus $P(k+1)$ is true, completing the proof for all $n \ge 1$.
An Exponential Inequality: $2^n \ge n+1$
Induction applies equally well to inequalities. We claim that for every integer $n \ge 0$:
- Base Case ($n = 0$): $2^0 = 1$ and $0 + 1 = 1$. Since $1 \ge 1$, the base case holds.
- Inductive Hypothesis: Assume $2^k \ge k + 1$ for an arbitrary integer $k \ge 0$.
- Inductive Step: Multiply both sides of the hypothesis by $2$: $$2^{k+1} = 2 \cdot 2^k \ge 2(k + 1) = 2k + 2$$ Because $k \ge 0$, we know that $2k + 2 = (k + 2) + k \ge k + 2$. Therefore: $$2^{k+1} \ge k + 2 = (k + 1) + 1$$
Exercise: Sum of the First $n$ Positive Odd Integers
Prove by weak induction that for every integer $n \ge 1$, the sum of the first $n$ positive odd integers is equal to $n^2$:
Proof Solution Breakdown:
- Base Case ($n=1$): The first odd integer is $1$, and $1^2 = 1$. The base case holds.
- Inductive Hypothesis: Assume $1 + 3 + 5 + \cdots + (2k-1) = k^2$ for $k \ge 1$.
- Inductive Step: The $(k+1)$-th odd integer is $2(k+1) - 1 = 2k + 1$. Adding it to both sides yields: $$\underbrace{1 + 3 + \cdots + (2k-1)}_{k^2} + (2k+1) = k^2 + 2k + 1 = (k+1)^2$$
- This completes the proof that the sum of the first $n$ odd integers equals $n^2$ for all $n \ge 1$.
Core Takeaway on Weak Induction
An induction proof requires a valid base case and an unbroken step $P(k) \implies P(k+1)$ that works for every eligible $k \ge n_0$. The induction hypothesis may only be applied to inputs it actually covers; checking many individual numerical examples cannot replace this logical step.
2.2 Strong Induction: Reaching Farther Back
In strong induction (sometimes called complete induction), the inductive step is granted access to all prior cases rather than just the single immediately preceding state. To prove that a statement $P(n)$ holds for every integer $n \ge n_0$, we establish the starting base case(s) and then demonstrate that $P(n_0), P(n_0+1), \dots, P(k)$ collectively imply $P(k+1)$.
Weak vs. Strong Induction: Scope of the Hypothesis
Despite its name, strong induction does not prove "stronger" mathematical facts than weak induction—both methods establish truth across the exact same set of integers. However, strong induction provides immense practical convenience when a problem breaks down into smaller subproblems whose sizes are strictly less than $k$, but not necessarily equal to $k-1$.
Weak (Ordinary) Induction
• Hypothesis: Assumes only the immediate predecessor $P(k)$ is true.
• Ideal For: Problems where state $k+1$ builds directly on state $k$ (e.g., adding a single term to a sum, or adding one node to a path).
Strong (Complete) Induction
• Hypothesis: Assumes all preceding statements $P(n_0), P(n_0+1), \dots, P(k)$ are true.
• Ideal For: Problems that divide into smaller fragments (e.g., prime factorization $n = a \cdot b$, polygon triangulation, or stamp values).
Existence of Prime Factorization
A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. We claim that every integer $n \ge 2$ can be written as a product of one or more prime numbers.
Why Weak Induction Fails Here
Knowing that $k$ has a prime factorization tells us almost nothing about $k+1$. For instance, knowing $11$ is prime does not help factor $12 = 3 \times 4$. However, composite numbers break down into smaller factors $a$ and $b$ that are strictly less than $k+1$. Strong induction gives us coverage for all factors in the range $[2, k]$.
Step-by-Step Proof by Strong Induction:
- Base Case ($n = 2$): The number 2 is prime, so it is trivially written as a 1-factor product of primes. $P(2)$ holds.
- Strong Induction Hypothesis: Assume that every integer from $2$ up to $k$ can be written as a product of primes.
- Inductive Step (Evaluate $k+1$):
- Case A (Prime): If $k+1$ is prime, it is already a single-factor prime product.
- Case B (Composite): If $k+1$ is composite, it can be factored into a product $k+1 = a \cdot b$, where $2 \le a, b \le k$.
Because both $a$ and $b$ fall squarely within the range $[2, k]$, our Strong Induction Hypothesis applies to both factors! Therefore, $a$ and $b$ each possess prime factorizations:
Concatenating these prime factors produces a valid prime factorization for $k+1$, completing the proof for all $n \ge 2$.
Multi-Base Case Induction: The Postage Stamp Problem
Some strong-induction proofs require a step that jumps backward by $m$ units (e.g., examining $k+1-m$). In these situations, we must prove $m$ consecutive base cases before the inductive step can safely begin!
Worked Example: 4-Unit and 7-Unit Postage Stamps
Theorem: Every integer postage amount $n \ge 18$ cents can be formed using only 4-cent and 7-cent stamps.
Why 4 Base Cases Are Mandatory:
To construct amount $k+1$, we subtract 4 cents to inspect amount $(k+1)-4 = k-3$. To ensure that $k-3$ stays within our proven territory ($\ge 18$), $k+1$ must be at least $22$, meaning $k \ge 21$. Therefore, we must manually establish four consecutive base cases ($18, 19, 20, 21$) as our foundation!
$18 = 7 + 7 + 4$
$19 = 7 + 4 + 4 + 4$
$20 = 4 + 4 + 4 + 4 + 4$
$21 = 7 + 7 + 7$
Inductive Step ($k \ge 21$):
Assume every postage amount from $18$ up through $k$ can be formed. To make $k+1$ cents:
- Subtract $4$ cents to inspect amount $k-3$.
- Because $k \ge 21$, we have $18 \le k-3 \le k$. By the Strong IH, amount $k-3$ can be formed.
- Add one 4-cent stamp to the combination for $k-3$ to obtain exactly $k+1$ cents!
Practice Exercise: 5-Cent and 8-Cent Stamps
Prove that every postage amount $n \ge 28$ cents can be formed using only 5-cent and 8-cent stamps.
Solution Outline:
- Determine Base Case Count: Because we jump back by $5$ cents (subtracting $5$), we must establish 5 consecutive base cases:
- $28 = 8 + 4 \times 5$
- $29 = 3 \times 8 + 5$
- $30 = 6 \times 5$
- $31 = 2 \times 8 + 3 \times 5$
- $32 = 4 \times 8$
- Inductive Step ($k \ge 32$): To form $k+1$ cents, inspect $(k+1)-5 = k-4$. Since $28 \le k-4 \le k$, amount $k-4$ is solvable by the Strong IH. Add one 5-cent stamp to make $k+1$.
Induction Selection Guide
| Feature | Weak (Ordinary) Induction | Strong (Complete) Induction |
|---|---|---|
| Hypothesis Scope | Only immediate predecessor $P(k)$ | All prior states $P(n_0), P(n_0+1), \dots, P(k)$ |
| Required Base Cases | Usually 1 base case ($n_0$) | $m$ base cases (where $m$ is the backward step size) |
| Subproblem Size | Strictly size $k$ | Any size(s) inside $[n_0, k]$ |
| Classic Applications | Summation formulas, simple recurrence relations, line graphs | Prime factorization, polygon triangulation, stamp problems, game trees |
2.3 Structural Induction: Reasoning over Recursive Structures
While numerical induction steps linearly through integer counts ($n \to n+1$), structural induction follows the grammatical rules that build complex data structures. When a class of mathematical objects is defined recursively from atomic base elements using constructor rules, structural induction proves a property holds for all base elements and is strictly preserved by every constructor.
Numerical vs. Structural Induction
In standard numerical induction, objects are measured by a single integer parameter (such as size, length, or height). In contrast, structural induction operates directly on the inductive definition of the object itself, matching its branching shape without needing an explicit integer size function.
Numerical Induction
• Domain: Ordered integers $n \ge n_0$.
• Progression: Linear sequence ($1 \to 2 \to 3 \to \dots \to k \to k+1$).
• Mechanism: Assumes truth for size $k$ and proves size $k+1$.
Structural Induction
• Domain: Inductively defined sets (trees, lists, formulas, graphs).
• Progression: Hierarchical construction from sub-structures.
• Mechanism: Proves atomic base cases, then proves constructors preserve the invariant.
Full Ordered Binary Trees
To demonstrate structural induction, consider the class of finite full ordered binary trees defined by the following two recursive rules:
Inductive Definition of the Tree Class
- Base Object: A single leaf (a node with zero children) is a tree.
- Constructor Step: Joining a left subtree $A$ and a right subtree $B$ under a new internal node creates a valid tree.
- Exclusivity: Every tree in this class is generated by applying rules (1) and (2) a finite number of times.
"Full" Property
Every internal node has exactly two children. Internal nodes with 1 child are strictly forbidden in this class.
"Ordered" Property
Left and right child positions are distinguished. Swapping subtrees $A$ and $B$ produces a distinct tree structure.
Theorem: $L(T) = I(T) + 1$
Let $L(T)$ be the number of leaves and $I(T)$ be the number of internal nodes in a full ordered binary tree $T$. We claim that every such tree satisfies:
Step-by-Step Proof by Structural Induction:
1. Base Case (Atomic Object)
Consider the simplest possible tree $T$, consisting of a single leaf node:
- Number of leaves: $L(T) = 1$
- Number of internal nodes: $I(T) = 0$
- Relation check: $1 = 0 + 1 \implies L(T) = I(T) + 1$. Base case holds!
2. Constructor Step (Inductive Extension)
Suppose the relation holds for two arbitrary trees $A$ and $B$ (the induction hypotheses):
Now construct a new tree $T$ by joining $A$ and $B$ beneath a new internal root node. Count the total leaves and internal nodes of $T$:
- Total Leaves: $L(T) = L(A) + L(B)$ (joining subtrees creates no new leaves)
- Total Internal Nodes: $I(T) = I(A) + I(B) + 1$ (the new root adds 1 internal node)
Substitute the induction hypotheses into $L(T)$:
Rearrange terms by grouping $[I(A) + I(B) + 1]$:
The invariant $L = I + 1$ is preserved by the constructor. Therefore, it holds for all full ordered binary trees!
Parent–Child Edge Counting
Exercise: Prove $E(T) = 2 I(T)$
Prove that every full ordered binary tree with $I$ internal nodes has exactly $E = 2I$ parent–child edges.
Hint & Solution Breakdown:
- Base Object: A single leaf has $0$ internal nodes and $0$ edges ($E = 0, I = 0 \implies 0 = 2(0)$). Base case holds!
- Constructor Step: Assume $E(A) = 2I(A)$ and $E(B) = 2I(B)$. Joining $A$ and $B$ under a new root introduces exactly **2 new edges** (one to $A$, one to $B$): $$E(T) = E(A) + E(B) + 2 = 2I(A) + 2I(B) + 2 = 2[I(A) + I(B) + 1] = 2I(T)$$
- Total Vertex Corollary: Combining $E = 2I$ with $L = I + 1$, the total vertex count is $V = L + I = (I + 1) + I = 2I + 1 = E + 1$. This confirms the fundamental graph identity that every tree has $V = E + 1$ vertices.
Expression Trees & Compilers
Structural induction is the primary tool used by computer scientists to prove compiler correctness, evaluate programming syntax, and verify algebraic parsers. Mathematical expressions are parsed directly into Abstract Syntax Trees (ASTs):
- Leaves (Atomic Operands): Numbers or variables (e.g.,
3,5,x). - Internal Nodes (Binary Operators): Operations like addition, subtraction, or multiplication (e.g.,
+,-,*).
By proving that basic operations evaluate correctly and that tree constructors preserve correctness, compilers guarantee that complex nested expressions yield correct execution behavior without evaluating every infinite expression individually!
Summary: Structural Induction at a Glance
| Phase | Role in Proof | Tree Example Application |
|---|---|---|
| Grammar Rules | Defines base elements and valid constructors. | Base: Single Leaf | Constructor: Join $A$ and $B$ under Root. |
| Base Case | Verifies property on atomic elements. | Single Leaf: $L = 1, I = 0 \implies 1 = 0 + 1$. |
| Induction Hypotheses | Assumes property holds for sub-components. | Assume $L(A) = I(A) + 1$ and $L(B) = I(B) + 1$. |
| Constructor Step | Proves constructor preserves the invariant. | $L(T) = L(A) + L(B) = [I(A)+1] + [I(B)+1] = I(T) + 1$. |
2.4 Recursive Definitions and Recursive Constructions
In computer science and combinatorics, we often define objects and algorithms not by describing their complete static structure all at once, but by specifying how to build larger instances from smaller ones. A recursive definition specifies base elements and rules for constructing larger objects, while a recursive construction turns those rules into an executable step-by-step procedure.
The Three Golden Rules of Recursive Design
To ensure that a recursive definition or algorithm is mathematically sound and does not loop infinitely or produce ambiguous outputs, every valid recursive system must answer three fundamental questions:
1. Termination
What stops the recursion?
There must be well-defined base cases that can be solved directly without making further recursive calls.
2. Progress
What makes each call smaller?
Every recursive step must reduce a measured input size ($k \to k-1$ or $N \to N/2$), strictly moving closer to a base case.
3. Correctness
Why do returned pieces solve it?
An inductive combination step must guarantee that correctly solved smaller pieces assemble seamlessly into a valid global solution.
Recursive Generation of All Binary Strings
How do we construct the set $B(n)$ of all binary strings of length $n$ using recursion?
Recursive Definition of $B(n)$
- Base Case ($n = 0$): $B(0) = \{\varepsilon\}$, containing only the empty string $\varepsilon$ (a valid string of length zero).
- Recursive Step ($n+1$): To construct $B(n+1)$, take every string $s \in B(n)$ and create two new strings by prefixing $s$ with
0and with1: $$B(n+1) = \{ \mathtt{0}s \mid s \in B(n) \} \cup \{ \mathtt{1}s \mid s \in B(n) \}$$
Evaluating the first few iterations demonstrates exponential set growth:
- $B(0) = \{\varepsilon\}$ (1 string of length 0)
- $B(1) = \{\mathtt{0}, \mathtt{1}\}$ (2 strings of length 1)
- $B(2) = \{\mathtt{00}, \mathtt{01}, \mathtt{10}, \mathtt{11}\}$ (4 strings of length 2)
- $B(3) = \{\mathtt{000}, \mathtt{001}, \mathtt{010}, \mathtt{011}, \mathtt{100}, \mathtt{101}, \mathtt{110}, \mathtt{111}\}$ (8 strings of length 3)
Proof of Correctness (Exhaustive & Duplicate-Free):
This construction is exhaustive because every non-empty binary string has a unique first digit (0 or 1) followed by a shorter suffix in $B(n)$. It introduces no duplicates because strings starting with 0 and 1 belong to disjoint sets, and stripping the first digit recovers a unique shorter suffix. By weak induction, $B(n)$ generates every length-$n$ binary string exactly once, giving total count $|B(n)| = 2^n$.
Numerical Recurrence: Domino Tiling Counts
Recursive definitions apply to sequence calculations as well as set generation. Recall the 2-by-$n$ domino tiling problem from Chapter 1, where the number of valid tilings $T(n)$ satisfies the famous linear recurrence relation:
The Defective Board Tromino Construction, Fully Justified
Let $P(k)$ represent the formal statement: "Every $2^k \times 2^k$ board missing any single square can be completely tiled by L-trominoes." We establish $P(k)$ for all $k \ge 1$ using our three recursive questions:
Step-by-Step Proof of the Tromino Algorithm
- Base Case ($k = 1$): A $2^1 \times 2^1 = 2 \times 2$ board with 1 missing square leaves 3 unit squares in an L-shape. A single L-tromino covers it perfectly.
- Inductive Reduction ($k \to k+1$): Take a $2^{k+1} \times 2^{k+1}$ board with 1 missing square. Divide the board into four equal $2^k \times 2^k$ quadrants. Exactly one quadrant contains the original missing square.
- The Central Placement: Place 1 central L-tromino right at the intersection of the four quadrants, covering the inner corner square of each of the three intact quadrants.
- Recursive Call: Now, every single one of the four $2^k \times 2^k$ quadrants has exactly one unavailable square (either the original hole or a central tromino tile).
- Unwinding & Assembly: By the Induction Hypothesis $P(k)$, each of the four $2^k \times 2^k$ subproblems can be tiled independently. Because the four quadrants are mutually disjoint and do not overlap the central tromino, combining their solutions tiles the entire $2^{k+1} \times 2^{k+1}$ board perfectly!
Exercise: The Hypothesis Strengthening Principle
Question: Why is an induction hypothesis that claims tiling is possible only for corner holes too narrow for this proof?
The Flaw in Too Narrow a Hypothesis
If we restrict $P(k)$ to mean "boards with a hole in the corner can be tiled," the recursive step breaks! When we partition a $2^{k+1} \times 2^{k+1}$ board, the original missing square in its quadrant might be located near the center or an interior edge of that quadrant—not at its corner. The inductive step would fail because $P(k)$ would not apply to that quadrant!
The Solution: Generalizing the Hypothesis
By strengthening $P(k)$ to state that a tiling exists for a missing square located anywhere on the board, we ensure that every quadrant subproblem—no matter where its defect sits—is fully covered by the hypothesis.
Recursion Concepts at a Glance
| Concept | Primary Purpose | Worked Example |
|---|---|---|
| Recursive Definition | Specifies base elements and constructors to define a set or sequence. | Binary strings $B(n+1) = \{0s\} \cup \{1s\}$ with $B(0)=\{\varepsilon\}$. |
| Recursive Construction | An algorithmic process that generates physical instances of an object. | Subdividing a $2^k \times 2^k$ board and placing 1 central L-tromino. |
| Inductive Proof | Verifies that a recursive construction terminates and runs correctly. | Proving that placing central trominoes reduces tiling to $2 \times 2$ base cases. |
2.5 Well-Ordering Principle and Minimal Counterexamples
At the foundation of mathematical induction lies a fundamental axiom of the natural numbers: the Well-Ordering Principle. While induction provides a forward mechanism for propagating truth ($k \to k+1$), the Well-Ordering Principle allows us to reason backward by examining the smallest possible failing case in a proof by contradiction.
The Well-Ordering Principle (WOP)
Formal Statement of the Well-Ordering Principle
Every non-empty set of non-negative integers ($\mathbb{N}_0 = \{0, 1, 2, 3, \dots\}$) contains a least element. That is, if $S \subseteq \mathbb{N}_0$ and $S \neq \emptyset$, then there exists an element $m \in S$ such that $m \le x$ for all $x \in S$.
This principle applies to both finite and infinite subsets of non-negative integers. For example, the infinite set of positive multiples of seven, $S = \{7, 14, 21, 28, \dots\}$, is non-empty and has the clear minimal element $m = 7$.
The Method of Minimal Counterexamples
The Method of Minimal Counterexample converts the Well-Ordering Principle into a powerful proof strategy by contradiction. To prove that a statement $P(n)$ is true for all integers $n \ge n_0$:
- Assume Falsehood: Assume for the sake of contradiction that $P(n)$ fails for at least one integer $n \ge n_0$.
- Construct Failure Set: Define the set of counterexamples $F = \{ x \in \mathbb{N}_0 \mid x \ge n_0 \text{ and } P(x) \text{ is FALSE} \}$. By assumption, $F$ is non-empty.
- Select Minimal Element: By the Well-Ordering Principle, $F$ must contain a smallest element $m = \min(F)$.
- Exploit Minimality: Because $m$ is the absolute smallest counterexample, every smaller eligible instance $k < m$ must satisfy $P(k)$!
- Derive Contradiction: Use the validity of smaller cases $P(k)$ to show that $P(m)$ must actually be true after all, contradicting $m \in F$. Thus, $F = \emptyset$ and $P(n)$ holds for all $n$.
Applying WOP & Minimal Counterexamples
Worked Proof 1: Prime Factorization Revisited
Theorem: Every integer $n \ge 2$ can be written as a product of prime numbers.
Proof by Minimal Counterexample:
- Suppose the theorem is false. Let $S$ be the set of integers $n \ge 2$ that have no prime factorization. By assumption, $S \neq \emptyset$.
- By the Well-Ordering Principle, $S$ contains a smallest element $m = \min(S)$.
- The integer $m$ cannot be prime, because a single prime $m$ is its own 1-factor prime product (which would mean $m \notin S$).
- Therefore, $m$ must be composite, meaning $m = a \cdot b$ for integers $a, b$ satisfying $2 \le a, b \le m-1$.
- Because $a < m$ and $b < m$, neither $a$ nor $b$ can belong to the failure set $S$ (since $m$ is the absolute smallest element in $S$).
- Thus, $a$ and $b$ both possess valid prime factorizations. Concatenating their prime factors produces a prime factorization for $m = a \cdot b$.
- This contradicts $m \in S$! Hence, no counterexample $m$ can exist, and $S = \emptyset$. $\blacksquare$
Notice that this minimal counterexample argument uses the exact same core logic as strong induction: assuming that all smaller integers possess prime factorizations allows us to handle composite numbers seamlessly.
Worked Proof 2: Why Ordinary Induction Works (WOP Foundation)
Why are we mathematically guaranteed that ordinary weak induction is sound? We can prove weak induction itself using the Well-Ordering Principle!
Proof:
- Suppose we established the Base Case $P(n_0)$ and the Inductive Step $P(k) \implies P(k+1)$ for all $k \ge n_0$, but $P(n)$ still fails for some $n$.
- Let $F = \{ x \ge n_0 \mid P(x) \text{ is FALSE} \}$ be the non-empty set of failures.
- By WOP, choose the smallest failing index $m = \min(F)$.
- Because the base case $P(n_0)$ was proven true, $m$ cannot equal $n_0$. Thus, $m > n_0$, which means $m - 1 \ge n_0$.
- By minimality of $m$, the predecessor $m - 1$ is not in $F$, so $P(m-1)$ is TRUE!
- Applying the established inductive step $P(m-1) \implies P(m)$ forces $P(m)$ to be TRUE.
- This contradicts $m \in F$. Therefore, no failing index $m$ can exist, proving weak induction is logically sound! $\blacksquare$
Exercise: Termination of Strictly Decreasing Sequences
Suppose a recursive procedure takes a positive integer $n$ and replaces it with a strictly smaller positive integer whenever it continues. Why is it mathematically impossible for this process to run forever?
Proof Solution via Well-Ordering Principle:
Suppose for contradiction that the procedure ran forever, generating an infinite strictly decreasing sequence of positive integers:
Let $V = \{ n_1, n_2, n_3, \dots \}$ be the set of all visited values. Because $V$ is a non-empty set of positive integers, the Well-Ordering Principle guarantees that $V$ must contain a least element $m \in V$.
Since $m \in V$, the procedure reaches state $m = n_k$ at some step $k$. Because the procedure continues, the next step visits $n_{k+1}$, which satisfies $n_{k+1} < n_k = m$. But $n_{k+1} \in V$, contradicting the fact that $m$ was the smallest member of $V$! Thus, the procedure must terminate in finitely many steps. $\blacksquare$
2.6 Bijections via Recursive Decompositions
In Chapter 1, we constructed bijections between combinatorial sets using static rules (such as pairing subsets with binary strings). When dealing with recursively built objects—such as trees, paths, and parenthesized expressions—we can define recursive bijections that match components level by level. Reversibility remains the ultimate gold standard: shared counts or matching recurrences alone do not establish a bijection without an explicit round-trip proof.
Balanced-Parenthesis Words
A string of opening ( and closing ) parentheses is called a balanced-parenthesis word if it satisfies two conditions:
- Equal Total Count: It contains exactly as many opening parentheses
(as closing parentheses). - Prefix Balance Condition: In every prefix (initial substring), the number of opening parentheses is greater than or equal to the number of closing parentheses ($\text{count}(\mathtt{(}) \ge \text{count}(\mathtt{)})$.
Valid Balanced Examples
- $\varepsilon$ (Empty word, 0 pairs)
()(1 pair)(())and()()(2 pairs)((())),(()()),(())(),()(()),()()()(3 pairs)
Invalid Examples
)((Prefix ")" drops balance to $-1$)(()(Unequal total counts: $2$ openings, $1$ closing)()) ((Prefix "())" drops balance to $-1$)
Unique First-Return Decomposition: (U)V
Every non-empty balanced word $w$ possesses a unique structural decomposition of the form:
How to Extract $U$ and $V$:
- Scan the word from left to right, keeping a running balance count of $\text{openings} - \text{closings}$.
- Locate the first position where the balance returns to zero. The closing parenthesis
)at this exact return matches the initial opening parenthesis(. - The enclosed sub-word between this first matched pair is $U$ (which is guaranteed to be balanced).
- The remaining suffix after this first return is $V$ (which is also guaranteed to be balanced).
Understanding First-Return: The "First Complete Block" Principle
Why is this decomposition guaranteed to be unique? Because a string can only have one first time its balance drops back to zero. Think of a balanced parenthesis string as a sequence of nested HTML/JSON blocks or function scopes:
- The very first character is always an opening
(—it opens the top-level container block. - As you scan forward, you might enter inner nested blocks (increasing the balance level).
- The moment the balance drops back to 0 for the first time, the top-level container block has officially closed. Everything inside that first block forms $U$, and any remaining code following it forms $V$.
Real-World Code Examples:
()(())
• Initial ( opens at index 0 (balance = 1).
• Next char is ) at index 1 (balance returns to 0 immediately!).
• Enclosed contents $U = \varepsilon$ (empty). Remaining suffix $V = \mathtt{(())}$.
• Result: $w = \mathtt{(}\varepsilon\mathtt{)}\mathtt{(())} \implies U = \varepsilon, V = \mathtt{(())}$.
((()))
• Initial ( opens at index 0. Balance rises to 2, then 3, then drops to 2, 1, and reaches 0 only at the very final character.
• The outer pair wraps the inner block (()).
• Enclosed contents $U = \mathtt{(())}$. Remaining suffix $V = \varepsilon$ (empty).
• Result: $w = \mathtt{(}\mathtt{(())}\mathtt{)}\varepsilon \implies U = \mathtt{(())}, V = \varepsilon$.
Encoding ($\Phi$) and Decoding ($\Psi$) Maps
We now establish a formal bijection between full ordered binary trees and balanced-parenthesis words using matching recursive maps $\Phi$ and $\Psi$.
Encoder $\Phi$: Tree $\to$ Word
- Base Case: A single leaf node maps to the empty word $\varepsilon$: $$\Phi(\text{leaf}) = \varepsilon$$
- Recursive Step: A tree $T$ with left subtree $A$ and right subtree $B$ maps to: $$\Phi(T) = \mathtt{(} \, \Phi(A) \, \mathtt{)} \, \Phi(B)$$
Decoder $\Psi$: Word $\to$ Tree
- Base Case: The empty word $\varepsilon$ maps to a single leaf node: $$\Psi(\varepsilon) = \text{leaf}$$
- Recursive Step: Decompose a non-empty word uniquely as $\mathtt{(} U \mathtt{)} V$. Construct an internal root node with: $$\text{Left Subtree } = \Psi(U), \quad \text{Right Subtree } = \Psi(V)$$
How $\Phi$ and $\Psi$ Work in Practice
The encoder map $\Phi$ converts a hierarchical tree into a flat string of parentheses by traversing the tree top-down. Each internal node emits a pair of parentheses wrapping its left child's code, followed by its right child's code: $\mathtt{(}\text{Left}\mathtt{)}\text{Right}$.
Step-by-Step Walkthrough: Encoding Tree $T$ into Word $w$
Consider a tree $T$ where the Root has a Left child = Leaf, and a Right child = an internal subtree with 2 Leaves.
-
Root Level: $T = (\text{Left Leaf}, \text{Right Subtree})$.
$\Phi(T) = \mathtt{(} \, \Phi(\text{Left Leaf}) \, \mathtt{)} \, \Phi(\text{Right Subtree})$. -
Left Branch Base Case: Left child is a Leaf $\implies \Phi(\text{Leaf}) = \varepsilon$.
So the left portion evaluates to $\mathtt{(} \varepsilon \mathtt{)} = \mathtt{()}$. - Right Branch Recursive Step: The Right Subtree has 2 leaves under its node $\implies \Phi(\text{Right Subtree}) = \mathtt{(}\Phi(\text{Leaf})\mathtt{)}\Phi(\text{Leaf}) = \mathtt{(}\varepsilon\mathtt{)}\varepsilon = \mathtt{()}$.
-
Combine Results: Concatenate the left and right outputs $\implies \mathtt{()} + \mathtt{()} = \mathtt{()()}$.
Final Output: The 2 internal nodes encoded perfectly into 2 balanced parenthesis pairs()()!
Proof That Maps $\Phi$ and $\Psi$ Are Inverses
To prove $\Phi$ is a bijection, we prove that both round trips recover the original object:
- Tree Round Trip ($\Psi(\Phi(T)) = T$):
Proved by structural induction on tree $T$. A leaf maps to $\varepsilon$, and $\Psi(\varepsilon) = \text{leaf}$. For an internal tree $T = (A, B)$, $\Phi(T) = \mathtt{(}\Phi(A)\mathtt{)}\Phi(B)$. First-return decomposition recovers $U = \Phi(A)$ and $V = \Phi(B)$. By induction hypothesis, $\Psi(\Phi(A)) = A$ and $\Psi(\Phi(B)) = B$, recovering $T$. - Word Round Trip ($\Phi(\Psi(w)) = w$):
Proved by strong induction on the number of parenthesis pairs $n$. The empty word $\varepsilon$ ($n=0$) maps to a leaf, and $\Phi(\text{leaf}) = \varepsilon$. For a non-empty word $w = \mathtt{(}U\mathtt{)}V$, $\Psi(w)$ creates a root with subtrees $\Psi(U)$ and $\Psi(V)$. Encoding gives $\Phi(\Psi(w)) = \mathtt{(}\Phi(\Psi(U))\mathtt{)}\Phi(\Psi(V))$. Since $U$ and $V$ have fewer pairs, strong induction yields $\Phi(\Psi(U)) = U$ and $\Phi(\Psi(V)) = V$, recovering $w$.
Exercise: Decode the Word ()(())
Apply decoder map $\Psi$ to construct the exact full ordered binary tree corresponding to $w = \mathtt{()(())}$.
• Word: ( ) ( ( ) )
• First zero balance occurs at index 2 after initial pair ().
• Left Part $U$: $\varepsilon$ | Right Part $V$: (())
• Left Subtree $\Psi(U)$: $\Psi(\varepsilon) = \text{Leaf}$.
• Right Subtree $\Psi(V)$: Decode (()) $\implies$ $U' = \mathtt{()}, V' = \varepsilon$.
• Right subtree has an internal node with 2 leaves on left, 1 leaf on right.
Final Decoded Tree Specifications:
- Root Node: Left child is a leaf ($\Psi(\varepsilon)$); Right child is an internal subtree ($\Psi(\mathtt{(())})$).
- Total Internal Nodes ($I$): $3$ internal nodes (matches $3$ parenthesis pairs!)
- Total Leaves ($L$): $L = I + 1 = 4$ leaves.
Practical Applications of Recursive Bijections
Beyond theoretical combinatorics, bijective recursive decompositions provide powerful algorithms across computer science, software engineering, and data compression:
1. Compiler Parsing & AST Generation
The decoder map $\Psi$ is the foundation of recursive-descent parsers. Compilers convert linear source code (nested parentheses or expressions) into Abstract Syntax Trees (ASTs) by continuously decomposing code along grammar rules level by level.
2. Succinct Data Structures & Tree Encoding
Standard pointer-based trees require $O(n \log n)$ bits of memory storing node pointers. The encoder $\Phi$ allows storing any $n$-node binary tree in exactly $2n$ bits (using balanced parenthesis strings), matching the theoretical minimum space bound while enabling $O(1)$ navigation via rank/select bit-vector operations.
3. Uniform Random Generation & Testing
Generating a uniform random syntax tree or valid expression directly is challenging. By establishing a bijection to Dyck paths, software engineers can sample a random balanced word in $O(n)$ time and decode it into a random tree, ensuring unbiased test-case generation for software verification.
4. XML/JSON & Hierarchical Serialization
Structured data formats like XML, JSON, and HTML rely on recursive balance rules (e.g., matching opening <tag> and closing </tag> pairs). Recursive bijections allow streaming serializers to flatten nested data structures into flat byte sequences and reconstruct them without ambiguity or extra metadata.
Deep Dive: Succinct Tree Encoding ($O(n \log n)$ vs $2n$ Bits)
In standard software implementations, a binary tree uses explicit pointers (memory addresses) for child nodes. On a 64-bit architecture, each pointer requires 64 bits ($\log n$ bits to address arbitrary memory locations). For a tree with $n$ nodes, storing two pointers per node consumes $2n \times 64$ bits—scaling as $O(n \log n)$ memory.
Information theory proves there are only $C_n = \frac{1}{n+1}\binom{2n}{n}$ distinct binary trees of size $n$ (the $n$-th Catalan number). Distinguishing any $n$-node tree theoretically requires only $\log_2(C_n) \approx 2n$ bits. A succinct data structure achieves this absolute $2n$-bit minimum using encoder map $\Phi$.
Practical Example: Encoding a 3-Node Binary Tree
Consider a tree with $n = 3$ internal nodes ($I_1, I_2, I_3$) and 4 leaves ($L$):
/ \
(L) (I₂)
/ \
(I₃) (L)
/ \
(L) (L)
- Node $I_1$ (Root): Left child is Leaf ($\varepsilon$), Right child is Subtree $I_2 \implies \Phi(I_1) = \mathtt{()} \Phi(I_2)$.
- Node $I_2$: Left child is Subtree $I_3$, Right child is Leaf ($\varepsilon$) $\implies \Phi(I_2) = \mathtt{(} \Phi(I_3) \mathtt{)}$.
- Node $I_3$: Left and Right children are Leaves ($\varepsilon$) $\implies \Phi(I_3) = \mathtt{()}$.
- Full Parenthesis Word: $\Phi(T) = \mathtt{()((()))}$
Converting to a Compact Bit-Vector:
Map opening parenthesis ( $\to$ 1 (node entry) and closing parenthesis ) $\to$ 0 (step back/leaf):
| Char | ( |
) |
( |
( |
( |
) |
) |
) |
| Bit | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
$O(1)$ Tree Navigation Without Pointers
To navigate succinct trees without decompressing them into pointers, modern systems execute $\text{rank}_1(x)$ (counts 1s up to index $x$) and $\text{select}_1(k)$ (finds index of $k$-th 1) bitwise operations. By storing small auxiliary indexing structures taking $o(n)$ extra space, hardware can calculate the left child index ($\text{select}_1(i) + 1$) or right child index in $O(1)$ constant time. This enables genome alignment (FM-Index) and search engine Tries with billions of keys to fit entirely inside CPU cache memory.
Summary: Part 2 Proof Methodologies at a Glance
| Method | Core Principle / Premise | Primary Advantage |
|---|---|---|
| Weak Induction | Step $P(k) \implies P(k+1)$ supported by Base Case $P(n_0)$. | Ideal for linear sequential progressions and summations. |
| Strong Induction | Step supported by all preceding states $P(n_0) \dots P(k)$. | Handles arbitrary fragmentation into smaller subproblems. |
| Structural Induction | Follows grammar rules generating recursive data structures. | Proves invariants across trees, lists, and compilers without integer sizes. |
| Minimal Counterexample | Well-Ordering Principle guarantees smallest failure $m = \min(F)$. | Derives clean contradictions by forcing $m$ into safe territory. |
| Recursive Bijection | Level-by-level reversible structural pairing ($\Phi \leftrightarrow \Psi$). | Establishes exact set equivalence between complex recursive classes. |
Investigation: Repairing Proofs & Constructing Bijections
Inputs & Scope
We work with positive-integer induction claims, $2 \times n$ domino tiling boards, finite full ordered binary trees, and balanced-parenthesis words. A leaf node contains zero internal nodes, and the empty word $\varepsilon$ contains zero parenthesis pairs. Left-to-right ordering is preserved throughout.
Part 1: Warm-Up Exercises
Odd Integer Sums
First 4 sums: $1, 4, 9, 16$ (suggesting $n^2$). While patterns suggest conjectures, an induction proof establishes truth for all $n \ge 1$.
4¢ & 7¢ Postage Stamps
Base combinations: $18 = 7+7+4$, $19 = 7+4+4+4$, $20 = 5 \times 4$, $21 = 3 \times 7$. Four consecutive bases support subtracting 4.
Tree Leaf Counting
A full binary tree with $I = 4$ internal nodes has $L = I + 1 = 5$ leaves, proven by structural induction.
Repair 1: Locating a Missing Dependency in Domino Tilings
The Defective Argument
"Claim: $T(1) = 1$, and $T(n) = T(n-1) + T(n-2)$ for $n \ge 2$, so all $2 \times n$ domino tiling counts follow by induction."
Diagnosis: This argument is incomplete! Evaluating the recurrence at $n = 2$ gives $T(2) = T(1) + T(0)$. However, $T(0)$ has not been defined! Without supplying $T(0)$, the inductive chain cannot evaluate its very first step at $n = 2$.
The Complete Repair:
- Set base case $T(0) = 1$ (representing the single empty tiling on a $2 \times 0$ board).
- Set base case $T(1) = 1$ (a single vertical domino on a $2 \times 1$ board).
- The recurrence $T(n) = T(n-1) + T(n-2)$ is valid for all $n \ge 2$.
Exhaustive Decomposition of the Left Edge: Consider the leftmost edge of a $2 \times n$ board. There are exactly two mutually disjoint, exhaustive ways to cover this edge:
- Place 1 Vertical Domino ($2 \times 1$): Leaves a $2 \times (n-1)$ remaining sub-board, which can be tiled in $T(n-1)$ ways.
- Place 2 Horizontal Dominoes ($2 \times 2$): Leaves a $2 \times (n-2)$ remaining sub-board, which can be tiled in $T(n-2)$ ways.
Repair 2: Identifying a Defective Inductive Step (The Token Paradox)
The False Theorem
"Proposed Theorem: Every non-empty finite set of colored tokens has only one color. Base Case ($n=1$): True. Step ($k \to k+1$): Compare the first $k$ tokens with the last $k$ tokens. Since both subsets have $k$ tokens, each subset is monochromatic. Because they overlap, all $k+1$ tokens must have the same color."
Diagnosis of Failure: Where does this "proof" break down? It fails at the transition from $k = 1$ to $k+1 = 2$!
- For $k+1 = 2$ tokens $\{t_1, t_2\}$, the first $k=1$ token is $\{t_1\}$ and the last $k=1$ token is $\{t_2\}$.
- The intersection of these two subsets is $\{t_1\} \cap \{t_2\} = \emptyset$ (the empty set!).
- Because there is no shared token in the overlap to bridge the color, knowing $\{t_1\}$ is monochromatic and $\{t_2\}$ is monochromatic tells us nothing about whether $t_1$ and $t_2$ share the same color. A set containing 1 red token and 1 blue token is a direct counterexample!
Because the proposed theorem is false, it cannot be repaired. Instead, we write a valid induction proof for the Odd-Integer Sum Identity:
Correct Proof: Sum of the First $n$ Positive Odd Integers Equals $n^2$
Theorem: For every integer $n \ge 1$, $1 + 3 + 5 + \dots + (2n - 1) = n^2$.
Proof by Weak Induction:
- Base Case ($n = 1$): The sum has 1 term: $1 = 1^2$. The base case holds.
- Inductive Hypothesis: Assume $1 + 3 + \dots + (2k - 1) = k^2$ for an arbitrary integer $k \ge 1$.
- Inductive Step: The $(k+1)$-th odd term is $2(k+1) - 1 = 2k + 1$. Add it to the hypothesis: $$\underbrace{1 + 3 + \dots + (2k - 1)}_{k^2} + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2$$ This produces the exact formula for $n = k + 1$, completing the proof for all $n \ge 1$. $\blacksquare$
Part 3: Bijection Workshop & Pseudocode
We implement the encoder map $\Phi$ and decoder map $\Psi$ as clear recursive procedures:
Encoder Pseudocode: encode(tree)
Decoder Pseudocode: decode(word)
Part 4: Counting Consequence & The 5 Catalan Trees ($n = 3$)
Let $C(n)$ count either full ordered binary trees with $n$ internal nodes or balanced words with $n$ parenthesis pairs. The recursive tree decomposition splits $n$ internal nodes into 1 root node, $i$ left internal nodes, and $n-1-i$ right internal nodes ($0 \le i \le n-1$). This establishes the fundamental Catalan Recurrence:
Evaluating the first few Catalan numbers:
- $C(0) = 1$ (1 leaf / 1 empty word $\varepsilon$)
- $C(1) = C(0)C(0) = 1 \times 1 = 1$ (1 tree / word
()) - $C(2) = C(0)C(1) + C(1)C(0) = 1 + 1 = 2$ (words
(()),()()) - $C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 2 + 1 + 2 = 5$ (5 distinct trees & words)
Optional Extension: Uniform Random Tree Sampling
Suppose you want to sample a size-$n$ tree uniformly at random from all $C(n)$ possibilities. Choosing the left-subtree size $i \in \{0, 1, \dots, n-1\}$ uniformly is mathematically incorrect! Different left-subtree split sizes contain different numbers of valid trees.
For $n = 3$, the split counts $C(i) C(n-1-i)$ across the three choices $i = 0, 1, 2$ are:
- Split $i = 0$: $C(0) C(2) = 1 \times 2 = 2$ trees
- Split $i = 1$: $C(1) C(1) = 1 \times 1 = 1$ tree
- Split $i = 2$: $C(2) C(0) = 2 \times 1 = 2$ trees
Because the total count is $2 + 1 + 2 = 5$, uniform random sampling requires selecting split $i$ according to the weighted probabilities $2/5$, $1/5$, $2/5$, followed by recursive uniform sampling within the chosen subtree classes!
Deliverables & Assessment Rubric (20 Points)
| Criteria | Point Value | Requirements & Expectations |
|---|---|---|
| Dependency & Quantifier Rigor | 4 Points | Correct starting values, valid quantifiers, and complete dependency structures established. |
| Proof Diagnosis | 4 Points | Precise identification and repair of both defective inductive arguments (domino and token). |
| Inductive Reasoning | 4 Points | Complete numerical induction (odd sums) and structural induction reasoning provided. |
| Bijection Proofs | 4 Points | Unique first-return decomposition, terminating procedures, and formal round-trip proofs ($\Psi \circ \Phi$ and $\Phi \circ \Psi$). |
| Catalan Validation | 4 Points | Correct tree/word counts, checked $n=3$ examples, and clear separation between computation and proof. |
Next in the Series
In Chapter 3: Pigeonhole Principle and Introductory Ramsey Theory, we'll explore When unavoidable repetition forces mathematical structure.