Discrete Math › Section E · Sequences › Topic E.6
Strong induction
Ordinary induction lets each case lean on the one just before it. Strong induction lets it lean on every earlier case at once, which is exactly what you need when a problem breaks into smaller pieces of unpredictable size.
When one step back is not enough
Suppose you want to show that 60 is a product of primes. Knowing about 59 is no help at all. What helps is that \(60 = 6 \times 10\), and that 6 and 10 are already known to be products of primes. The useful smaller cases here are 6 and 10, not 59, and in general you cannot predict which smaller numbers a factorisation will produce. The ordinary induction of the topic "Proof by induction" only lets the \(k + 1\) case use the \(k\) case. Strong induction removes that restriction, so the step can call on whichever earlier cases it needs.
The principle of strong induction
To prove \(P(n)\) for all \(n \ge n_0\), prove two things. The base case or cases: \(P(n_0)\), and any further starting values the step needs. The inductive step: for every \(k\) at least as large as the last base case, if \(P(j)\) is true for every \(j\) with \(n_0 \le j \le k\), then \(P(k + 1)\) is true. The assumption is now a whole list of cases, \(P(n_0), P(n_0 + 1), \ldots, P(k)\), called the strong inductive hypothesis. The dominoes picture still works, but each domino is now knocked over by the combined weight of all the dominoes before it.
Worked example: every integer factors into primes
Prove that every integer \(n \ge 2\) is a prime or a product of primes. 1. Base case: 2 is prime. 2. Hypothesis: every \(j\) with \(2 \le j \le k\) is a prime or a product of primes. 3. Consider \(k + 1\). If it is prime, we are done. 4. Otherwise \(k + 1 = ab\) with \(2 \le a, b \le k\). Both factors are in the range of the hypothesis, so each is a prime or a product of primes. 5. Multiplying those factorisations writes \(k + 1\) as a product of primes. By strong induction the claim holds for all \(n \ge 2\). Note that \(a\) and \(b\) could be anywhere between 2 and \(k\), which is why the ordinary hypothesis would not do.
Worked example: postage stamps
Prove that every amount of 12 cents or more can be paid exactly with 4-cent and 5-cent stamps. 1. Base cases: \(12 = 4 + 4 + 4\), \(13 = 4 + 4 + 5\), \(14 = 4 + 5 + 5\) and \(15 = 5 + 5 + 5\). 2. Hypothesis: every amount from 12 up to \(k\) can be paid, where \(k \ge 15\). 3. For \(k + 1 \ge 16\), the amount \(k + 1 - 4 = k - 3\) lies between 12 and \(k\), so it can be paid by the hypothesis. 4. Add one 4-cent stamp to that payment to get \(k + 1\). The step reaches back 4 cents, so four base cases are needed. The bound is sharp: 11 cents cannot be paid.
How many base cases?
A strong induction step that reaches back \(m\) places needs \(m\) base cases. The stamp proof reaches back 4, so it starts with 12, 13, 14 and 15; with only 12 as a base, the step for 13 would call on 9 cents, which the hypothesis does not cover, and for 15 it would call on 11 cents, which cannot be paid at all. A recurrence that uses two earlier terms needs two base cases. The step must also be valid for every \(k\) from the last base case onwards. A useful check is to try the step on the first value it has to cover and confirm that every case it calls on is already proved.
Worked example: confirming a closed formula
In "Describing sequences and sums", \(a_n = a_{n-1} + 2a_{n-2}\) with \(a_0 = 0\), \(a_1 = 1\) was matched by \(a_n = \frac{2^n - (-1)^n}{3}\). Prove it for all \(n \ge 0\). 1. Base cases: \(\frac{1 - 1}{3} = 0\) and \(\frac{2 + 1}{3} = 1\), as required. 2. Hypothesis: the formula holds for all indices up to \(k\), where \(k \ge 1\). 3. Then \(a_{k+1} = a_k + 2a_{k-1}\), and substituting both,
4. Since \(-2(-1)^{k-1} = 2(-1)^k\), this is
and dividing by 3 gives the formula at \(k + 1\).
Worked example: sums of powers of 2
Prove that every integer \(n \ge 1\) is a sum of distinct powers of 2. 1. Base case: \(1 = 2^0\). 2. Hypothesis: every \(j\) with \(1 \le j \le k\) has such a representation. 3. If \(k + 1 = 2m\) is even, then \(1 \le m \le k\). Doubling each power in the representation of \(m\) gives distinct powers adding to \(2m\). 4. If \(k + 1 = 2m + 1\) is odd, with \(m \ge 1\), the doubled representation of \(m\) uses only powers of at least 2, so adding \(2^0 = 1\) keeps the powers distinct. For example, \(11 = 8 + 2 + 1\), so \(22 = 16 + 4 + 2\). This proof is the reason every positive integer has a binary representation.
Divide and conquer
The last example halved the problem rather than shrinking it by one. That is the typical shape of a strong induction proof: break a case of size \(k + 1\) into one or more smaller cases of any sizes, trust the hypothesis for each, and combine. It mirrors divide-and-conquer algorithms such as merge sort and binary search, whose correctness proofs assume the algorithm works on every smaller input. The topic "Recursion and structural induction" develops this connection between recursive programs and inductive proofs.
Is strong induction really stronger?
Despite the name, strong induction proves nothing that ordinary induction cannot. Given \(P(n)\), define \(Q(n)\) as "\(P(j)\) holds for every \(j\) from \(n_0\) to \(n\)". A strong induction proof of \(P\) is then an ordinary induction proof of \(Q\), and \(Q(n)\) includes \(P(n)\). Both rest on the well-ordering principle. The difference is convenience: when the smaller cases you need are unpredictable, strong induction states the hypothesis you actually use. When only the previous case is needed, ordinary induction is simpler and clearer.
Common mistakes to avoid
First, too few base cases: a step that reaches back four places needs four starting values. Second, calling on a case below the base, such as using the amount 8 cents in the stamp proof, which the claim never covered. Third, splitting \(k + 1\) into pieces that are not strictly smaller, so the hypothesis does not apply. Fourth, forgetting to check that the pieces stay in range: a factor of \(k + 1\) must be at least 2, not 1. Fifth, reaching for strong induction when the ordinary kind would do, which hides how the proof works.
Key takeaways
Strong induction assumes \(P(j)\) for every \(j\) from the base up to \(k\), then proves \(P(k + 1)\). Use it when a case breaks into smaller cases of unknown size, as in prime factorisation, binary representation, and divide-and-conquer arguments. A step reaching back \(m\) places needs \(m\) base cases. Recurrences that use two earlier terms are proved this way with two base cases. Strong and ordinary induction prove exactly the same statements; choose the one whose hypothesis matches the argument.
Flashcards
Flashcard
Assume P(j) for all j from n₀ to k, then prove P(k + 1)
Test your understanding
Question 1 of 5
In the step of a strong induction proof that P(n) holds for all n ≥ 2, what may you assume when proving P(k + 1)?
Question 2 of 5
A strong induction proof shows every amount of 8 cents or more can be paid with 3-cent and 5-cent stamps, by paying k − 2 and adding a 3-cent stamp. How many base cases does it need?
Question 3 of 5
Why is strong induction the natural tool for proving that every integer n ≥ 2 is a prime or a product of primes?
Question 4 of 5
What is the largest whole number of cents that cannot be paid exactly with 4-cent and 5-cent stamps?
Question 5 of 5
The halving proof writes 11 as 8 + 2 + 1. Which representation of 22 does it produce?
