##### Theorem5.4.1

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

The strong form of mathematical induction (a.k.a. the principle of complete induction, PCI; also a.k.a. course-of-values induction) 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 \begin{equation*} \forall k (P_0 \land P_1 \land \ldots \land P_{k-1}) \implies P_k. \end{equation*}

An outline of a strong inductive proof is:

\begin{minipage}{.75\textwidth}
Theorem \(\displaystyle \forall n \in \Naturals, \; P_n\)
Proof: (By complete induction)
Basis:
\(\vdots\) \begin{minipage}[c]{1.7 in} (Technically, a PCI
proof doesn't require a basis. We recommend that you show that \(P_0\)
is true anyway.)
Inductive step:
\(\vdots\) \begin{minipage}[c]{1.7 in} (Here we must show that \(\forall k, \left( \bigwedge_{i=0}^{k-1} P_i \right) \implies P_{k}\) is true.)
Q.E.D. |

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.

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

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\)\cents stamps and \(7\)\cents stamps, show (using strong induction) that any postage value \(12\)\cents or higher can be achieved. That is, \begin{equation*} \forall n \in \Naturals, n \geq 12 \; \implies \; \exists x,y \in \Naturals , n = 3x + 7y. \end{equation*}

Show that any integer postage of \(12 \cents\) or more can be made using only \(4\cents\) and \(5\cents\) 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\).