Strong Induction
Simple induction assumes only the $k$th case. But what if proving case $k+1$ requires knowing cases $k-1$, $k-2$, or even earlier? Strong induction gives you the full history — assume all previous cases at once, and suddenly proofs like prime factorisation and the Fibonacci bound become straightforward.
In simple induction, the inductive hypothesis assumes $P(k)$ is true. Without looking at the lesson — think of a situation where knowing only $P(k)$ might NOT be enough to prove $P(k+1)$. Describe it below.
Strong induction is a variant of mathematical induction where the inductive hypothesis is more powerful. Instead of assuming only $P(k)$ is true, you assume that all preceding statements $P(1), P(2), \ldots, P(k)$ are true.
This extra assumption is essential when proving $P(k+1)$ requires knowing not just $P(k)$, but some earlier case such as $P(k-1)$ or $P(m)$ for $m < k$.
If $P(1)$ is true, and if $P(1) \wedge P(2) \wedge \cdots \wedge P(k) \Rightarrow P(k+1)$ for every $k \geq 1$, then $P(n)$ is true for all positive integers $n$.
Key facts
- Strong induction hypothesis: assume $P(1) \wedge P(2) \wedge \cdots \wedge P(k)$
- Simple induction is a special case of strong induction
- Recurrence relations that use two previous terms require two base cases
Concepts
- Why assuming all previous cases is logically valid
- How to recognise when strong induction is necessary
- Why prime factorisation and Fibonacci bounds need strong induction
Skills
- Write a complete strong induction proof with correct hypothesis wording
- Identify how many base cases a proof requires
- Apply strong induction to prime factorisation and inequality problems
| Feature | Simple Induction | Strong Induction |
|---|---|---|
| Hypothesis | Assume $P(k)$ only | Assume $P(1), P(2), \ldots, P(k)$ |
| Base case(s) | Usually one value ($n = 1$) | May need multiple values |
| When needed | $P(k+1)$ depends only on $P(k)$ | $P(k+1)$ depends on earlier cases |
| Examples | Sum formulas, inequality $2^n > n$ | Fibonacci bound, prime factorisation |
Key concept: Simple vs strong induction — side by side.
Pause — copy the side-by-side comparison: simple induction assumes $n=k$ only; strong induction assumes all cases up to $n=k$ — include the decision rule (use strong when inductive step needs earlier cases) into your book.
Quick check: When using strong induction to prove a statement about the Fibonacci sequence $F_n = F_{n-1} + F_{n-2}$, you would need:
We just saw that simple induction assumes only $n=k$, while strong induction assumes all cases from the base up to $n=k$, giving a richer hypothesis. That raises a question: why is strong induction essential for the prime factorisation proof, where $n=k+1$ splits into two factors both strictly less than $k+1$? This card answers it → if $k+1=ab$ with $a,b Statement: Prove that every integer $n \geq 2$ can be written as a product of primes. Step 1 — Base Case ($n = 2$): $2$ is prime, so $2 = 2$ is a (trivial) product of primes. True for $n = 2$. ✓ Step 2 — Inductive Hypothesis: Assume every integer $m$ with $2 \leq m \leq k$ can be written as a product of primes. Step 3 — Inductive Step ($n = k + 1$): Consider $k + 1$. Case 1: If $k + 1$ is prime, it is trivially a product of primes. ✓ Case 2: If $k + 1$ is composite, then $k + 1 = ab$ for integers $a, b$ with $2 \leq a, b \leq k$. By the inductive hypothesis, both $a$ and $b$ have prime factorisations. So $k + 1 = ab$ is also a product of primes. ✓ In both cases $k + 1$ has a prime factorisation. By strong induction, every integer $n \geq 2$ can be written as a product of primes. ∎ Statement: Prove that every integer $n \geq 2$ can be written as a product of primes. Pause — copy the strong-induction proof that every integer $n\geq2$ has a prime factorisation, identifying the line where the strong hypothesis is essential into your book.
Did you get this? True or false: In the prime factorisation proof, the base case is $n = 1$ because $1$ is the smallest positive integer.
Worked examples · 3 in a row, reveal as you go
Let $F_1 = 1$, $F_2 = 1$, $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$. Prove $F_n < 2^n$ for all $n \geq 1$.
For the Fibonacci bound proof, write the correct strong induction hypothesis and explain why simple induction fails.
A sequence satisfies $a_1 = 1$, $a_2 = 3$, $a_n = a_{n-1} + 2a_{n-2}$ for $n \geq 3$. Use strong induction to prove that $a_n$ is odd for all $n \geq 1$. (3 marks)
Fill the gap: In a strong induction proof for a recurrence $a_n = a_{n-1} + a_{n-2}$, the number of base cases needed is .
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: In a strong induction proof, it is acceptable to write "Assume $P(k)$ is true" and then use $P(k-1)$ in the inductive step.
Activities · practice with the ideas
State the strong induction hypothesis you would use to prove $F_n < 2^n$ for the Fibonacci sequence.
How many base cases are needed to prove that every integer $n \geq 2$ has a prime factorisation? Explain why.
Why does the proof that every integer $\geq 2$ has a prime factorisation require strong (not simple) induction? Write 2–3 sentences.
A sequence satisfies $b_1 = 2$, $b_2 = 2$, $b_n = b_{n-1} + b_{n-2}$. Use strong induction to prove $b_n$ is even for all $n \geq 1$.
Write the concluding sentence for a strong induction proof of the statement $P(n)$: "Every integer $n \geq 2$ has a prime factorisation."
Odd one out: Three of these statements about strong induction are correct. Which one is WRONG?
Earlier you described a situation where knowing only $P(k)$ might not be enough.
The canonical example is the Fibonacci sequence: to prove $F_{k+1} < 2^{k+1}$, you need $F_k < 2^k$ AND $F_{k-1} < 2^{k-1}$. Simple induction only gives you the former. Similarly, prime factorisation is impossible with simple induction because a composite number could split into factors that are far earlier in the sequence — not just one step back.
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. Explain the difference between simple and strong induction. Your answer should address: the hypothesis, the base cases, and when each is used. (2 marks)
Q2. Use strong induction to prove that every integer $n \geq 2$ can be written as a product of prime numbers. (4 marks)
Q3. Let $F_1 = 1$, $F_2 = 1$, $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$. Prove by strong induction that $F_n < 2^n$ for all positive integers $n$. (4 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. "Assume $F_m < 2^m$ for all integers $m$ with $1 \leq m \leq k$, where $k \geq 2$." · 2. One base case ($n=2$) — in the step, we only use $m \leq k$, not $m \leq k-1$ for a second level. · 4. $b_n$ even: step: $b_{k+1} = b_k + b_{k-1}$; both even by hypothesis; even + even = even. ∎ · 5. "By the principle of strong mathematical induction, every integer $n \geq 2$ has a prime factorisation."
Q1 (2 marks): Simple induction assumes $P(k)$ only [1]. Strong induction assumes $P(1), P(2), \ldots, P(k)$ — all previous cases [1]. Use simple when $P(k+1)$ depends only on $P(k)$; use strong when earlier cases are needed (e.g. recurrences, prime factorisation).
Q2 (4 marks): Base case $n=2$: $2$ is prime ✓ [1]. Hypothesis: assume every integer $m$ with $2 \leq m \leq k$ is a product of primes [1]. Step: Case 1 — if $k+1$ is prime, trivially done. Case 2 — if $k+1$ composite, $k+1=ab$ with $2 \leq a,b \leq k$; by hypothesis $a$ and $b$ have prime factorisations, so $k+1=ab$ does too [1]. Conclusion: by strong induction, true for all $n \geq 2$ [1].
Q3 (4 marks): Base cases: $F_1=1<2$ ✓; $F_2=1<4$ ✓ [1]. Hypothesis: assume $F_m < 2^m$ for all $1 \leq m \leq k$, $k \geq 2$ [1]. Step: $F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 3 \cdot 2^{k-1} < 4 \cdot 2^{k-1} = 2^{k+1}$ [1]. Conclusion: by strong induction, $F_n < 2^n$ for all $n \geq 1$ [1].
Five timed questions. 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.