Mathematical Induction
“Induction is the trick of toppling infinite dominoes with just two checks.”
The formula
[ P(1) ∧ ( P(k) ⟹ P(k+1) ) ] ⟹ ∀n ≥ 1, P(n)How to read it: if the first case is true and each case being true forces the next, then the statement is true for every natural number
- P(n)
- — the statement to prove for a natural number n
- P(1)
- — the base case—knock over the first domino
- P(k) ⟹ P(k+1)
- — the inductive step—each domino knocks the next
- ∀n ≥ 1
- — therefore it holds for all natural numbers
The hook
Prove infinitely many cases in just two lines—knock over the first domino, show each domino topples the next, and you're done.
In plain words
Mathematical induction proves statements true 'for every natural number n'. (1) Show it holds at n=1 (the base), and (2) show that if it holds at n=k it must hold at n=k+1 (the step); like dominoes, they all fall.
The intuition
Imagine an endless line of dominoes. You can't topple each one by hand. But you only need to check two things—the first one falls, and 'whenever any domino falls, its neighbor falls too'. Then the first topples the second, the second the third… on forever, so all fall. Infinity is conquered by two finite checks.
How it's built
Two parts—the base case and the inductive step. The base directly checks that the starting point (usually n=1) holds. The step uses the inductive hypothesis 'P(k) is true' to derive P(k+1). You need both: without the first domino nothing falls, and without the chain only one falls.
Example
Prove 1+2+⋯+n = n(n+1)/2. Base n=1: the left side is 1 = 1·2/2 = 1 ✓. Step: assume 1+⋯+k = k(k+1)/2, then 1+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, which matches the formula at n=k+1 ✓. So it holds for all n.
Common mistake
The inductive hypothesis 'assume P(k) is true' looks like circular reasoning—assuming what you want to prove—but it isn't. You are not claiming P(k) is actually true; you are only proving the conditional link 'if it's true, so is the next' (the gap between dominoes).
Where it's used
Proving sum and inequality formulas, verifying algorithm correctness (recursion and loops), proving the correctness of data structures and compilers, countless theorems in number theory and combinatorics—it's everywhere infinite cases appear in mathematics and computer science.
Where it came from
Pascal used it explicitly in the 1600s while working with Pascal's triangle, and in the 1800s Peano built it into the axioms of the natural numbers, making it a pillar of logic.
Prerequisites
Quick check
Besides the base case, what must you prove in mathematical induction?
- that if P(k) is true then P(k+1) is true✓
- that P(n) is true for one large n
- that P(n) is never false
- nothing more is needed
Practice
Use the formula 1+2+⋯+n = n(n+1)/2 to compute 1+2+⋯+10.
Answer: 55
- substitute n=10: 10·11/2
- = 110/2 = 55
Takeaway: Once induction proves a formula, you just substitute.
Compute 1+2+⋯+100.
Answer: 5050
- 100·101/2
- = 10100/2 = 5050
Takeaway: The very sum young Gauss reportedly cracked in seconds.
The sum of the first n odd numbers is 1+3+5+⋯+(2n−1) = n². Find its value for n=5.
Answer: 25
- 1+3+5+7+9 = 25
- = 5² = 25
Takeaway: The odd numbers sum to a perfect square—a classic induction example.
Prove 1+2+⋯+n = n(n+1)/2 by induction (write the base and inductive steps).
Answer: undefined
- base n=1: 1 = 1·2/2 = 1 ✓
- assume: 1+⋯+k = k(k+1)/2
- add (k+1): k(k+1)/2 + (k+1) = (k+1)(k+2)/2, the formula at n=k+1 ✓
Takeaway: Base + step = a complete proof for infinitely many cases.