Strong Induction - Induction

Mathematical Writing - Vivaldi Franco 2014

Strong Induction
Induction

In an induction proof, the successful completion of the inductive step rests on the assumption that to prove $${\fancyscript{P}}(k+1)$$ we only need $${\fancyscript{P}}(k)$$. Should we instead (or in addition) need $${\fancyscript{P}}(k-1)$$, then this method would collapse.

This situation is not unusual. Suppose we want to prove by induction that every integer is a product of prime numbers. To prove that this statement is true for, say, $$k+1=12$$, the preceding case $$k=11$$ is of no use. We would need instead $$k=3$$ and $$k=4$$.

The rescue is a form of induction called strong induction (or complete induction), which is formulated as follows:

($$D$$) If $${\fancyscript{P}}$$ is a predicate over $$\mathbb {N}$$ such that

i)

ii)

As with Peano’s induction, the base case of strong induction can be any integer, and there is an equivalent formulation in terms of sets:

($$D^\prime $$) If $$S$$ is a subset of $$\mathbb {N}$$ such that

i)

ii)

Strong induction follows from Peano’s induction ($$(C)\Rightarrow (D)$$), since the latter has fewer conditions. (One could say that induction is stronger than strong induction!)

In Sect. 8.1 we proved that every integer greater than 1 is a product of one or more primes by combining well-ordering with contradiction; we now prove the same statement using strong induction. The two proofs employ two variants of the same argument, giving a tangible illustration of the equivalence of well-ordering and strong induction.

PROOF. We use strong induction. The integer 2 is prime, which establishes the base case. Suppose that for some $$k>1$$ every integer $$n$$ with $$1<n\leqslant k$$ is a product of primes, and consider $$k+1$$. If $$k+1$$ is prime, then there’s nothing to prove. If $$k+1$$ is not a prime then there are integers $$m,n$$ such that $$mn=k+1$$ and $$1<m,n\leqslant k$$. By the induction hypothesis, $$m$$ and $$n$$ are products of primes, and hence so is $$k+1$$. We have completed the inductive step. $$\square $$

With the help of strong induction, Euclid’s elegant proof of the infinitude of primes (Sect. 7.5) yields an upper bound (or an estimate) for the $$n$$th prime number.

Theorem 8.1

For all $$n\geqslant 1$$, the $$n$$th prime $$p_n$$ satisfies the upper bound $$p_n\leqslant 2^{2^{n-1}}$$.

PROOF. We use strong induction. The base case is clear: $$p_1=2\leqslant 2^{2^{0}}=2$$. Assuming that for some $$k\geqslant 1$$ we have $$p_j\leqslant 2^{2^{j-1}}$$ for $$j=1,2,\ldots k$$, we have

$$\begin{aligned} p_{k+1}&\leqslant 1+\prod _{j=1}^kp_j \leqslant 1+\prod _{j=1}^k2^{2^{j-1}}\\&= 1+2^{\sum \limits _{j=1}^{k}2^{j-1}}=1+2^{2^k-1}<2^{2^k} \end{aligned}$$

where the first inequality follows from Euclid’s argument (the right-hand side is divisible by a prime greater than $$p_k$$, see (7.7)), while the second inequality follows from the induction hypothesis. The proof is complete. $$\square $$

To complete the proof that the four formulations of the induction principle are equivalent, it remains to show that well-ordering follows from strong induction ($$(D)\Rightarrow (A)$$). When this is done, we will have proved that

$$ (A)\,\Leftrightarrow \, (B)\qquad \mathrm{and}\qquad (A)\,\Rightarrow \, (C)\,\Rightarrow \, (D)\,\Rightarrow \, (A) $$

and equivalence follows from a loop of implications (cf. Sect. 7.4.1).

We use the both ends method. Assume that strong induction holds but that there is a non-empty subset $$S$$ of $$\mathbb {N}$$ without a least element. Let $$S^{\,\prime }=\mathbb {N}{\backslash }S$$. Then $$1\in S^{\,\prime }$$, for otherwise 1 would be the least element of $$S$$. Likewise, if for some $$k\geqslant 1$$ we have $$\{1,\ldots ,k\}\subset S^{\,\prime }$$, then we must also have $$k+1\in S^{\,\prime }$$, because otherwise $$k+1$$ would be the smallest element of $$S$$. Hence, from strong induction, we have that $$S^{\,\prime }=\mathbb {N}$$, and hence $$S=\emptyset $$, contradicting the hypothesis $$S\not =\emptyset $$.