Strong Induction

From Ordinary Induction to Strong Induction

Ordinary induction proves a statement $P(n)$ by showing that truth passes from one case to the next:

This is enough for many arguments. In number theory, however, the proof of $P(k+1)$ often requires more than the immediately preceding case. It may require several earlier cases, or even all earlier cases.

Strong induction is designed for this situation.

Instead of assuming only $P(k)$, one assumes

and uses all of these statements to prove $P(k+1)$.

The Principle of Strong Induction

Let $P(n)$ be a statement depending on a natural number $n$. Suppose that:

1. $P(1)$ is true.
2. For every $k\in\mathbb{N}$, if $P(1),P(2),\ldots,P(k)$ are all true, then $P(k+1)$ is true.

Then $P(n)$ is true for every $n\in\mathbb{N}$.

The assumption that all earlier statements are true is called the strong induction hypothesis.

Although strong induction looks more powerful than ordinary induction, the two principles are logically equivalent. Strong induction is often more convenient because arithmetic problems naturally break into smaller cases of different sizes.

Why Strong Induction Works

Strong induction works for the same reason ordinary induction works: the natural numbers are well ordered.

Suppose the statement fails for at least one natural number. Then the set of counterexamples is nonempty. By the well-ordering principle, it has a least element, say $m$.

The base case shows that $m\ne1$. Therefore $m>1$. Since $m$ is the least counterexample, all statements

are true. The strong induction step then implies that $P(m)$ is true. This contradicts the choice of $m$.

Hence no counterexample exists, and the statement holds for every natural number.

A Basic Example

We prove that every integer $n\ge2$ is either prime or can be written as a product of primes.

Let $P(n)$ be the statement:

For $n=2$, the statement is true because $2$ is prime.

Now assume that $P(2),P(3),\ldots,P(k)$ are true for some $k\ge2$. We prove $P(k+1)$.

If $k+1$ is prime, then $P(k+1)$ is true.

If $k+1$ is not prime, then it is composite. Hence there exist integers $a,b$ such that

where

and

By the strong induction hypothesis, both $a$ and $b$ are prime or products of primes. Therefore their product $ab$ is also a product of primes. Since

it follows that $k+1$ is a product of primes.

Thus, by strong induction, every integer $n\ge2$ is prime or a product of primes.

Strong Induction and Divisibility

Strong induction is especially useful when a number is reduced by division rather than by subtracting one.

For example, suppose a proof about $n$ requires considering a proper divisor $d$ of $n$. Such a divisor need not be $n-1$. It may be much smaller. Ordinary induction gives information only about $n-1$, while strong induction gives information about all smaller positive integers.

This is why strong induction appears naturally in proofs about factorization, greatest common divisors, Euclidean algorithms, and recursive arithmetic procedures.

Induction from an Arbitrary Starting Point

Strong induction can begin at any integer $n_0$. Suppose $P(n)$ is intended to hold for all integers $n\ge n_0$. It is enough to prove:

1. $P(n_0)$ is true.
2. For every $k\ge n_0$, if $P(n_0),P(n_0+1),\ldots,P(k)$ are true, then $P(k+1)$ is true.

Then $P(n)$ holds for all $n\ge n_0$.

This version is often used when the first few values behave differently from the general case.

Strong Induction and Minimal Counterexamples

Many strong induction proofs can be written as minimal counterexample arguments.

To prove a statement for all natural numbers, assume there is a counterexample. Choose the smallest counterexample $m$. Then all smaller cases are true. Use those smaller cases to prove the statement for $m$, obtaining a contradiction.

This method is common in number theory because the well-ordering principle gives immediate access to the least counterexample.

For instance, the existence of prime factorization can also be proved this way. Suppose some integer $n\ge2$ cannot be written as a product of primes. Let $m$ be the least such integer. Then $m$ cannot be prime, so

with

By minimality of $m$, both $a$ and $b$ have prime factorizations. Hence $m=ab$ also has a prime factorization, a contradiction.

Therefore every integer $n\ge2$ has a prime factorization.

Role in Number Theory

Strong induction is one of the main proof tools in elementary and modern number theory. It is used whenever an integer is analyzed through smaller integers whose sizes are not fixed in advance.

Prime factorization, Euclidean algorithms, recursive definitions, divisibility arguments, and many Diophantine methods rely on this form of reasoning.

The central idea is simple: to prove a statement about $n$, one may use the truth of the statement for every smaller positive integer. This matches the arithmetic habit of reducing a difficult number to simpler pieces.