Mathematical induction

Mathematical induction proves a statement for all n: show it is true for n = 1 (base case), and show that if it is true for k it is true for k + 1 (inductive step). Like dominoes, all then fall.

P(k) ⇒ P(k+1)Mathematical induction

📐 Formula

P(1) true and P(k) ⇒ P(k + 1) ⇒ P(n) true for all n ≥ 1

✏️ Worked example

1 + 3 + 5 + … + (2n − 1) = n²: each new odd number adds an L-shaped layer to the square. For n = 5: 25.

🌍 Where it is used

Proving formulas for sums, divisibility and algorithms.

❓ Quick check

The first step of induction is the…

🏋️ Practice

EasyCheck 1 + 2 + … + n = n(n + 1)/2 for n = 4.

Answer: 10 = 10 ✓

MediumIs 3ⁿ − 1 always even? Base case?

Answer: n = 1: 2, even ✓

ChallengeSum of first 10 odd numbers?

Answer: 100