Algebra
Mathematical induction
Prove a statement for all n by toppling dominoes — base case + inductive step.
Mathematical induction proves a statement for all natural numbers — like toppling an infinite line of dominoes.
Walk through
Step 1 of 5
Claim
We want to prove P(n): 1 + 2 + 3 + … + n = n(n+1)/2, for every natural number n ≥ 1.
You must actually use the inductive hypothesis in the step. If your proof of P(k+1) never refers to P(k), it isn't an induction proof — and may be hiding a gap.
Your turn
What is the base case for proving 'n³ − n is divisible by 3 for all n ≥ 1'?
Recap
- Two parts: a base case and an inductive step.
- The step proves P(k) ⇒ P(k+1) — the chain reaction.
- Together they prove P(n) for all n from the base onward, like infinite dominoes.
Two steps
- Base case: prove it for n = 1.
- Inductive step: assume true for n, prove for n+1.
Try it
Prove 1 + 2 + ... + n = n(n+1)/2
Base: 1 = 1·2/2 ✓. Step: assume sum to k, add (k+1), simplify to (k+1)(k+2)/2.