Strong induction and well-ordering

Ordinary induction steps from \(k\) to \(k + 1\). Sometimes that is not enough: to understand \(k + 1\) you may need several earlier cases, or a case far back. Factoring a number into primes is the standard example. To factor 60 you split it as \(6 \cdot 10\), and to factor those you need to know about 6 and 10, not about 59. Strong induction lets the inductive step use every earlier case at once. This lesson introduces strong induction, its close relative the well-ordering principle, and uses them to prove two foundations of number theory: every integer greater than 1 is a product of primes, and the division algorithm.

Strong induction

Principle of strong induction. Let \(P(n)\) be a statement about integers \(n \ge n_0\). Suppose that

• (base case) \(P(n_0)\) is true, and

• (inductive step) for every \(k \ge n_0\), if \(P(n_0), P(n_0 + 1), \dots, P(k)\) are all true, then \(P(k + 1)\) is true.

Then \(P(n)\) is true for every \(n \ge n_0\).

The only difference from ordinary induction is the inductive hypothesis, which is now 'all cases up to \(k\)' instead of 'case \(k\)'. Strong induction is no stronger as a logical principle: if you let \(Q(n)\) be the statement '\(P(n_0), \dots, P(n)\) are all true', then strong induction for \(P\) is ordinary induction for \(Q\). But it is often far more convenient, and many proofs that look hopeless with ordinary induction become easy.

Some strong induction proofs need more than one base case. If the inductive step for \(P(k + 1)\) uses \(P(k)\) and \(P(k - 1)\), then the step only makes sense once two earlier cases exist, so you must check two base cases directly. Always ask: for the smallest \(k\) where I apply the step, do all the cases it relies on actually exist and lie at or above \(n_0\)?

Every integer is a product of primes

Theorem. Every integer \(n \ge 2\) is a prime or a product of primes.

Proof. We use strong induction on \(n\). Base case: \(n = 2\) is prime. Inductive step: let \(k \ge 2\), and suppose every integer \(m\) with \(2 \le m \le k\) is a prime or a product of primes. Consider \(k + 1\). If \(k + 1\) is prime, we are done. Otherwise \(k + 1\) is composite, so \(k + 1 = ab\) for some integers \(a, b\) with \(2 \le a, b \le k\). By the inductive hypothesis, \(a\) and \(b\) are each a prime or a product of primes. Multiplying the two expressions shows that \(k + 1 = ab\) is a product of primes. By strong induction the theorem holds for every \(n \ge 2\). \(\blacksquare\)

Ordinary induction would have been useless here: knowing how to factor \(k\) tells you nothing about how to factor \(k + 1\), since \(k\) and \(k + 1\) share no prime factors. Strong induction lets us use the factorizations of \(a\) and \(b\), wherever they happen to lie below \(k + 1\).

This theorem gives the existence half of the fundamental theorem of arithmetic. The uniqueness half, that the factorization is unique apart from the order of the factors, needs Euclid's lemma and is proved in MATH-351. A corollary is the fact used in lesson 5 to prove there are infinitely many primes: every integer \(n \ge 2\) has at least one prime divisor.

Postage stamps

Theorem. Every amount of postage of 12 cents or more can be made using only 4-cent and 5-cent stamps.

Proof. Let \(P(n)\) be 'postage of \(n\) cents can be made from 4-cent and 5-cent stamps'. Base cases: \(12 = 4 + 4 + 4\), \(13 = 4 + 4 + 5\), \(14 = 4 + 5 + 5\) and \(15 = 5 + 5 + 5\). Inductive step: let \(k \ge 15\) and suppose \(P(m)\) holds for every \(m\) with \(12 \le m \le k\). Then \(k + 1 - 4 = k - 3\) satisfies \(12 \le k - 3 \le k\), so \(P(k - 3)\) holds. Adding one 4-cent stamp to postage for \(k - 3\) cents gives postage for \(k + 1\) cents. By strong induction, \(P(n)\) holds for every \(n \ge 12\). \(\blacksquare\)

The step jumps back four places, so it needs four base cases: for \(k + 1 = 16\) it uses 12, for 17 it uses 13, for 18 it uses 14, for 19 it uses 15, and from 20 on it uses cases already established by the step. Checking that the step only uses cases at or above 12 is exactly the check described above. The amount 11 cannot be made, which shows that 12 is the true starting point.

Fibonacci numbers

The Fibonacci numbers are defined by \(F_1 = 1\), \(F_2 = 1\) and \(F_{n} = F_{n-1} + F_{n-2}\) for \(n \ge 3\), giving 1, 1, 2, 3, 5, 8, 13, 21, 34, … Because each term depends on two earlier ones, statements about them are natural candidates for strong induction with two base cases.

A sharper bound is \(F_n \le \varphi^{n-1}\), where \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\) is the golden ratio. The proof is the same, using the identity \(\varphi^2 = \varphi + 1\). An exact formula, Binet's formula \(F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}\) with \(\psi = \frac{1 - \sqrt{5}}{2}\), can also be proved by strong induction, and MATH-221 derives it by diagonalizing a matrix.

The well-ordering principle

Well-ordering principle. Every non-empty set of natural numbers has a smallest element.

This sounds obvious, and for natural numbers it is part of what we mean by 'natural number'. It fails for other number systems: the integers have no smallest element, and neither does the set of positive rational numbers, since \(x/2\) is always smaller than \(x\). Well-ordering is logically equivalent to induction. One direction: suppose induction holds, and let \(S\) be a set of natural numbers with no smallest element. Let \(P(n)\) be 'none of \(1, \dots, n\) is in \(S\)'. \(P(1)\) holds, since otherwise 1 would be the smallest element of \(S\). If \(P(k)\) holds and \(k + 1\) were in \(S\), it would be the smallest element, so \(P(k + 1)\) holds. By induction \(S\) contains no natural number, so \(S\) is empty. Hence every non-empty set has a smallest element.

Well-ordering gives a style of proof called the method of the minimal counterexample, or infinite descent. To prove that \(P(n)\) holds for every \(n\), suppose not. Then the set of counterexamples is non-empty, so it has a smallest element \(m\). Use the fact that \(P\) holds for every number below \(m\) to derive a contradiction, usually by producing a smaller counterexample. Pierre de Fermat used infinite descent in the seventeenth century to prove that there are no positive integers with \(x^4 + y^4 = z^2\).

The division algorithm, proved

Lesson 4 used the division algorithm without proof. Here is the proof, which uses well-ordering for existence and a short argument for uniqueness.

Theorem. For every integer \(a\) and positive integer \(b\), there are unique integers \(q\) and \(r\) with \(a = bq + r\) and \(0 \le r < b\).

Proof of existence. Let \(S = \{a - bq : q \in \mathbb{Z} \text{ and } a - bq \ge 0\}\). First, \(S\) is non-empty: taking \(q = -|a|\) gives \(a - bq = a + b|a| \ge a + |a| \ge 0\), because \(b \ge 1\). The well-ordering principle applies to sets of non-negative integers as well (add 1 to every element), so \(S\) has a smallest element \(r = a - bq\) for some integer \(q\). By construction \(r \ge 0\). If \(r \ge b\), then \(r - b = a - b(q + 1)\) would be a smaller element of \(S\), contradicting the choice of \(r\). So \(0 \le r < b\) and \(a = bq + r\).

Proof of uniqueness. Suppose \(a = bq + r = bq\prime + r\prime\) with \(0 \le r, r\prime < b\). Then \(b(q - q\prime) = r\prime - r\). The right side satisfies \(-b < r\prime - r < b\), so \(b\,|q - q\prime| < b\), giving \(|q - q\prime| < 1\). Since \(q - q\prime\) is an integer, \(q = q\prime\), and then \(r = r\prime\). \(\blacksquare\)

Another descent proof

Well-ordering gives a second proof that \(\sqrt{2}\) is irrational, one that does not mention lowest terms. Suppose \(\sqrt{2}\) is rational. Then the set \(S = \{b \in \mathbb{N} : b\sqrt{2} \in \mathbb{Z}\}\) is non-empty, so it has a smallest element \(b\). Let \(a = b\sqrt{2}\), an integer. Consider \(b\prime = a - b = b(\sqrt{2} - 1)\). Since \(1 < \sqrt{2} < 2\), we have \(0 < b\prime < b\), and \(b\prime\) is an integer. But \(b\prime\sqrt{2} = 2b - a\) is also an integer, so \(b\prime \in S\) and \(b\prime < b\), contradicting the choice of \(b\). This is a model descent argument: a hypothetical smallest example produces an even smaller one.

Checking the patterns

The code below checks the postage theorem by building each amount from smaller ones, exactly as the strong induction step does, and confirms that 11 is the largest amount that cannot be made. It also factors numbers recursively, mirroring the proof that every integer at least 2 is a product of primes, and checks the Fibonacci bound and the golden ratio bound.

# postage with 4 and 5 cent stamps, built by the strong-induction step
can = {0: True}
for n in range(1, 80):
    can[n] = (n >= 4 and can[n - 4]) or (n >= 5 and can[n - 5])
print("amounts that cannot be made:", [n for n in range(1, 80) if not can[n]])

# recursive factorization, mirroring the proof
def factor(n):
    for a in range(2, int(n ** 0.5) + 1):
        if n % a == 0:
            return factor(a) + factor(n // a)   # both pieces are smaller than n
    return [n]                                  # no divisor: n is prime
for n in [60, 97, 360, 1001, 2 ** 10 - 1]:
    print(n, "=", " * ".join(map(str, factor(n))))

# Fibonacci bounds
F = [None, 1, 1]
for n in range(3, 60):
    F.append(F[-1] + F[-2])
phi = (1 + 5 ** 0.5) / 2
print("F_n < 2^n for n < 60:", all(F[n] < 2 ** n for n in range(1, 60)))
print("F_n <= phi^(n-1) for n < 60:", all(F[n] <= phi ** (n - 1) + 1e-9 for n in range(1, 60)))

amounts that cannot be made: [1, 2, 3, 6, 7, 11]
60 = 2 * 2 * 3 * 5
97 = 97
360 = 2 * 2 * 2 * 3 * 3 * 5
1001 = 7 * 11 * 13
1023 = 3 * 11 * 31
F_n < 2^n for n < 60: True
F_n <= phi^(n-1) for n < 60: True

The postage table is computed bottom-up, each value from values already found, which is exactly what strong induction justifies. Recursive programs and inductive proofs are two views of the same idea: a program that calls itself on smaller inputs terminates and is correct if the smallest cases are handled and each call reduces the problem.