5.4 The strong form of mathematical induction

The strong form of mathematical induction (a.k.a. the principle of complete induction, PCI) is so-called because the hypotheses one uses are stronger. Instead of showing that \(P_k \implies P_{k+1}\) in the inductive step, we get to assume that all the statements numbered smaller than \(P_{k+1}\) are true. To make life slightly easier, we’ll renumber things a little. The statement that needs to be proved is

\[ \forall k (P_0 \land P_1 \land \ldots \land P_{k-1}) \implies P_k. \]

Below is an outline for a strong inductive proof of \(\forall n \in {\mathbb N},\; P_n\):

(By complete induction)

Basis: \[\begin{array}{ll} \vdots ~~~~~~~~~~& (\text{Technically, a basis is not required in a} \\ & \text{PCI proof. But we recommend having one.}) \\ & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \\ \end{array}\]

Inductive step: \[\begin{array}{ll} \vdots ~~~~~~~~~~& (\text{Here we establish } \forall k, \left( \bigwedge_{i=0}^{k-1} P_i \right) \implies P_{k}.) \\ & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \\ \end{array}\] By the principle of complete induction, \(P_n\) is true for every \(n \in {\mathbb N}.\)

 

It’s fairly common that we won’t truly need all of the statements from \(P_0\) to \(P_{k-1}\) to be true, but just one of them (and we don’t know a priori which one). The following is a classic result; the proof that all numbers greater than 1 have prime factors.

Theorem 5.10 For all natural numbers \(n\), \(n > 1\) implies \(n\) has a prime factor.

Proof. (By strong induction) Consider an arbitrary natural number \(n>1\). If \(n\) is prime, then \(n\) clearly has a prime factor (itself). So suppose that \(n\) is not prime. By definition, a composite natural number can be factored, so \(n=a \cdot b\) for some pair of natural numbers \(a\) and \(b\) which are both greater than 1. Since \(a\) and \(b\) are factors of \(n\) both greater than 1, it follows that \(a < n\) (it is also true that \(b < n\) but we don’t need that ). The inductive hypothesis can now be applied to deduce that \(a\) has a prime factor \(p\). Since \(p \mid a\) and \(a \mid n\), by transitivity \(p \mid n\). Thus \(n\) has a prime factor.

5.4.1 Exercises

Give inductive proofs of the following

  1. A “postage stamp problem” is a problem that (typically) asks us to determine what total postage values can be produced using two sorts of stamps. Suppose that you have \(3\)¢ stamps and \(7\)¢ stamps, show (using strong induction) that any postage value \(12\)¢ or higher can be achieved. That is, \[ \forall n \in {\mathbb N}, n \geq 12 \; \implies \; \exists x,y \in {\mathbb N}, n = 3x + 7y. \]

  2. Show that any integer postage of \(12\)¢ or more can be made using only \(4\)¢ and \(5\)¢ stamps.

  3. The polynomial equation \(x^2 = x+1\) has two solutions, \(\alpha = \frac{1+\sqrt{5}}{2}\) and \(\beta = \frac{1-\sqrt{5}}{2}\). Show that the Fibonacci number \(F_n\) is less than or equal to \(\alpha^{n}\) for all \(n \geq 0\).