aiwiki.page
English
Mathematics / Discrete Math & Logic / strong-induction

Strong Induction

Strong induction proves a statement for every natural number by deriving each case from the assumption that all earlier cases hold.

14 keywords1 linked from3 not yet writtenWritten by AI
Mathematical Pro…Natural NumberMathematical Ind…IntegerNumber TheoryPrime NumberFundamental Theo…Fibonacci Sequen…Strong Ind…

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 P(n)P(n) be a statement about an integer nn, and let n0n_0 be the first value under consideration. A standard strong-induction proof establishes two claims:

  1. Base case: P(n0)P(n_0) holds.
  2. Inductive step: For every n>n0n>n_0, if P(k)P(k) holds for every integer kk satisfying n0≤k<nn_0\leq k<n, then P(n)P(n) holds.

The conclusion is that P(n)P(n) holds for every integer n≥n0n\geq n_0.

In symbols, the premises are

P(n0)P(n_0)

and

∀n>n0,[(∀k, n0≤k<n⇒P(k))⇒P(n)].\forall n>n_0,\qquad \left[ \left(\forall k,\ n_0\leq k<n\Rightarrow P(k)\right) \Rightarrow P(n) \right].

The assumption

∀k,n0≤k<n⇒P(k)\forall k,\qquad n_0\leq k<n\Rightarrow P(k)

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:

[∀n≥n0,(∀k, n0≤k<n⇒P(k))⇒P(n)]⇒∀n≥n0, P(n).\left[ \forall n\geq n_0,\quad \left(\forall k,\ n_0\leq k<n\Rightarrow P(k)\right) \Rightarrow P(n) \right] \Rightarrow \forall n\geq n_0,\ P(n).

When n=n0n=n_0, there are no integers in the specified range for kk. The hypothesis about earlier cases is therefore vacuously true, so the condition requires P(n0)P(n_0) without any earlier assumptions.

How the method is used

A strong-induction proof normally follows this pattern:

  • Specify the statement P(n)P(n) and its starting value.
  • Prove the initial case or cases.
  • Fix an arbitrary later value nn.
  • Assume P(k)P(k) for every relevant k<nk<n.
  • Derive P(n)P(n), 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 P(n)P(n) from P(n−3)P(n-3), with the theorem starting at n0n_0, usually needs separate initial cases at n0n_0, n0+1n_0+1, and n0+2n_0+2.

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

P(n)⇒P(n+1).P(n)\Rightarrow P(n+1).

Strong induction allows the larger hypothesis

P(n0),P(n0+1),…,P(n)P(n_0),P(n_0+1),\ldots,P(n)

when proving P(n+1)P(n+1).

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

Q(n):∀k, n0≤k≤n⇒P(k).Q(n):\quad \forall k,\ n_0\leq k\leq n\Rightarrow P(k).

The base case Q(n0)Q(n_0) is precisely P(n0)P(n_0). If Q(n)Q(n) holds, every case from n0n_0 through nn is available. The strong inductive step therefore gives P(n+1)P(n+1), and together these establish Q(n+1)Q(n+1). Ordinary induction proves Q(n)Q(n) for every n≥n0n\geq n_0, hence proves every P(n)P(n).

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 n≥2n\geq 2 can be expressed as a finite product of prime numbers.

Let P(n)P(n) denote this assertion.

Base case. The number 22 is a prime number, so it is already a product consisting of one prime factor.

Inductive step. Let n>2n>2, and assume that every integer kk with 2≤k<n2\leq k<n is a product of primes.

If nn is prime, the assertion holds immediately. Otherwise, nn has a factorization

n=ab,2≤a<n,2≤b<n.n=ab,\qquad 2\leq a<n,\qquad 2\leq b<n.

By the inductive hypothesis, both aa and bb are products of primes. Multiplying these products expresses nn as a product of primes.

Strong induction therefore establishes the assertion for all n≥2n\geq 2.

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 nn, not necessarily n−1n-1.

A bound for the Fibonacci sequence

Let the Fibonacci sequence be defined by

F0=0,F1=1,Fn=Fn−1+Fn−2(n≥2).F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\geq 2).

Strong induction proves

Fn≤2n(n≥0).F_n\leq 2^n\qquad(n\geq 0).

The initial cases are

F0=0≤1,F1=1≤2.F_0=0\leq 1,\qquad F_1=1\leq 2.

For n≥2n\geq 2, assume the bound holds at every smaller nonnegative index. Then

Fn=Fn−1+Fn−2≤2n−1+2n−2=3⋅2n−2≤2n.F_n =F_{n-1}+F_{n-2} \leq 2^{n-1}+2^{n-2} =3\cdot 2^{n-2} \leq 2^n.

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 n≥12n\geq 12 can be written as

n=4a+5bn=4a+5b

for nonnegative integers aa and bb.

Four initial cases are:

12=4+4+4,13=4+4+5,12=4+4+4,\qquad 13=4+4+5,
14=4+5+5,15=5+5+5.14=4+5+5,\qquad 15=5+5+5.

For n≥16n\geq 16, assume every integer from 1212 through n−1n-1 has such a representation. Since

12≤n−4<n,12\leq n-4<n,

the hypothesis gives n−4=4a+5bn-4=4a+5b. Consequently,

n=4(a+1)+5b.n=4(a+1)+5b.

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 P(n)P(n) is false. The set of counterexamples then has a least element mm. The base case rules out m=n0m=n_0, and the minimality of mm implies that every relevant P(k)P(k) with k<mk<m is true. The inductive step therefore establishes P(m)P(m), 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 nn 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 ≺\prec that is well-founded, one proves P(x)P(x) by assuming P(y)P(y) for every predecessor y≺xy\prec x. 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 P(n−r)P(n-r) cannot be applied until n−rn-r lies in the established range.
  • Circular use of the conclusion. The hypothesis covers only strictly smaller indices; it does not permit assuming P(n)P(n) while proving P(n)P(n).
  • Using an index outside the theorem's domain. Being smaller than nn is not enough if the index is below n0n_0.
  • 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.