Strong induction: Worked examples — Maths deep dive

Parent: Strong induction. This child page is a drill hall. We build one table of every kind of case strong induction can throw at you, then work each cell to the ground. If you have not met the domino picture or the "assume all below, prove the next" idea yet, read the parent first — here we assume you know what strong induction is and we grind on how to actually do it.

The scenario matrix

Before any example, let us list every class of case a strong-induction problem can belong to. Each row is a "cell." Every worked example below is tagged with the cell it fills, so by the end no scenario is left unshown.

Cell	What makes it this case	How far the step reaches back	Base cases needed
A — single reach-back	step uses only $P (n - 1)$	1 step	1
B — fixed multi reach-back	step uses $P (n - 1)$ and $P (n - 2)$	2 steps	2
C — uncontrolled reach-back	step splits $n = ab$ , $a, b$ unknown but $< n$	anywhere below	1 (smallest)
D — jump-by- $d$ reach-back	step uses $P (n - d)$ for fixed $d > 1$	$d$ steps	$d$ (fill the base zone)
E — degenerate / boundary	smallest inputs, or the step would point below the floor	—	must plug the gap
F — limiting / growth behaviour	what the bound does as $n \to \infty$	—	—
G — real-world word problem	phrased in coins/stamps/tiles	depends	depends
H — exam twist	a "too few base cases" trap or a false claim	—	—

Now, one guiding rule that resolves all of them (recall $n_{0}$ = starting index, $d$ = largest reach-back, both defined just above):

Example 1 — Cell A (single reach-back)

Worked example

Claim $P (n)$ : for all $n \geq 1$ , the sum $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ . (Here the starting index $n_{0} = 1$ .)

Forecast: guess — does this need one base case or more? (Only $P (n - 1)$ is used, so $d = 1$ … one base.)

Base $P (1)$ : left side $= 1$ , right side $= \frac{1 \cdot 2}{2} = 1$ . ✅ Why this step? $n = 1$ is the floor $n_{0}$ ; nothing smaller exists, so we verify it directly.
Strong step: assume $P (k)$ for all $1 \leq k < n$ . We only need $k = n - 1$ : $1 + 2 + \dots + n = = \frac{( n - 1 ) n}{2} by hypothesis (1 + \dots + (n - 1)) + n .$ Why this step? Peel off the last term so the remaining sum is a smaller case the hypothesis covers.
Simplify: $\frac{( n - 1 ) n}{2} + n = \frac{( n - 1 ) n + 2 n}{2} = \frac{n ^{2} + n}{2} = \frac{n ( n + 1 )}{2} .$ Why this step? Common denominator $2$ , then factor $n$ — this must land on the target formula.

Verify: $n = 4$ : $1 + 2 + 3 + 4 = 10$ and $\frac{4 \cdot 5}{2} = 10$ . ✅ Here strong induction is overkill — ordinary induction would do — which is exactly the point of Cell A: single reach-back never needs the full history.

Example 2 — Cell B (two fixed predecessors) + a figure

Worked example

Find the growth bases: the recurrence $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ has characteristic equation $x^{2} = 5 x - 6$ , i.e. $x^{2} - 5 x + 6 = 0$ , with roots $x = 2$ and $x = 3$ . So $a_{n} = A \cdot 2^{n} + B \cdot 3^{n}$ . Why this step? A two-term linear recurrence is solved by its two roots; the general solution is their weighted sum.
Fit the two bases: $A \cdot 2 + B \cdot 3 = 2$ and $A \cdot 4 + B \cdot 9 = 5$ . From the first, $2 A = 2 - 3 B \Rightarrow A = 1 - \frac{3}{2} B$ ; substitute into the second: $4 (1 - \frac{3}{2} B) + 9 B = 5 \Rightarrow 4 + 3 B = 5 \Rightarrow B = \frac{1}{3}, A = \frac{1}{2}$ . $a_{n} = \frac{1}{2} \cdot 2^{n} + \frac{1}{3} \cdot 3^{n} = 2^{n - 1} + 3^{n - 1} .$ Why this step? The two base values pin the two unknowns — exactly why Cell B needs two base cases.
Strong step (proving the closed form): assume $a_{k} = 2^{k - 1} + 3^{k - 1}$ for all $k < n$ , in particular $k = n - 1, n - 2$ . Then $a_{n} = 5 (2^{n - 2} + 3^{n - 2}) - 6 (2^{n - 3} + 3^{n - 3}) .$ Group powers of $2$ : $5 \cdot 2^{n - 2} - 6 \cdot 2^{n - 3} = 2^{n - 3} (10 - 6) = 4 \cdot 2^{n - 3} = 2^{n - 1}$ . Group powers of $3$ : $5 \cdot 3^{n - 2} - 6 \cdot 3^{n - 3} = 3^{n - 3} (15 - 6) = 9 \cdot 3^{n - 3} = 3^{n - 1}$ . So $a_{n} = 2^{n - 1} + 3^{n - 1}$ . ✅ Why this step? Substitute both predecessors — a single one is useless here, which is the signature of Cell B (the two arrows in the figure).

Verify: $a_{1} = 2^{0} + 3^{0} = 2$ ✅, $a_{2} = 2^{1} + 3^{1} = 5$ ✅, $a_{3} = 5 \cdot 5 - 6 \cdot 2 = 13 = 2^{2} + 3^{2} = 4 + 9$ ✅.

Example 3 — Cell C (uncontrolled reach-back)

Worked example

Claim $P (n)$ : every integer $n \geq 2$ has a prime divisor. (Starting index $n_{0} = 2$ .)

Forecast: how many base cases? The split $n = ab$ can land anywhere below $n$ — so we cannot predict $n - 1$ vs $n - 7$ . Guess: one base ( $n = 2$ ), full history hypothesis.

Base $P (2)$ : $2$ is prime, so it divides itself — a prime divisor exists. ✅ Why this step? Smallest possible input $n_{0} = 2$ ; there is no room to factor.
Strong step: assume every $k$ with $2 \leq k < n$ has a prime divisor. Take $n$ .
- If $n$ is prime: $n$ is its own prime divisor. Done.
- If $n$ is composite: $n = ab$ with $2 \leq a < n$ . By the strong hypothesis $a$ has a prime divisor $p$ , and $p ∣ a ∣ n$ , so $p ∣ n$ . Why this step? We do not know which smaller number $a$ is — that is exactly why ordinary induction (only $n - 1$ ) cannot help. Cell C demands the whole history.

Verify: $n = 91 = 7 \cdot 13$ ; $a = 7$ is $< 91$ , its prime divisor $7$ divides $91$ . ✅ We never needed $P (90)$ .

Example 4 — Cell D (jump-by- $d$ , here $d = 4$ ) — the stamps

Worked example

Claim: every amount $n \geq 12$ cents is payable with $4$ - and $5$ -cent stamps. (Starting index $n_{0} = 12$ .)

Forecast: the step will subtract one stamp — the smallest useful jump is $4$ . So Cell D with $d = 4$ ⇒ four base cases.

Base zone $n = 12, 13, 14, 15$ : $12 = 4 + 4 + 4, 13 = 4 + 4 + 5, 14 = 4 + 5 + 5, 15 = 5 + 5 + 5. ✅$ Why four? By the base-zone rule with $n_{0} = 12, d = 4$ we need $n_{0}, \dots, n_{0} + 3 = 12, 13, 14, 15$ .
Strong step for $n \geq 16$ : assume all of $[12, n)$ payable. Since $n \geq 16$ , we have $n - 4 \geq 12$ , so $n - 4$ is payable; add one $4$ -cent stamp. Why this step? The reach-back is a fixed $4$ , and the base zone is exactly $4$ wide, so $n - 4$ always lands inside proven territory.

Verify: $n = 23$ : subtract one $4$ -cent stamp to get $19$ ; $19 = 4 + 5 + 5 + 5$ (one $4$ , three $5$ s). Adding the removed $4$ : $23 = 4 + 4 + 5 + 5 + 5$ , i.e. two $4$ -cent and three $5$ -cent stamps, and $2 \cdot 4 + 3 \cdot 5 = 8 + 15 = 23$ . ✅

Example 5 — Cell E (degenerate boundary) — a figure

Example 6 — Cell F (limiting behaviour) — a figure

Worked example

Claim: with the same Fibonacci sequence, $F_{n} \geq (\frac{3}{2})^{n - 2}$ for all $n \geq 1$ — a lower growth bound. Combined with Example 5 this pins the growth rate as $n \to \infty$ .

Forecast: two reach-back terms ( $d = 2$ ) ⇒ two base cases. And the interesting part is Cell F: what does the pair of bounds say about $\infty$ ?

Bases $n = 1, 2$ : $F_{1} = 1 \geq (\frac{3}{2})^{- 1} = \frac{2}{3}$ ✅; $F_{2} = 1 \geq (\frac{3}{2})^{0} = 1$ ✅. Why? Two-term recurrence again — anchor two.
Strong step ( $n \geq 3$ ): assume $F_{k} \geq (\frac{3}{2})^{k - 2}$ for $k < n$ . $F_{n} = F_{n - 1} + F_{n - 2} \geq (\frac{3}{2})^{n - 3} + (\frac{3}{2})^{n - 4} .$ Why this step? Lower-bound each term by its hypothesis value.
Factor: $= (\frac{3}{2})^{n - 4} (\frac{3}{2} + 1) = (\frac{3}{2})^{n - 4} \cdot \frac{5}{2} .$ Since $\frac{5}{2} \geq (\frac{3}{2})^{2} = \frac{9}{4} = 2.25$ , we get $F_{n} \geq (\frac{3}{2})^{n - 4} (\frac{3}{2})^{2} = (\frac{3}{2})^{n - 2}$ . ✅ Why this step? We compare $\frac{5}{2} = 2.5$ against $(\frac{3}{2})^{2} = 2.25$ ; the surplus lets us fold the constant into the exponent.

Limiting reading (Cell F), see the figure in Example 5: the plum floor $1. 5^{n - 2}$ and orange ceiling $2^{n}$ from that same picture together bracket the teal dots: $(\frac{3}{2})^{n - 2} \leq F_{n} < 2^{n} .$ As $n \to \infty$ the band between plum and orange widens on the log plot but $F_{n}$ stays trapped inside it forever, so $F_{n}$ grows exponentially with base somewhere between $1.5$ and $2$ — the two strong-induction proofs are the two walls of that visual squeeze.

Verify: $n = 8$ : $F_{8} = 21$ ; lower bound $(\frac{3}{2})^{6} = \frac{729}{64} \approx 11.39$ ; upper $2^{8} = 256$ . $11.39 \leq 21 < 256$ ✅.

Example 7 — Cell G (real-world word problem)

Worked example

Claim (tiling): a $2 \times n$ strip can be fully covered by $1 \times 2$ dominoes for every $n \geq 1$ , and the number of tilings $T_{n}$ obeys $T_{n} = T_{n - 1} + T_{n - 2}$ (so $T_{n} = F_{n + 1}$ ).

Forecast: placing the last tile either vertical (covers the last column, uses $T_{n - 1}$ ) or two horizontals (covers last two columns, uses $T_{n - 2}$ ). Two reach-backs ( $d = 2$ ) ⇒ Cell B/G, two bases.

Bases: $T_{1} = 1$ (one vertical domino), $T_{2} = 2$ (two verticals or two horizontals). ✅ Why two? The recurrence looks back two columns.
Strong step ( $n \geq 3$ ): every tiling of the $2 \times n$ strip ends in exactly one of two ways — a vertical domino in column $n$ (rest is a $2 \times (n - 1)$ strip) or two stacked horizontal dominoes in columns $n - 1, n$ (rest is $2 \times (n - 2)$ ). These cases are disjoint and exhaustive, so $T_{n} = T_{n - 1} + T_{n - 2}$ . Why strong not ordinary? The count of the $2 \times (n - 2)$ sub-strip is needed directly — a single predecessor cannot supply it.

Verify: $T_{3} = T_{2} + T_{1} = 2 + 1 = 3$ . By hand: strip $2 \times 3$ has tilings ${$ three verticals; V + two horiz; two horiz + V $} = 3$ . ✅ And $T_{3} = F_{4} = 3$ . ✅

Example 8 — Cell H (exam twist: too few base cases → false "proof")

Worked example

Twisted claim (FALSE): "For $a_{1} = 1, a_{2} = 8, a_{n} = 2 a_{n - 1}$ for $n \geq 3$ … by strong induction with one base case $a_{1} = 1$ , we prove $a_{n} = 2^{n - 1}$ ."

Forecast: spot the crack before reading on. The recurrence uses only $a_{n - 1}$ (Cell A, $d = 1$ ) but the closed form is contradicted by $a_{2}$ . Does one base case suffice?

Test the alleged formula at the given data: $a_{2} = 8$ , but $2^{2 - 1} = 2$ . So $a_{2} \neq = 2^{1}$ . The claim is false at $n = 2$ . Why this step? An exam "proof" that never checks $n = 2$ hides that $a_{2}$ was defined as $8$ , breaking $2^{n - 1}$ immediately.
Where the false proof cheats: the recurrence only holds for $n \geq 3$ , so $a_{2}$ is a second base value that must be checked, not derived. It was skipped. This is the Cell H trap: missing the base case that the recurrence does not cover. Why this matters: Cell E and H are cousins — always ask "for which $n$ does my step actually apply?" The step here runs only for $n \geq 3$ , so both $a_{1}$ and $a_{2}$ are bases, and $a_{2}$ kills the formula.
Correct closed form: from $a_{3} = 2 a_{2} = 16, a_{4} = 32, \dots$ we get for $n \geq 2$ , $a_{n} = 8 \cdot 2^{n - 2} = 2^{n + 1}$ ; but $a_{1} = 1 \neq = 2^{2}$ . So there is no single clean formula for all $n \geq 1$ ; the sequence is $1, 8, 16, 32, 64, \dots$ .

Verify: $a_{3} = 2 \cdot 8 = 16$ and $2^{3 + 1} = 16$ ✅; $a_{4} = 2 \cdot 16 = 32 = 2^{5}$ ✅; and $2^{2 - 1} = 2 \neq = 8 = a_{2}$ confirming the original claim false. ✅

Coverage check

Recall Did we hit every cell?

A ::: Example 1 (single reach-back, one base). B ::: Example 2 (two predecessors, two bases, characteristic roots). C ::: Example 3 (uncontrolled split $n = ab$ , full history). D ::: Example 4 (jump-by-4 stamps, four bases). E ::: Example 5 (Fibonacci upper bound, boundary $F_{0}$ patched by two bases). F ::: Example 6 (lower bound + limiting squeeze $1. 5^{n - 2} \leq F_{n} < 2^{n}$ ). G ::: Example 7 (domino tiling word problem). H ::: Example 8 (too-few-base-cases exam trap, false formula).

Connections

Strong induction — the parent principle these examples drill.
Mathematical Induction (ordinary) — Example 1 shows a Cell-A case where ordinary induction already suffices.
Recurrence Relations — Examples 2, 5, 6, 7, 8 are all recurrences.
Prime Factorisation — Example 3 is the smallest brick of the Fundamental Theorem.
Well-Ordering Principle — an alternative engine for the same proofs.
Sequences & Series — closed forms of recursively defined sequences.

Worked examples — Strong induction

The scenario matrix

Example 1 — Cell A (single reach-back)

Example 2 — Cell B (two fixed predecessors) + a figure

Example 3 — Cell C (uncontrolled reach-back)

Example 4 — Cell D (jump-by- $d$ , here $d = 4$ ) — the stamps

Example 5 — Cell E (degenerate boundary) — a figure

Example 6 — Cell F (limiting behaviour) — a figure

Example 7 — Cell G (real-world word problem)

Example 8 — Cell H (exam twist: too few base cases → false "proof")

Coverage check

Connections

Concept Map