Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

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.

Proof

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\).