# Section5.4The strong form of mathematical induction

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.

# Subsection5.4.1Exercises

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$\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*}

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