Lesson 8: 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:

1. The statement holds for some specific k (Basis Step says k = 1 works).
2. The statement holding for k forces it to hold for k+1 (Inductive Step).
3. 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.