Strong Induction is the habit of using all previous cases, not just the immediately previous case, to prove the next one. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
No tagged problems yet We are still curating launch-ready practice for this technique.
The Key Result
$$\big(P(1),\dots,P(k)\text{ all true}\big)\Rightarrow P(k+1) \;\;\Longrightarrow\;\; P(n)\ \text{true } \forall n.$$
Like ordinary induction, but the step may lean on every earlier case at once, not just the one immediately before — essential when a value is built from cases far back.
Why It Works
1
Establish the needed base case(s) directly — sometimes more than one is required for the step to reach back.
2
Inductive hypothesis: assume $P(m)$ holds for all $m$ with $1 \le m \le k$.
3
Inductive step: prove $P(k+1)$ using whichever earlier cases you need, even ones well before $P(k)$.
4
Because every case below $k+1$ is available, recurrences or factorizations that jump backward are fully supported.
Worked Examples
Example 1
Every integer $n \ge 2$ can be written as a product of one or more prime numbers. Prove it.
1
Base case $n = 2$: $2$ is prime, so it is a product of one prime.
2
Assume the claim for all integers $m$ with $2 \le m \le k$.
3
Consider $n = k+1$. If it is prime, we are done. Otherwise $n = a \cdot b$ with $2 \le a, b \le k$.
4
By the strong hypothesis both $a$ and $b$ are products of primes, so their product $n$ is too; by strong induction every $n \ge 2$ factors into primes.
Answer:
Every integer $\ge 2$ is a product of primes (existence half of the Fundamental Theorem of Arithmetic).
Contest level
Stamps come in only $4$-cent and $5$-cent denominations. Prove that every postage amount of $12$ cents or more can be made exactly using these stamps.
1
Base cases: $12 = 4+4+4$, $13 = 4+4+5$, $14 = 4+5+5$, $15 = 5+5+5$. Four consecutive bases are needed because the step reaches back by $4$.
2
Inductive hypothesis: assume every amount $m$ with $12 \le m \le n$ (for some $n \ge 15$) can be made.
3
For $n + 1 \ge 16$ we have $(n+1) - 4 = n - 3 \ge 12$, so by the hypothesis the amount $n - 3$ can be made.
4
Add one more $4$-cent stamp to that arrangement to make $n + 1$. By strong induction every amount $\ge 12$ is achievable.
Answer:
Every postage amount of $12$ cents or more is exactly makeable with $4$- and $5$-cent stamps.
Olympiad / Challenge
A sequence is defined by $a_1 = 1$, $a_2 = 3$, and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 3$. Prove that $a_n = \dfrac{2^{n+1} + (-1)^n}{3}$ for every positive integer $n$.
1
Two base cases (the recurrence looks back two steps): $a_1 = \frac{2^2 + (-1)^1}{3} = \frac{4 - 1}{3} = 1$ ✓ and $a_2 = \frac{2^3 + (-1)^2}{3} = \frac{8 + 1}{3} = 3$ ✓.
2
Strong hypothesis: assume the formula holds for $n - 1$ and $n - 2$ (both needed, which is why ordinary one-step induction will not do).
Since $(-1)^{n-2} = (-1)^n$ and $(-1)^{n-1} = -(-1)^n$, the sign part is $-(-1)^n + 2(-1)^n = (-1)^n$, giving $a_n = \frac{2^{n+1} + (-1)^n}{3}$, as required.
Answer:
$a_n = \dfrac{2^{n+1} + (-1)^n}{3}$ for all $n \ge 1$.
Going Deeper
Strong induction is the natural tool whenever a value depends on more than just its immediate predecessor — factorizations $n = ab$, linear recurrences $a_n = a_{n-1} + 2a_{n-2}$, and game positions that branch into several earlier states.
It underlies prime factorization, the validity of the Euclidean algorithm, well-ordering arguments, and the analysis of Nim-like games on AIME/olympiad — anywhere a problem reduces to strictly smaller, but not necessarily adjacent, cases.
Pitfall: provide enough base cases to anchor every backward reach. A step that uses the two previous terms needs two bases; the postage step reaches back $4$ and needs four — too few bases leaves a gap the induction cannot cross.
Spot the Signal
Look for problems where the key step is using all previous cases, not just the immediately previous case, to prove the next one.
You can describe the hard part as using all previous cases, not just the immediately previous case, to prove the next one, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the problem-solving bottleneck that calls for strong induction, then rewrite the givens around it.
Name the relation that makes Strong Induction legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Strong Induction just because the surface looks familiar; verify the required condition first.
Applying Strong Induction because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let strong induction reveal the strategic structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is using all previous cases, not just the immediately previous case, to prove the next one.