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.
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.