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 lessonthink 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<k+1$, the strong hypothesis covers both $a$ and $b$, while simple induction only gives $n=k$.
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 confidencethat 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.