Strong Induction
A number theorist proves every integer $\geq 2$ has a prime factorisation. A combinatorialist bounds the $n$-th Fibonacci number. A child counts how to make $24c$ stamps from $5c$ and $9c$ values. All three reach for the same tool — strong induction — where the $(k+1)$-th case might depend not just on $k$ but on any smaller case in the chain. This lesson rewires your induction reflex.
Ordinary induction uses $P(k) \Rightarrow P(k+1)$. Before reading on — give an example where this is not enough: the next case naturally depends on two or more earlier cases rather than just the immediately previous one. Hint: think recurrences and number theory.
Strong induction rewards two habits: verify enough base cases to cover the depth of the recurrence, then assume the claim for all values up to $k$ (not just $k$ itself) when proving $P(k+1)$. The logical structure is identical to ordinary induction — only the hypothesis is stronger.
The all-prior-cases strategy: (1) verify base cases for $n_0, n_0+1, \ldots$ as far as the recurrence reaches, (2) assume $P(j)$ true for every $j$ with $n_0 \leq j \leq k$, (3) prove $P(k+1)$ using any combination of these prior cases.
Strong IH: $\forall j \in \{n_0, \ldots, k\}: P(j) \Rightarrow P(k+1)$
Key facts
- Strong induction: assume $P(j)$ for every $j \in \{n_0, \ldots, k\}$, then prove $P(k+1)$
- Well-ordering principle: every non-empty subset of $\mathbb{N}$ has a least element
- Fibonacci recurrence: $F_{n+1} = F_n + F_{n-1}$ with $F_1 = F_2 = 1$
Concepts
- Why ordinary induction fails when the recurrence depends on multiple earlier cases
- How strong induction and well-ordering are equivalent statements
- Why the prime factorisation theorem needs strong induction (not ordinary)
Skills
- Write a strong induction proof with multiple base cases and an explicit strong IH
- Prove every integer $\geq 2$ has a prime factorisation
- Solve postage-stamp / coin-change problems using strong induction
Ordinary induction proves $P(k+1)$ from $P(k)$ alone. But sometimes the structure of the problem forces $P(k+1)$ to depend on cases earlier than $k$. The classic examples:
- Fibonacci-style. $F_{n+1} = F_n + F_{n-1}$ — to bound $F_{n+1}$ you need bounds on both $F_n$ and $F_{n-1}$.
- Prime factorisation. A composite $n+1 = a \cdot b$ has $a, b < n+1$ but neither is necessarily $n$. You need their factorisations from the strong hypothesis.
- Postage stamps. Showing every $n \geq n_0$ can be written as $5a + 9b$ uses $n - 5$ or $n - 9$, not just $n - 1$.
Hook revisited (prime factorisation of 84). $84 = 4 \cdot 21 = 2 \cdot 2 \cdot 3 \cdot 7$. To prove that every $n \geq 2$ has a prime factorisation:
- Base: $n=2$ is prime — its own factorisation. ✓
- Strong IH: assume every $j$ with $2 \leq j \leq k$ has a prime factorisation.
- Step on $k+1$: if $k+1$ is prime, done. Otherwise $k+1 = a \cdot b$ with $2 \leq a, b \leq k$. By the strong IH both $a$ and $b$ have prime factorisations, so does $k+1$. ✓
Strong IH: assume $P(j)$ for all $j$ from $n_0$ up to $k$, not just $k$ · Use strong induction when the recurrence depends on multiple earlier cases · Prime factorisation: composite $k+1 = a \cdot b$ with $a, b \leq k$; apply IH to both · Strong induction $\Leftrightarrow$ well-ordering (least counterexample argument)
Pause — copy the strong IH statement, the prime-factorisation argument (composite $k+1 = ab$ with $a,b \leq k$, apply IH to both), and the equivalence with well-ordering into your book.
Quick check: A proof claims that for $n \geq 12$, every integer $n$ can be written as $4a + 5b$ for some non-negative integers $a, b$. Which base cases must be verified before the strong inductive step?
We just saw that ordinary induction fails when $P(k+1)$ requires $P(k-1)$ or earlier, as in prime factorisation — so we need the strong IH: assume $P(j)$ for all $j$ from $n_0$ up to $k$. That raises a question: what is the canonical two-step recurrence that demands both $P(k)$ and $P(k-1)$? This card answers it → $F_n < 2^n$, proved using $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^{k+1}$.
The Fibonacci sequence $F_1 = F_2 = 1$, $F_{n+1} = F_n + F_{n-1}$ is the archetype for strong induction. Any bound on $F_n$ usually uses the previous two terms together. Claim: $F_n < 2^n$ for all $n \geq 1$.
- Bases. $F_1 = 1 < 2 = 2^1$ ✓. $F_2 = 1 < 4 = 2^2$ ✓. Two bases are required because the recurrence reaches back two steps.
- Strong IH. Assume $F_j < 2^j$ for all $j$ with $1 \leq j \leq k$ (some $k \geq 2$).
- Step. $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1}(2+1) = 3 \cdot 2^{k-1} < 4 \cdot 2^{k-1} = 2^{k+1}$. ✓
$F_n < 2^n$ for $n \geq 1$: bases $F_1=1<2$ and $F_2=1<4$ · Inductive step uses both $F_k$ and $F_{k-1}$, hence strong IH · $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 3 \cdot 2^{k-1} < 2^{k+1}$ · Number of base cases = depth of recurrence
Pause — copy $F_n < 2^n$ with two base cases $F_1=1<2$, $F_2=1<4$, the strong-IH step $F_{k+1} = F_k+F_{k-1} < 2^k+2^{k-1} = 3 \cdot 2^{k-1} < 2^{k+1}$, and the rule that the number of base cases equals the recurrence depth into your book.
Did you get this? True or false: to prove $F_n < 2^n$ for all $n \geq 1$ using strong induction, verifying only $F_1 < 2$ as the base case is sufficient.
Worked examples · 3 in a row, reveal as you go
Prove by strong induction that the Fibonacci numbers, defined by $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$ for $n \geq 2$, satisfy $F_n < 2^n$ for all $n \geq 1$.
Prove by strong induction that every integer $n \geq 2$ can be written as a product of one or more primes.
Prove by strong induction that every integer $n \geq 8$ can be written as $n = 3a + 5b$ for some non-negative integers $a, b$.
Fill the gap: In the Fibonacci proof $F_n < 2^n$, the inductive step gives $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = \cdot 2^{k-1}$, which is less than $2^{k+1}$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: the well-ordering principle states that every non-empty subset of $\mathbb{N}$ has a greatest element.
Activities · practice with the ideas
Prove by strong induction that the Fibonacci numbers satisfy $F_n \leq \left(\tfrac{7}{4}\right)^{n-1}$ for all $n \geq 1$. (Hint: use bases $n=1, 2$ and check the step using the recurrence.)
Prove by strong induction that every integer $n \geq 2$ has a prime factorisation.
Prove by strong induction that every integer $n \geq 8$ can be written as $n = 3a + 5b$ for some non-negative integers $a, b$. State all base cases.
Explain in your own words why strong induction is equivalent to the well-ordering principle. (One paragraph.)
A sequence is defined by $a_1 = 1$, $a_2 = 3$ and $a_{n+1} = a_n + 2a_{n-1}$ for $n \geq 2$. Prove by strong induction that $a_n = 2^n - (-1)^n$ for all $n \geq 1$.
Odd one out: Three of these statements about strong induction are correct. Which one is NOT?
Earlier you considered factoring $84 = 2 \cdot 2 \cdot 3 \cdot 7$ and asked whether ordinary induction could prove every integer has such a factorisation.
The answer is no — the factor pair $a \cdot b = k+1$ has $a$ and $b$ smaller than $k+1$ but neither is forced to equal $k$. Ordinary induction $P(k) \Rightarrow P(k+1)$ gives you only $P(k)$, not $P(a)$ or $P(b)$. Strong induction provides every prior case, exactly the hypothesis the proof needs. This pattern — recurrences that reach back unpredictably — is why strong induction matters.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove by strong induction that the Fibonacci numbers $F_n$ (with $F_1 = F_2 = 1$, $F_{n+1} = F_n + F_{n-1}$) satisfy $F_n < 2^n$ for all $n \geq 1$. (2 marks)
Q2. Prove by strong induction that every integer $n \geq 2$ can be written as a product of one or more primes. (3 marks)
Q3. Prove by strong induction that every integer $n \geq 8$ can be written as $n = 3a + 5b$ for some non-negative integers $a, b$. State and justify the base cases. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Bases: $F_1=1 \leq 1=(7/4)^0$ ✓, $F_2=1 \leq 7/4$ ✓. Strong IH up to $k$. Step: $F_{k+1}=F_k+F_{k-1} \leq (7/4)^{k-1} + (7/4)^{k-2} = (7/4)^{k-2}(7/4 + 1) = (7/4)^{k-2} \cdot 11/4$. Since $11/4 < (7/4)^2 = 49/16$ (i.e. $44 < 49$), we get $F_{k+1} \leq (7/4)^{k-2} \cdot (7/4)^2 = (7/4)^k$. ✓
2. Base $n=2$ is prime. Strong IH: every $j$ with $2 \leq j \leq k$ has prime factorisation. Step: if $k+1$ prime done; else $k+1 = ab$ with $2 \leq a, b \leq k$, both have factorisations by IH, product is a factorisation of $k+1$.
3. Bases: $8=3+5$, $9=3+3+3$, $10=5+5$. Strong IH up to $k \geq 10$. Step: $k+1 \geq 11 \Rightarrow k+1-3 = k-2 \geq 8$, apply IH: $k-2 = 3a'+5b'$, so $k+1 = 3(a'+1)+5b'$.
4. (Equivalence) Suppose strong induction fails on some claim. Let $S$ be the set of counterexamples. By well-ordering, $S$ has a least element $n_0$. All $j < n_0$ are not in $S$ (i.e. satisfy $P$), so the strong inductive step forces $P(n_0)$ — contradicting $n_0 \in S$. So no counterexample exists; strong induction holds. The reverse direction is similar.
5. Bases: $a_1 = 1 = 2 - (-1)$ ✓, $a_2 = 3 = 4 - 1$ ✓. Step: $a_{k+1} = a_k + 2a_{k-1} = (2^k - (-1)^k) + 2(2^{k-1} - (-1)^{k-1}) = 2^k + 2^k - (-1)^k - 2(-1)^{k-1} = 2^{k+1} - (-1)^k(1 - 2) = 2^{k+1} - (-1)^k(-1) = 2^{k+1} - (-1)^{k+1}$.
Q1 (2 marks): Bases $F_1, F_2$ verified [1]. Strong IH and step $F_{k+1} < 2^k + 2^{k-1} = 3 \cdot 2^{k-1} < 2^{k+1}$ [1].
Q2 (3 marks): Base $n=2$ prime [1]. Strong IH and split into prime / composite cases [1]. Apply IH to both factors of a composite [1].
Q3 (3 marks): Three bases $n=8,9,10$ verified [1]. Strong IH and step uses $n+1-3 \geq 8$ [1]. Add one stamp of value 3 to express $n+1$ [1].
Five timed questions on Fibonacci-style inequalities, prime factorisation, and postage-stamp problems. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering strong-induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.