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.
5.4.1 Exercises
Give inductive proofs of the following
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. \]
Show that any integer postage of \(12\)¢ or more can be made using only \(4\)¢ and \(5\)¢ stamps.
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\).