Mathematical Induction
What Is Mathematical Induction?
Mathematical induction is a proof technique used to verify that a statement P(n) is true for every natural number n.
It works on the same logic as dominos: if the first domino falls (base case), and each falling domino causes the next to fall (inductive step), then all dominos eventually fall.
The Two Steps of Mathematical Induction
Step 1 — Basis Step: Show that the statement P(1) is true (or P(0), depending on the starting value).
Step 2 — Inductive Step: Assume P(k) is true for an arbitrary natural number k (the inductive hypothesis). Then prove that P(k+1) must also be true.
Formal expression: (P(1) ∧ ∀k[P(k) → P(k+1)]) → ∀n P(n)
Why Two Steps Are Needed
Testing a few values shows a pattern, but does not prove it holds for all values. Induction provides the general argument:
- The statement holds for some specific k (Basis Step says k = 1 works).
- The statement holding for k forces it to hold for k+1 (Inductive Step).
- Therefore, it holds for all n ≥ 1.
What Mathematical Induction Can Prove
- Summation formulas (e.g., 1 + 2 + 3 + ... + n = n(n+1)/2)
- Inequalities (e.g., 2ⁿ > n for all n ≥ 1)
- Divisibility arguments (e.g., 3 | n³ + 2n)
- Properties of algorithms and graphs
Note: Mathematical induction proves existing conjectures; it is not a method for discovering new formulas.
Worked Example
Prove: 1³ + 2³ + 3³ + ... + n³ = n²(n+1)² / 4
Basis Step (n = 1): LHS = 1³ = 1 RHS = 1²(1+1)² / 4 = 1 × 4 / 4 = 1 ✓
Inductive Step: Assume P(k) is true: 1³ + 2³ + ... + k³ = k²(k+1)² / 4
Show P(k+1): 1³ + 2³ + ... + k³ + (k+1)³ = (k+1)²(k+2)² / 4
Using the inductive hypothesis: = k²(k+1)²/4 + (k+1)³ = (k+1)²[k²/4 + (k+1)] = (k+1)²[(k² + 4k + 4) / 4] = (k+1)²(k+2)² / 4 ✓
Both steps verified — the formula holds for all n.