Strong Induction

When One Earlier Case Is Not Enough

In ordinary induction, the step from $P(n)$ to $P(n+1)$ uses just the statement at $n$. Some problems do not have that structure. To prove a statement at $n+1$, we may need an earlier case such as $P(n-3)$, or we may need to split $n+1$ into factors that are both smaller than $n+1$. Strong induction is designed for these situations: in its step, we may assume every case from the starting index through $n$.

The extra assumptions do not make the proof circular. They apply only to earlier indices; the case being proved is $n+1$, which is not among them. The base cases begin the argument, and the step shows that those established cases collectively suffice to establish the next one.

Theorem (Strong Induction). Let $m\in\mathbb{N}_0$, and let $r$ be a positive integer. Suppose $P(n)$ is a statement for every integer $n\ge m$. If $P(m),P(m+1),\ldots,P(m+r-1)$ are true, and for every $n\ge m+r-1$ the statements $$ P(m),P(m+1),\ldots,P(n) $$ together imply $P(n+1)$, then $P(n)$ is true for every integer $n\ge m$.

Proof. Define $Q(n)$, for $n\ge m+r-1$, to be the statement that every $P(j)$ with $m\le j\le n$ is true. The assumed initial cases give $Q(m+r-1)$.

Now fix $n\ge m+r-1$ and assume $Q(n)$. By the definition of $Q(n)$, all of $P(m),P(m+1),\ldots,P(n)$ hold. The assumed strong inductive step therefore gives $P(n+1)$. Together with $Q(n)$, this proves that all cases from $m$ through $n+1$ hold; in other words, $Q(n+1)$ holds. The Principle of Mathematical Induction, applied starting at $m+r-1$, gives $Q(n)$ for every $n\ge m+r-1$. The initial cases already cover the indices from $m$ through $m+r-1$, so $P(n)$ holds for every $n\ge m$. $\square$

This proof reduces strong induction to the Principle of Mathematical Induction established earlier in this course. The integer $r$ makes explicit that a proof may need several initial cases. When $r=1$, the result is the usual strong induction principle with a single base case. When a recurrence or construction needs more than one starting value, choose a larger $r$ and verify each of those cases.

Worked Example: Every Integer at Least Two Is a Product of Primes

Worked Example: Factoring an Integer into Primes

A prime is an integer greater than $1$ whose only positive divisors are $1$ and itself. A composite integer is an integer greater than $1$ that is not prime. We prove that every integer $N\ge2$ can be written as a product of one or more primes.

Let $P(N)$ be the assertion that $N$ is a product of primes. At $N=2$, the number $2$ is prime, so it is a product consisting of the single prime $2$. This establishes the base case.

For the strong inductive step, fix $N\ge2$ and assume that every integer $j$ with $2\le j\le N$ is a product of primes. We show that $N+1$ is also a product of primes. If $N+1$ is prime, it is already such a product. If $N+1$ is composite, it has a factorization

$$ N+1=ab, $$

where $a$ and $b$ are integers satisfying $2\le a\le N$ and $2\le b\le N$. The upper bounds hold because $a$ and $b$ are proper factors of the composite number $N+1$. The inductive hypothesis applies to both factors, so each is a product of primes. Multiplying those two prime products expresses $N+1=ab$ as a product of primes. Thus $P(N+1)$ holds in either case, and strong induction proves the claim for every $N\ge2$.

The key point is that the factors need not be $N$; they may be any smaller integers in the established range. Ordinary induction, if used only in its one-case form, would not directly provide the factorization of both $a$ and $b$. Strong induction makes that information available.

Using More Than One Earlier Case

A recurrence that refers to the two preceding terms is a natural setting for strong induction. The step for the next value can use both earlier bounds, so the proof begins by checking enough cases to make both available.

Worked Example: A Bound for the Fibonacci Sequence

Define the Fibonacci sequence by $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ for integers $n\ge0$. We prove that

F_n\le 2^{n-1}\qquad\text{for every integer }n\ge1.

The starting cases are $F_1=1$ and $F_2=F_1+F_0=1$. They satisfy $F_1=1\le2^0=1$ and $F_2=1\le2^1=2$.

For the step, let $n\ge2$ and assume the bound holds for every integer $k$ from $1$ through $n$. In particular,

F_n\le2^{n-1} \qquad\text{and}\qquad F_{n-1}\le2^{n-2}.

The recurrence gives $F_{n+1}=F_n+F_{n-1}$, so adding the two bounds yields

F_{n+1} \le2^{n-1}+2^{n-2} =3\cdot2^{n-2} \le4\cdot2^{n-2} =2^n.

The penultimate inequality follows from $3\le4$ and $2^{n-2}>0$. Since $2^n=2^{(n+1)-1}$, this is the desired bound at $n+1$. Strong induction, with the two verified starting cases, proves the claim for every $n\ge1$.

The range in the hypothesis matters: when $n\ge2$, the index $n-1$ is at least $1$, so the assumed bound applies to $F_{n-1}$. Checking this lower endpoint prevents an unjustified use of the claim outside its stated range.

Worked Example: Making Amounts from Four- and Five-Unit Stamps

Worked Example: Representing Every Amount from Twelve Onward

We show that every integer $N\ge12$ can be written as $4a+5b$ for some nonnegative integers $a$ and $b$. This says that every such amount can be paid using stamps costing four or five units.

Check the four starting amounts:

12=4\cdot3+5\cdot0,\qquad 13=4\cdot2+5\cdot1, $$ $$ 14=4\cdot1+5\cdot2,\qquad 15=4\cdot0+5\cdot3.

For the step, let $N\ge15$ and assume every integer from $12$ through $N$ has the required representation. Since $N+1\ge16$, the integer $(N+1)-4=N-3$ satisfies $12\le N-3\le N$. The inductive hypothesis therefore gives nonnegative integers $a,b$ such that $N-3=4a+5b$. Adding one four-unit stamp gives

$$ N+1=(N-3)+4=4a+5b+4=4(a+1)+5b. $$

Both $a+1$ and $b$ are nonnegative integers, so this is a valid representation of $N+1$. Strong induction with the four starting cases proves the result for every integer $N\ge12$.

The four base cases are necessary for this particular step: subtracting $4$ repeatedly eventually reaches one of $12,13,14,15$. Starting with only $12$ would not establish $13$, $14$, or $15$, and the step from a known amount to the amount four units larger would not fill those gaps by itself.

Choosing the Hypothesis and Avoiding a Pitfall

Strong induction does not mean assuming every case, including the one being proved. At the step for $n+1$, the permitted assumptions are exactly the cases $P(m)$ through $P(n)$. The conclusion $P(n+1)$ must follow from them and the definitions or other established facts. If an argument needs $P(n+2)$, it has used a case that has not yet been proved.

A useful decision is whether the target case can be built from just its immediate predecessor. If so, ordinary induction may be simpler. If the argument must refer to a more distant earlier case, multiple earlier cases, or smaller components such as factors, strong induction often fits more directly. The strength lies in having the relevant earlier cases available, not in making the step less precise.

Set the range and starting cases.
Specify the first index and verify every initial case needed by the argument.

Fix the next index.
Choose an arbitrary $n$ in the step’s required range and state the target $P(n+1)$.

State the full hypothesis.
Assume $P(k)$ for each permitted index from the start through $n$, not for indices beyond $n$.

Identify the earlier cases used.
Check that each index needed by the recurrence, factorization, or construction lies in the assumed range.

Verify the exact target.
Show that the conclusion has the required form at $n+1$, then invoke strong induction.

Key takeaway. Strong induction proves each new case from all the earlier cases in the stated range. Its base cases must cover the starting values the step needs, and its inductive hypothesis must never include the case being proved.

Check Your Understanding

Use the strong induction principle and the examples above to answer the following questions.

In the proof about prime products, why are both factors $a$ and $b$ within the range covered by the inductive hypothesis?
Why are two starting cases used for the Fibonacci bound, and where is the condition $n\ge2$ needed?
In the stamp example, why does $N\ge15$ ensure that the earlier amount $N-3$ is at least $12$?
At the step for $P(n+1)$, which earlier cases may be assumed, and which case must still be proved?
How does the proof of the Strong Induction Theorem reduce its conclusion to ordinary induction?

What You'll Learn