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.
Start with the warm-up and record your first reasoning.
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.
Orient yourself to the lesson goals, language, and core approach.
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)$
Work through the concept and complete its check.
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:
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:
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?
Build the next proof move and complete its check.
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$.
$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.
Follow the worked examples, then complete the check.
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} = c \cdot 2^{k-1}$, where $c =$ , which is less than $2^{k+1}$.
Correct the common traps and test your understanding.
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.
Complete the practice activities and revisit your opening thinking.
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.
Multiple choice, then short answer under exam conditions.
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)
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].
Sit the module quiz, then close the lesson off.
A full module quiz covering every lesson in this module, not just this one. Set aside a decent block of time and treat it like a real assessment.
Start the module quiz →Tick when you've finished the practice and review.
Work through this topic 1-on-1 with an experienced HSC tutor.
Book a free session →