How do you prove that a property holds for all natural numbers, when there are infinitely many? You cannot check them one by one. The principle of induction solves the problem with a simple idea: if the property holds for the first number, and whenever it holds for a number it also holds for the next, then it holds for all of them.
The idea: a row of dominoes
Picture an infinite row of dominoes. To be sure they all fall, two facts are enough:
- the first domino falls;
- every domino, as it falls, knocks over the next.
Induction formalises exactly this reasoning.
The structure of a proof by induction
Let P(n) be a property of natural numbers. To prove that P(n) holds for every n ≥ n₀:
- Base case: prove P(n₀).
- Inductive step: take an arbitrary k ≥ n₀, assume that P(k) is true (this is the inductive hypothesis) and prove P(k + 1).
The inductive step does not claim that P(k) is true: it proves the implication P(k) → P(k + 1). Together with the base case, this implication propagates truth to every number.
First example: the sum of the first n numbers
Statement: for every n ≥ 1, 1 + 2 + … + n = n(n + 1)/2.
Base case (n = 1): the left side is 1, the right side is 1 · 2 / 2 = 1. True.
Inductive step: assume 1 + 2 + … + k = k(k + 1)/2. Then
1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1)
Factoring out (k + 1):
= (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2
which is exactly the formula with n = k + 1. The proof is complete.
This formula has a concrete consequence: an algorithm with two nested loops, where the inner loop runs 1, 2, …, n steps, performs about n²/2 operations, so its complexity is quadratic.
Second example: an inequality
Statement: for every n ≥ 4, 2ⁿ ≥ n².
The base case is not n = 1 (where 2 ≥ 1 holds, but for n = 3 we have 8 < 9, so the property fails for some small values). We start from n = 4.
Base case (n = 4): 2⁴ = 16 and 4² = 16. True.
Inductive step: assume 2ᵏ ≥ k² with k ≥ 4. Then 2ᵏ⁺¹ = 2 · 2ᵏ ≥ 2k². It remains to show that 2k² ≥ (k + 1)², that is, k² ≥ 2k + 1. For k ≥ 4 we have k² ≥ 4k = 2k + 2k ≥ 2k + 8 > 2k + 1. Hence 2ᵏ⁺¹ ≥ (k + 1)².
The example shows that choosing the base case is part of the proof, and that the inductive step may use the assumption k ≥ n₀.
Third example: divisibility
Statement: for every n ≥ 0, 3 divides n³ − n.
Base case (n = 0): 0³ − 0 = 0, which is divisible by 3.
Inductive step: assume that 3 divides k³ − k. Compute
(k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k)
The first term is divisible by 3 by the inductive hypothesis, the second is a multiple of 3. Their sum is divisible by 3.
Typical mistakes
Forgetting the base case
Without a base case you can "prove" anything. Example: "for every n, n = n + 1". If k = k + 1, adding 1 gives k + 1 = k + 2: the inductive step works! But there is no n to start from, and the statement is false.
An inductive step that fails for some k
A famous example: "all horses are the same colour". Base case: a single horse is the same colour as itself. Step: given a group of k + 1 horses, removing one leaves k of the same colour; removing a different one leaves another k of the same colour; the two groups overlap, so all are the same colour. The mistake is that for k = 1 the two groups consist of one horse each and do not overlap. The step from 1 to 2 fails, and the whole chain collapses.
Using what you want to prove
In the inductive step you must start from P(k) and arrive at P(k + 1), not start from P(k + 1) and manipulate it until you get something true, unless every step is an equivalence.
Induction and programming
Induction and recursion are two sides of the same idea. A recursive function has a base case and a step that reduces to a smaller case; proving it correct almost always uses induction on the size of the input. If the base case is right and, assuming the recursive call returns the correct result, the step builds the correct result, then the function is correct for every input.
In short
- Induction proves P(n) for every n ≥ n₀ with a base case and a step P(k) → P(k + 1).
- The base case must be chosen with care and checked: without it the proof is worthless.
- The inductive step must work for every k ≥ n₀, including the smallest ones.
- It is the natural tool for sums, inequalities, divisibility and recursive formulas.
- Proving a recursive function correct is, in effect, a proof by induction.
