Strong induction ($P(n_0),[\forall k\in \{n_0,\dots ,n\},P(k)]\Rightarrow P(n+1)$)

Strong induction establishes a proposition $P(n)$ for all integers $n\ge n_0$. Prove $P(n_0)$; then, for each $n\ge n_0$, assume every $P(k)$ with $n_0\le k\le n$ and prove $P(n+1)$. The induction hypothesis includes all earlier cases, so the inductive step can use whichever smaller indices it needs. It cannot use $P(n+1)$ itself.^[ref]

This is useful when a construction breaks into smaller pieces of varying sizes. A prime factorization splits a composite number into smaller integer divisors, which need not be one less than the original integer. A recursive procedure can likewise call itself on several smaller inputs. The available cases should match those dependencies. Strong induction lets the mathematical proof follow the construction rather than forcing every step through the immediately preceding size.

Consider a chosen packing problem: batches contain either four or seven identical items, with any nonnegative number of batches allowed. Which integer totals can be formed? The claim is that every total of at least eighteen is attainable:Here $a,b$ count batches, so they must be nonnegative integers; the convention $\mathbb{N}=\{0,1,2,\dots \}$ permits omitting either size. Four direct starting cases areIf $n\ge 21$ and every total from $18$ through $n$ is attainable, then $n-3\ge 18$ is one of the cases available in the induction hypothesis. Add a batch of four to its representation to obtain $n+1$. Thus the inductive step applies to every new total from $22$ onward. Formally, one can start the strong induction at $18$ and handle the next three totals directly before using the uniform step. The finite checks and the propagation together establish all totals, not merely those drawn below.

Checking only $18$ and repeatedly adding four would reach only totals congruent to $18$ in modular arithmetic modulo four. The four induction base cases supply all four residue classes. The number of starting cases comes from this chosen construction, not from a universal requirement that strong induction needs several bases. A different construction can need different starting information.

The threshold is sharp for these batch sizes. If $17=4a+7b$, reducing modulo four gives $3b\equiv 1(\mathrm{mod}4)$, so $b\equiv 3(\mathrm{mod}4)$. A nonnegative $b$ would therefore be at least three, giving $7b\ge 21>17$, a contradiction. A finite failed search alone would need an explicit bound on $a,b$; this short modular arithmetic argument supplies a general obstruction.

Every integer $n\ge 2$ has a prime factorization. The induction base case $2$ is prime. For a larger integer, either it is prime or it is $ab$, with $2\le a,b<n$. The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for $n$. This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.^[ref]

For the chosen number $84$, one possible recursive decomposition isThe step at $84$ needs results for $6$ and $14$, rather than a result for $83$. Each composite number in this factorization tree splits into strictly smaller positive integers, so recursive descent terminates at prime numbers. The tree describes one construction; another choice of integer divisors can give a differently shaped factorization tree.

The same pattern explains the usefulness of strong induction for algorithm correctness. When a recursive procedure returns answers for smaller inputs, the induction hypothesis can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a nonnegative integer size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an algorithm correct.

Strong induction does not prove more than ordinary mathematical induction. Put $Q(n)={\bigwedge }_{k=n_0}^{n}P(k)$. Ordinary mathematical induction on $Q$ retains the earlier cases and obtains the next one, establishing the same conclusion. Conversely, an ordinary inductive step can ignore the extra cases allowed in a strong induction hypothesis.^[ref]

The well-ordering principle gives another view. A least counterexample would have all smaller cases true, so the strong induction step would establish that allegedly false case. The starting case excludes the beginning.