Mathematical induction
Induction proves statements about all natural numbers by showing a first case and a step that carries truth forward, like an infinite row of falling dominoes.
The principle
To prove \(P(n)\) for all \(n \ge n_0\): prove the base case \(P(n_0)\), then prove the inductive step: for every \(k \ge n_0\), if \(P(k)\) is true, then \(P(k + 1)\) is true. The assumption \(P(k)\) is the inductive hypothesis. Together, these knock over every domino.
Worked example: a sum formula
Prove \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\). Base: \(n = 1\), both sides equal 1. Step: assume it holds for \(k\). Then \(1 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k + 1) = \frac{(k+1)(k+2)}{2}\), which is the formula for \(k + 1\). So it holds for all \(n \ge 1\).
\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}Worked example: divisibility
Prove \(3\) divides \(n^3 - n\) for all \(n \ge 0\). Base: \(0^3 - 0 = 0\), divisible by 3. Step: \((k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k\). The first part is divisible by 3 by hypothesis, and \(3k^2 + 3k\) is clearly divisible by 3, so the whole is.
Worked example: an inequality
Prove \(2^n > n\) for all \(n \ge 1\). Base: \(2 > 1\). Step: if \(2^k > k\), then \(2^{k+1} = 2 \cdot 2^k > 2k \ge k + 1\) for \(k \ge 1\). Inequalities often need a small extra estimate like \(2k \ge k + 1\).
Strong induction
In strong induction, the step may assume \(P\) holds for all values from the base case up to \(k\), not just \(k\). This is useful when \(P(k+1)\) depends on earlier cases. Example: every integer \(n \ge 2\) is a product of primes; if \(n\) is not prime, it factors into smaller numbers, each of which is a product of primes by the strong hypothesis.
Common errors in induction
Skipping the base case can 'prove' false statements, since the step alone shows nothing. A famous fake proof that all horses are the same colour fails because the step from 1 to 2 does not work. Also avoid assuming what you are trying to prove for \(k + 1\); use only the hypothesis for \(k\).
Why induction works
Induction is equivalent to the well-ordering principle: every nonempty set of natural numbers has a smallest element. If \(P\) failed somewhere, there would be a smallest failure, contradicting the base case or the inductive step. Induction is therefore as solid as the natural numbers themselves.
Induction in computer science
Induction proves that recursive algorithms are correct and that loops maintain their invariants. To show a loop computes a running total correctly, prove the invariant holds initially (base) and is preserved by each iteration (step).
Key takeaways
Induction needs a base case and an inductive step from \(k\) to \(k + 1\). Strong induction assumes all earlier cases. Write the \(k + 1\) case and find the \(k\) case inside it. Never skip the base case, and use induction to prove sums, divisibility, inequalities, and program correctness.
Flashcard
Prove P(n0)
Check your understanding
In a proof by induction, what must be shown besides the base case?