Mathematical Induction: Infinite Dominos
You want to prove something is true for all natural numbers.
There are infinitely many natural numbers. You can't check them one by one — you'd never finish.
Mathematical induction lets you prove infinitely many statements with two finite steps.
The trick: you don't prove each case individually. You prove that each case implies the next one. Then you knock over the first domino and watch the entire infinite chain fall.
This is the machinery behind most proofs involving "for all n."
The Domino Principle
Imagine an infinite line of dominos.
You want to prove they all fall. You can't push each one — there are infinitely many.
Instead, you prove two things:
- The first domino falls
- If any domino falls, the next one falls
That's enough. If domino 1 falls, then by rule 2, domino 2 falls. If domino 2 falls, domino 3 falls. If domino 3 falls, domino 4 falls. Forever.
Mathematical induction works exactly this way. Prove the base case (domino 1). Prove the inductive step (each domino knocks over the next). Conclude all dominos fall.
The Structure of Induction
To prove a statement P(n) is true for all natural numbers n ≥ 1:
Base case: Prove P(1) is true.
Inductive step: Assume P(k) is true for some arbitrary k ≥ 1. Prove that P(k+1) is true.
Conclusion: By induction, P(n) is true for all n ≥ 1.
The assumption "P(k) is true" is called the inductive hypothesis. You're not assuming the thing you're trying to prove — you're assuming it for one specific case to prove it for the next case.
Example: Sum of First n Natural Numbers
Claim: 1 + 2 + 3 + ... + n = n(n+1)/2 for all n ≥ 1.
Base case (n=1): Left side: 1 Right side: 1(1+1)/2 = 1(2)/2 = 1 They match. Base case holds.
Inductive step: Assume the formula holds for n = k: 1 + 2 + 3 + ... + k = k(k+1)/2
Now prove it holds for n = k+1: 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2
Start with the left side: 1 + 2 + 3 + ... + k + (k+1)
By the inductive hypothesis, the first k terms sum to k(k+1)/2: = k(k+1)/2 + (k+1)
Factor out (k+1): = (k+1)(k/2 + 1) = (k+1)(k/2 + 2/2) = (k+1)(k+2)/2
That's the right side. The formula holds for n = k+1.
Conclusion: By induction, the formula holds for all n ≥ 1.
Why This Works
The base case anchors the proof. Without it, you have no starting point.
The inductive step creates the chain. It proves that truth propagates from each case to the next.
Together, they cover all natural numbers. Base case handles n=1. Inductive step guarantees if it works for 1, it works for 2. If it works for 2, it works for 3. And so on forever.
You've proven infinitely many statements with two finite steps.
Example: Sum of Powers of 2
Claim: 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1) - 1 for all n ≥ 0.
Base case (n=0): Left side: 2^0 = 1 Right side: 2^(0+1) - 1 = 2^1 - 1 = 2 - 1 = 1 Base case holds.
Inductive step: Assume the formula holds for n = k: 2^0 + 2^1 + ... + 2^k = 2^(k+1) - 1
Prove it for n = k+1: 2^0 + 2^1 + ... + 2^k + 2^(k+1) = 2^(k+2) - 1
Start with the left side: 2^0 + 2^1 + ... + 2^k + 2^(k+1)
By the inductive hypothesis: = [2^(k+1) - 1] + 2^(k+1) = 2 · 2^(k+1) - 1 = 2^(k+2) - 1
That's the right side. The formula holds for n = k+1.
Conclusion: By induction, the formula holds for all n ≥ 0.
The Inductive Hypothesis Isn't Circular
Students sometimes worry: "Aren't we assuming what we're trying to prove?"
No. We're proving a universal statement: "For all n, P(n) is true."
The inductive step proves a conditional: "If P(k) is true, then P(k+1) is true."
You're not assuming P(k) is true for all k. You're assuming it for one arbitrary k to prove it for k+1.
The base case then triggers the chain. P(1) is true (proved directly). By the inductive step, P(2) is true. By the inductive step again, P(3) is true. Forever.
Strong Induction
Sometimes proving P(k+1) requires more than just P(k). You need P(1), P(2), ..., P(k) — all previous cases.
Strong induction allows this.
Inductive step (strong version): Assume P(1), P(2), ..., P(k) are all true. Prove P(k+1) is true.
The conclusion is the same: P(n) is true for all n.
Strong induction isn't actually stronger — it's equivalent to regular induction. But it's more convenient for certain proofs.
Example: Fibonacci Induction
The Fibonacci sequence: F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) for n ≥ 3.
Claim: F(n) < 2^n for all n ≥ 1.
Base cases (n=1 and n=2): F(1) = 1 < 2^1 = 2 ✓ F(2) = 1 < 2^2 = 4 ✓
(We need two base cases because the recurrence relation uses two previous terms.)
Inductive step: Assume F(k) < 2^k and F(k-1) < 2^(k-1) for some k ≥ 2. Prove F(k+1) < 2^(k+1).
By the recurrence relation: F(k+1) = F(k) + F(k-1)
By the inductive hypothesis: < 2^k + 2^(k-1)
Factor: = 2^(k-1)(2 + 1) = 3 · 2^(k-1) < 4 · 2^(k-1) = 2^2 · 2^(k-1) = 2^(k+1)
So F(k+1) < 2^(k+1). The inequality holds for k+1.
Conclusion: By strong induction, F(n) < 2^n for all n ≥ 1.
Structural Induction
Induction isn't just for natural numbers. It works on any well-ordered structure.
Structural induction proves properties of recursively defined objects: lists, trees, expressions, programs.
The pattern:
- Base case: prove the property for the simplest structures
- Inductive step: assume the property for smaller structures, prove it for larger structures built from them
Example: prove every binary tree with n nodes has n+1 null pointers.
Base case: A tree with 0 nodes (empty tree) has 1 null pointer. 0+1 = 1 ✓
Inductive step: Assume the claim holds for all trees with fewer than k nodes. Consider a tree with k nodes — it has a root and two subtrees (left and right). Suppose the left subtree has m nodes and the right has k-1-m nodes (the -1 accounts for the root).
By the inductive hypothesis:
- Left subtree has m+1 null pointers
- Right subtree has (k-1-m)+1 = k-m null pointers
Total null pointers in the tree: (m+1) + (k-m) = k+1 ✓
The claim holds for k nodes.
Conclusion: By structural induction, every binary tree with n nodes has n+1 null pointers.
Common Mistakes
Forgetting the base case. Without the base case, the inductive step proves nothing. You've shown the dominos are spaced correctly, but you never proved the first one falls.
Assuming too much in the inductive hypothesis. You can assume P(k) (or P(1) through P(k) in strong induction). You can't assume P(k+1) — that's what you're trying to prove.
Not using the inductive hypothesis. If your proof of P(k+1) doesn't reference P(k), you're not doing induction. You're doing a direct proof.
Proving the wrong direction. You need to prove "If P(k), then P(k+1)" — not "If P(k+1), then P(k)."
Why Induction Works
Induction works because the natural numbers are well-ordered: every non-empty set of natural numbers has a smallest element.
Suppose P(n) is false for some n. Then there's a smallest n for which P(n) is false. Call it m.
Since m is the smallest counterexample, P(m-1) is true (assuming m > 1; if m = 1, the base case is false).
But the inductive step says "If P(m-1), then P(m)." So P(m) must be true.
Contradiction. There's no smallest counterexample. Therefore, there are no counterexamples. P(n) is true for all n.
This is the foundation. Induction leverages the well-ordering of the natural numbers to prove universal statements.
Induction vs. Deduction
Deduction: reason from general principles to specific conclusions. "All humans are mortal. Socrates is human. Therefore, Socrates is mortal."
Induction (mathematical induction): prove a general statement by establishing a base case and a propagation rule.
(This is different from empirical induction — observing patterns in specific cases and inferring a general rule. Mathematical induction is deductive, not empirical.)
When to Use Induction
Use induction when:
- The statement involves "for all n" where n is a natural number
- The structure is recursively defined
- Proving the (n+1) case from the n case seems feasible
Don't force induction if a direct proof is simpler. But for statements about all natural numbers, induction is often the cleanest approach.
Induction in Computer Science
Induction is everywhere in computer science:
Loop invariants: Prove that a property holds before the loop, is maintained by each iteration, and implies correctness after the loop terminates.
Recursive algorithms: Prove correctness by induction on the size of the input. Base case: the algorithm works for the smallest input. Inductive step: if it works for smaller inputs, it works for larger inputs.
Data structure properties: Prove properties of recursively defined structures (trees, lists) by structural induction.
Induction is the formal bridge between "this works for small cases" and "this works for all cases."
The Power of the Inductive Step
The magic is in the inductive step.
You don't need to verify the statement for n=1, n=2, n=3, n=4, ... individually. You prove a single conditional: "If it works for k, it works for k+1."
That conditional, combined with the base case, covers infinity.
This is the power of abstraction. You've reduced an infinite problem to two finite steps. The first domino falls. Each domino knocks over the next. The rest is inevitable.
Induction as a Proof Technique
Induction sits alongside other proof techniques:
- Direct proof: Assume premises, derive conclusion
- Proof by contradiction: Assume negation of conclusion, derive contradiction
- Proof by contrapositive: Prove "If ¬Q, then ¬P" instead of "If P, then Q"
- Proof by cases: Split into exhaustive cases, prove each one
- Proof by induction: Establish base case and inductive step
Each technique has its domain. Induction shines when the statement is about all natural numbers or recursively defined structures.
Variations on Induction
Starting from a different base: Not all inductive proofs start at n=1. You might start at n=0, or n=5, or n=100. The structure is the same — establish the base case, prove the inductive step, conclude the statement holds for all n ≥ base.
Backwards induction: Sometimes you prove statements going downwards. Establish P(N) for some large N, then prove "If P(k+1), then P(k)." Conclude P(n) holds for all n ≤ N. Less common, but occasionally useful.
Transfinite induction: Induction extends beyond natural numbers to ordinal numbers (infinite ordinals). The structure remains: base case, inductive step, conclusion. But the base cases and inductive steps become more intricate.
The Metaphor Breaks Down
The domino metaphor is useful, but it's not perfect.
Real dominos fall because of physics — momentum, gravity. The inductive step isn't a physical mechanism. It's a logical implication.
Real dominos fall over time. Induction is timeless — all cases are proven simultaneously, not sequentially.
Real domino chains can have gaps. Induction can't — the inductive step must hold for every k, without exception.
The metaphor helps intuition. But the logic is what matters.
Why This Matters
Mathematical induction is the workhorse of discrete mathematics.
Want to prove a formula works for all n? Induction.
Want to prove an algorithm terminates? Induction on the input size.
Want to prove a recursive data structure maintains a property? Structural induction.
Want to prove a claim about all integers, all sequences, all trees? Some form of induction.
Induction turns infinity into two finite steps. Master it, and you can prove things about all natural numbers without checking each one individually.
That's the magic: you prove an infinite statement with finite reasoning.
Part 11 of the Logic series.
Previous: Methods of Proof: Direct Contradiction Induction Next: Synthesis: Logic as the Foundation of Mathematical Reasoning
Comments ()