Strong induction is a method of mathematical proof used to establish a statement for every natural number, or for every integer above a specified starting value. In the inductive step, the statement may be assumed true for all smaller values in the relevant range, rather than only for the immediately preceding value. Despite its name, strong induction is logically equivalent to ordinary mathematical induction in the standard setting of natural-number arithmetic. Its advantage is that its hypothesis often fits the structure of a problem more directly.
Principle and formal statement
Let be a statement about an integer , and let be the first value under consideration. A standard strong-induction proof establishes two claims:
- Base case: holds.
- Inductive step: For every , if holds for every integer satisfying , then holds.
The conclusion is that holds for every integer .
In symbols, the premises are
and
The assumption
is the strong inductive hypothesis. It makes every earlier case available, but a particular proof may use only one or two of them.
An equivalent formulation incorporates the base case into a single condition:
When , there are no integers in the specified range for . The hypothesis about earlier cases is therefore vacuously true, so the condition requires without any earlier assumptions.
How the method is used
A strong-induction proof normally follows this pattern:
- Specify the statement and its starting value.
- Prove the initial case or cases.
- Fix an arbitrary later value .
- Assume for every relevant .
- Derive , checking that every application of the hypothesis uses a strictly smaller index within the stated range.
Several base cases may be needed when the inductive step refers back by more than one position. For example, a step that establishes from , with the theorem starting at , usually needs separate initial cases at , , and .
The hypothesis is temporary and conditional. The proof does not assume that the desired theorem already holds for all numbers. Instead, it proves that whenever all earlier cases hold, the next case follows. The induction principle then licenses the universal conclusion.
Equivalence to ordinary induction
Ordinary induction generally uses the step
Strong induction allows the larger hypothesis
when proving .
This gives more information within the inductive step, but it does not give a stronger overall proof principle.
To derive strong induction from ordinary induction, define the cumulative statement
The base case is precisely . If holds, every case from through is available. The strong inductive step therefore gives , and together these establish . Ordinary induction proves for every , hence proves every .
Conversely, ordinary induction follows from strong induction because the strong hypothesis includes the immediately preceding case. If that one case is sufficient, the other assumptions can simply remain unused.
Thus, choosing between the two methods is principally a matter of matching the proof's hypothesis to the dependencies of the statement.
Examples
Existence of prime factorizations
A standard example from number theory is the statement:
Every integer can be expressed as a finite product of prime numbers.
Let denote this assertion.
Base case. The number is a prime number, so it is already a product consisting of one prime factor.
Inductive step. Let , and assume that every integer with is a product of primes.
If is prime, the assertion holds immediately. Otherwise, has a factorization
By the inductive hypothesis, both and are products of primes. Multiplying these products expresses as a product of primes.
Strong induction therefore establishes the assertion for all .
This proves the existence part of the fundamental theorem of arithmetic. It does not prove uniqueness, which requires a separate argument. Strong induction is natural here because the relevant smaller numbers are factors of , not necessarily .
A bound for the Fibonacci sequence
Let the Fibonacci sequence be defined by
Strong induction proves
The initial cases are
For , assume the bound holds at every smaller nonnegative index. Then
Only two earlier cases are used, but the strong inductive hypothesis makes both available. This is typical of proofs involving a recurrence relation. The same proof could also be organized as ordinary induction on a statement containing two consecutive bounds.
Representation by two denominations
Every integer can be written as
for nonnegative integers and .
Four initial cases are:
For , assume every integer from through has such a representation. Since
the hypothesis gives . Consequently,
Here the four base cases supply the starting points needed for a step that moves backward by four.
Well-ordering and least counterexamples
Strong induction is closely connected to the well-ordering principle: every nonempty subset of the natural numbers has a least element.
A classical proof by contradiction explains the connection. Suppose the base case and strong inductive step hold, but some is false. The set of counterexamples then has a least element . The base case rules out , and the minimality of implies that every relevant with is true. The inductive step therefore establishes , contradicting its selection as a counterexample.
This is often called a least-counterexample argument. In standard classical treatments of arithmetic, ordinary induction, strong induction, and well-ordering are equivalent formulations over suitable background assumptions. The direct cumulative-statement proof of equivalence between the two forms of induction does not require a least-counterexample argument.
Applications and generalizations
Strong induction is particularly useful when an object of size is reduced to smaller objects whose sizes vary. Examples include factorization arguments, recursively defined sequences, and correctness proofs for a recursive algorithm.
In algorithmic applications, input size can serve as the induction parameter: correctness on all smaller inputs is used to prove correctness on the current input. Such an argument must also justify that recursive calls decrease the chosen measure and that the base cases are handled.
The broader principle is well-founded induction. Given a relation that is well-founded, one proves by assuming for every predecessor . Strong induction is the special case using the usual strict order on natural numbers.
Structural induction organizes proofs around the construction of recursively generated objects, such as expressions or finite trees. It is closely related, though its inductive hypotheses concern component structures rather than necessarily all objects with smaller numerical indices.
Common errors and scope
Several mistakes can invalidate a strong-induction argument:
- Missing initial cases. A step using cannot be applied until lies in the established range.
- Circular use of the conclusion. The hypothesis covers only strictly smaller indices; it does not permit assuming while proving .
- Using an index outside the theorem's domain. Being smaller than is not enough if the index is below .
- Leaving values uncovered. A step advancing by a fixed amount needs enough starting cases to reach every intended value.
Strong induction applies directly to natural numbers and to integer ranges with a least starting value. It does not apply unchanged to all integers under their usual order, or to real numbers under the usual strict order: those orders are not well-founded. Extensions to other domains require an appropriate well-founded relation or a different induction principle.