Mathematical induction proves statements indexed by the natural numbers by showing a base case and an inductive step. Strong induction allows the step to assume all previous cases, often simplifying recursive structures and number-theoretic proofs.
Details
Concepts
Weak induction: prove P(0) (or P(1)), then P(k) ⇒ P(k+1).
Strong induction: assume P(0..k) to prove P(k+1).
Well-ordering principle of ℕ: equivalent to induction.
Common patterns: sums/products, inequalities, divisibility, correctness of recursive algorithms.
Pitfalls: missing or incorrect base case, non-progressing step, unclear inductive hypothesis.
Exercises
Hands-on
Prove by induction: 1 + 2 + ··· + n = n(n + 1)/2.
Strong induction: every n ≥ 2 can be factored into primes.
Induction on algorithms: prove termination and correctness of a recursive binary search.