\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\newtheorem{method}{Method}

\begin{document}
\lecturenotes{2}{Induction}

\section{Proof by Induction}

\subsection{The Induction Axiom}

Induction is by far the most powerful and commonly-used proof
technique in Discrete Mathematics and Computer Science.  In fact, one
could say that applicability of induction is the defining
characteristic of \emph{discrete}, as opposed to \emph{continuous},
Mathematics.

The standard formulation of induction involves proving properties of
the natural numbers, $\naturals \eqdef 0,1,2, \dots$.  But since most
objects of interest in Computer Science---computer programs, task
schedules, game outcomes, steps in a computation---can be
numbered\footnote{A variant of induction, called \emph{structural
induction}, is specially tailored for proof about recursively defined
data structures and processes; structural induction will be discussed
in later notes.}, induction applies widely.

Induction captures a style of reasoning which is so obvious and
familiar that its use often goes unnoticed.  For example, suppose we
had some recipe for assigning a unique ``color'' to every natural
number.  One recipe might, for example, assign red to even numbers and
blue to odd numbers.  Another recipe would be to color even numbers
red, odd prime numbers blue, and all other numbers white.  Now suppose
someone formulates a recipe for natural number coloring, but doesn't
tell you exactly what the recipe is.  But they do tell you that zero
is colored red, and that the coloring has the property that, whenever
some number is red, then the next number is red.  Can there be any
doubt about what the unknown coloring is?  Of course not: \emph{every}
number is colored red!

The Axiom of Induction essentially just this: if zero is red, and the
next number after a red number is also red, then all numbers are red.
So the Induction Axiom is both simple and obvious.  What's not so
obvious is how much mileage we get by using it.  For example, let's
prove by induction that

\begin{equation}\label{sumn}
1 + 2 + \cdots + n + (n+1) = \frac{(n+2)(n+1)}{2},
\end{equation}

for all $n \in \naturals$.  The trick for applying induction is to use
this equation for assigning colors to numbers: color the number $n$ red
when equation~(\ref{sumn}) holds, otherwise color it white.  To verify
that equation~(\ref{sumn}) holds for all $n \in \naturals$, we must show
that every number is red.  Induction allows us to prove this using simple
arithmetic.

To begin with, we have to show that zero is red.  In other words, we have
to show that zero satisfies equation~(\ref{sumn}).  Now when $n=0$, the
lefthand side of the equation is simply 1 and the righthand side is
$(0+2)(0+1)/2$, which equals 1.  So zero is red.

Next, we suppose we have arrived at some natural number, $m$, which is
colored red.  We only have to show that the next number, $m+1$, must also
be red.  Then by induction all natural numbers are red.  That is,
equation~(\ref{sumn}) holds for all $n \in \naturals$.

Now in this case, saying that $m$ is red means
\begin{equation}\label{summ}
1 + 2 + \cdots + m + (m+1) = \frac{(m+2)(m+1)}{2}.
\end{equation}
This is called the \emph{induction hypothesis}.

How do we show the next number, $m+1$, is red?  We have to show:
\begin{equation}\label{summ1}
1 + 2 + \cdots + (m+1) + ((m+1)+1) = \frac{((m+1)+2)((m+1)+1)}{2}.
\end{equation}
But that's easy using the redness of $m$ and rules of arithmetic:
\begin{align*}
1 + 2 + \cdots + (m+1) + ((m+1)+1) = &  [1 + 2 + \cdots + (m+1)] + (m+2)\\
= &  [1 + 2 + \cdots + (m+1)] + (m+2) & \text{(associativity of $+$)}\\
= & \frac{(m+2)(m+1)}{2} + (m+2) & \text{(by~(\ref{summ}))}\\
=& (\frac{m+1}{2} +1)(m+2)\\
=& (\frac{m+1}{2} + \frac{2}{2})(m+2)\\
=& \frac{(m+1) +2}{2}(m+2)\\
=& \frac{((m+1)+2)((m+1)+1)}{2}.
\end{align*}
Here associativity for sums tells us it's ok to parenthesize the sum in
any convenient way, and the unlabelled equalities each follow by simple
arithmetic.  So we have finished the proof by induction that~(\ref{summ})
holds for all $n \in \naturals.$

The Induction Axiom is usually stated formally using logical formulas.  To
begin with, let's consider some fixed coloring, and interpret the
predicate $P(n)$ to mean that ``$n$ is colored red.''  Then we translate
our informal language in logical formulas as follows: ``we have a coloring
that makes zero red'' simply translates into $P(0)$.  The clause
``whenever some number is red, then the next number is red,'' translates
first into ``whenever some number, call it, $m$, satisfies $P(m)$, then
$P(m+1)$.''  We can translate the ``whenever some number $m$'' phrase into
a universal quantifier and the ``if \dots then'' into $\implies$, so the
whole phrase translates into
\[
\forall m \in \naturals\ P(m) \implies P(m+1).
\]
The conclusion that ``every number is colored red'' translates into
$\forall n\; P(n)$.  So now we can formally state the
\begin{axiom*}
[Induction] Suppose that $P(0)$ is true and
\[
\forall m \in \naturals\ P(m) \implies P(m+1).
\]
Then $\forall n \in \naturals\; P(n)$ is true.
\end{axiom*}

In fact, we can get rid of the English altogether and formulate
\begin{rul}[Induction]\label{indrule}
\Rule{P(0), \quad \forall m \in \naturals\ P(m) \implies P(m+1)}
{\forall n \in \naturals\; P(n).}
\end{rul}

We saved this last formulation to last because, until you're experienced
translating logical formulas into intelligible language, the formula can
hide how obvious and simple the Induction Axiom really is.  Actually,
you'll often see the Induction Axiom and Rule stated with $n$ in place of
$m$, which can make them even harder to decipher.  But since $m$ is a
bound variable in the second hypothesis of the rule, it doesn't matter if
we rename it to be $n$.

\iffalse
A common mistake is to think of $P(n)$ as a number, much as one thinks
of $f(n)$ as a number when $f$ is an ordinary function.  In fact,
$P(n)$ is a predicate; that is, a mathematical statement or
proposition.
\fi

\subsection{Ellipses}
Incidentally, the argument above could be criticized because notation such
as $1 + 2 + 3 + \cdots + n$ may seem imprecise.  Alway watch out for
notation with ``$\cdots$'' or ``\dots'' in it (the dots are called an
``ellipsis'').  This notation is common because it is convenient.  The
idea is to show enough of a sequence that anyone can figure out the
pattern needed to fill in the ellipsis.  We could have been more precise
by using summation notation instead, namely, $1 + 2 + 3 + \cdots + n$
could be written either as
\[
\sum_{i=1}^n i
\]
or as
\[
\sum_{1 \leq i \leq n} i.
\]
In this notation, the pattern of terms in the summation is made explicit.
In two important special cases, the definition of the summation $1 + 2 + 3
+ \cdots + n$ requires some care.  We already observed that if $n = 1$,
then $1 + 2 + 3 + \cdots + n = \sum_{1\le i \le 1} i = 1$.  That is, There
is only one term in the summation; the appearance of $2$ and $3$ to
indicate the pattern is misleading in this case, because they don't
appear.

What about when $n=0$?  Then $\sum_{1 \le i \le 0} i$ is a sum over an
\emph{empty set} of $i$'s.  That is, there are no terms at all in the
summation.  In this case, the sum is \emph{defined} to be zero by
convention.  This convention is useful, because, for example, we can say
that for any function $f:\naturals \to \reals$,
\[
\sum_{1 \le i \le n+1} f(i) = f(n+1) + \sum_{1 \le i \le n} f(i)
\]
for all $n \in \naturals$, even for $n = 0$.


\subsection{Proof Format}
The text of a proof by induction should consist of four parts.  We've
already seen each of these parts in the proof of equation~(\ref{sumn}).

\begin{enumerate}

\item \textbf{State that the proof is by induction.}  This immediately
conveys the general structure of the argument.

\item \textbf{Specify the induction hypothesis}: $P(n)$.  Sometimes, the
choice of $P(n)$ will come directly from the theorem statement.  In the
proof above, $P(n)$ was the equation~(\ref{sumn}) to be proved.  Other
times, the choice of $P(n)$ is not obvious at all; we will see an example
of this soon.

\item \textbf{The basis step}: prove $P(0)$.  The ``basis step'' or ``base
case'' is a proof of the predicate $P(0)$.

\item \textbf{The inductive step}: prove that $\forall m \in \naturals\
P(m) \implies P(m+1)$.  Begin the inductive step by writing, ``For $m \geq
0$, assume $P(m)$ in order to prove $P(m+1)$.''  (You can substitute in
the statements of the predicates $P(m)$ and $P(m+1)$ if the reminder seems
helpful.)  Then verify that $P(m)$ indeed implies $P(m+1)$ for every $m
\in \naturals$.

\end{enumerate}

In the case of equation~(\ref{sumn}), we used induction purely as a proof
technique; it gave little insight into why the theorem is true.

Furthermore, while induction was essential in proving the summation equal
to $n (n+1) / 2$, it did not help us find this formula in the first place.
We'll turn to the problem of finding sums of series in a couple weeks.

\subsection{Induction Examples}

This section contains several examples of induction proofs.  We begin with
an example about Fibonacci numbers, followed by an example from
elementary plane geometry, and finally an application of induction to a
design problem vital to the future of Computer Science at MIT.  Then we
illustrate some typical mistakes in using induction by proving
(incorrectly!)  that all horses are the same color and that camels can
carry an unlimited amount of straw.

\subsubsection{A Fibonacci Identity}

Fibonacci was a thirteenth century mathematician who invented
\emph{Fibonacci numbers} to model population growth (or rabbits, see
Rosen, pp. 205, 310).  The first two Fibonacci numbers are 0 and 1, and
each subsequent Fibonacci number is the sum of the two previous ones.  The
$n$th Fibonacci number is denoted $F_n$.  In other words, the Fibonacci
numbers are defined recursively by the rules
\begin{eqnarray*}
F_0 & \eqdef & 0,\\
F_1 & \eqdef & 1,\\
F_i & \eqdef & F_{i-1} + F_{i-2}, \text{ for }i \geq 2.
\end{eqnarray*}
Here, we're using the notation ``$\eqdef$'' to indicate that an equality
holds \emph{by definition}.  The first few Fibonacci numbers are
\[
0, 1, 1, 2, 3, 5, 8, 13, 21,\dots
\]
Fibonacci numbers come up in several different settings, but they have
captivated a continued mathematical following out of proportion to their
importance in applications because they have a rich and surprising
collection of properties, such as the one expressed in the following
theorem.  The theorem is a good thing to forget if you run low on brain
space, its proof just provides a nice illustration of induction.

\begin{theorem}
$\forall n \geq 0\ F_0^2 + F_1^2 + \cdots + F_n^2 = F_n F_{n+1}$
\end{theorem}

For example, for $n = 4$ we have $0^2 + 1^2 + 1^2 + 2^2 + 3^2 = 15 = 3 \cdot
5$.

Let's look for a proof by induction.  First, the theorem statement
suggests that the induction hypothesis $P(n)$ be
\begin{eqnarray*}
P(n) & \eqdef & \left[\sum_{i=0}^n F_i^2 = F_n F_{n+1}\right].
\end{eqnarray*}
Second, we want to identify the gap between $P(m)$ and $P(m+1)$.  The
predicate $P(m+1)$ states that $\sum_{i=0}^{m+1} F_i^2 = F_{m+1} F_{m+2}$.
Now the plan is to use $P(m)$ to reduce this statement to a simpler
assertion.  An easy way is to subtract the equation in predicate $P(m)$.
Taking the $P(m+1)$ equation ``minus'' $P(m)$ equation gives:
\[
F_{m+1}^2 = F_{m+1} F_{m+2} - F_m F_{m+1}.
\]

This is the Fibonacci recurrence in disguise; dividing by $F_{m+1}$ and
moving a term gives $F_m + F_{m+1} = F_{m+2}$.  This is the extra fact
need to bridge the gap between $P(m)$ and $P(m+1)$ in the inductive step.
The full proof is written below.

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that
$\sum_{i=0}^n F_i^2 = F_n F_{n+1}$.

\textbf{Base case} $n = 0$: $P(0)$ is true because
\[
F_0^2 = 0^2 = 0 = 0 \cdot 1 = F_0 F_1.
\]

\textbf{Inductive step}: For $m \geq 0$, assume $\sum_{i=0}^m F_i^2 = F_m
F_{m+1}$ to prove $\sum_{i=0}^{m+1} F_i^2 = F_{m+1} F_{m+2}$.

For all $m \geq 0$, the equation $F_m + F_{m+1} = F_{m+2}$ holds by the
definition of the Fibonacci numbers.  Multiplying both sides by $F_{m+1}$
and rearranging terms gives $F_{m+1}^2 = F_{m+1} F_{m+2} - F_m F_{m+1}$.
Adding this identity to the equation in the proposition $P(m)$ gives:
\begin{eqnarray*}
F_{m+1}^2 + \sum_{i=0}^m F_i^2 & = & (F_{m+1} F_{m+2} - F_m F_{m+1}) + F_m F_{m+1} \\
\sum_{i=0}^{m+1} F_i^2 & = & F_{m+1} F_{m+2}\\
\end{eqnarray*}
This proves that for all $m \in \naturals\; P(m) \implies P(m+1)$ and
completes the proof.
\end{proof}

\subsubsection{Geometry}

\begin{definition}
  A convex polygon is a polygon such that any straight line between
  any two vertices doesn't leave the polygon.
\end{definition}

\begin{theorem*}
The sum of the interior angles in any $n$-sided convex polygon is exactly
$(n-2) 180$ degrees, for all $n \ge 3$.
\end{theorem*}
\begin{proof}

The proof is by induction.  The induction hypothesis is
\begin{eqnarray*}
P(n) & \eqdef &
\text{\emph{The sum of the interior angles in any $n$-sided convex polygon
is $(n-2) 180$ degrees}}.
\end{eqnarray*}

\textbf{Base case} $n=3$: An $3$-sided polygon is a triangle, whose
interior angles were shown to sum to $180$ degrees by Euclid.

\textbf{Inductive step}:  Assume that $P(m)$ holds for some $m \ge 3$.
We must show that $P(m+1)$ holds.

So let $X$ be any $(m+1)$-vertex convex polygon, say with successive
vertices $x_1,x_2,\ldots,\linebreak[2]x_{m+1}$.  Let $Y$ be the polygon
with vertices $x_1,x_2,\ldots,x_{m}$.  That is, $Y$ is obtained by cutting
out one vertex from $X$.  Now $Y$ is also a convex polygon (proof left to
the reader!), so by induction hypothesis $P(m)$, the sum of the interior
angles of $Y$ is $(m-2)180$.  Now let $T$ be the triangle with vertices
$x_m, x_{m+1}, x_1$.  The sum of the interior angles in $X$ is the sum of
those in $Y$ plus the sum of those in $T$ (proof again left to the reader:
draw a picture \footnote{see Velleman, example 6.2.3}).  So the sum of the
interior angles in $X$ is $(m-2)180 + 180 = ((m+1)-2)180$.  Since $X$ was
arbitrary, we conclude that the sum of the interior angles of any
$(m+1)$-sided convex polygon is $((m-2)+1)180$.  That is, $P(m+1)$ holds.
\end{proof}

Note that this induction argument started with base case $n=3$ rather than
0.  The inductive step proved that $P(m) \implies P(m+1)$ for all $m \ge
3$.  The final conclusion was that $\forall n \ge 3\; P(n)$.  This is a
valid variant of induction.

\iffalse
\subsubsection{The Fate of Computer Science at MIT}

In the preceding examples, induction has served purely as a proof
technique.  However, it can be useful more generally in problem
solving.

MIT is constructing a new Stata Center on the site of the old Building 20.
Designed by the world famous architect Frank Gehry, the current cost of
the project is budgeted at around \$200 million.  The Center includes two
Computer Science Buildings, one of which is already named after Bill Gates
in recognition of his \$20 million donation toward construction.  But the
budget has grown enormously---it was originally supposed to be \$100
million.  Despite the dramatic recent declines in the stock market, Bill
can still afford to make another contribution to cover the
shortfall\footnote{Up to this point, the story is all true.}, but it will
take some special enticement.

Gehry has designed an atrium with a spacious central plaza to be tiled in
L-shaped tiles, and MIT is thinking about offering to place a statue of
Bill in the courtyard.
\begin{figure}
\begin{center}
\begin{picture}(50,50)
\put(0,0){\line(1,0){50}}
\put(50,0){\line(0,1){50}}
\put(50,50){\line(-1,0){25}}
\put(25,50){\line(0,-1){25}}
\put(25,25){\line(-1,0){25}}
\put(0,25){\line(0,-1){25}}
\end{picture}
\caption{One of the L-shaped tiles that will be used in the courtyard
of the new computer science building.} \label{fig:Ltile}
\end{center}
\end{figure}

The planned courtyard consists of $2^n \times 2^n$ squares.  Most of these
will be covered by L-shaped tiles, each covering three squares as shown in
Figure~\ref{fig:Ltile}.  However, one square will be covered by the statue
of Bill; in fact, this should be one of the central squares.  The problem
is to find a suitable tiling.  An example solution for the case of $n = 2$
is shown.

(The phrase ``central squares'' is a little ambiguous.  If $n = 0$, then
the courtyard is a single square, and Bill takes it.  If $n > 0$, then
there are four central squares, and Bill will take any of them.)

\begin{figure}
\begin{center}
\begin{picture}(100,100)

\put(0,0){\line(1,0){100}}
\put(25,25){\line(1,0){50}}
\put(25,75){\line(1,0){50}}
\put(0,100){\line(1,0){100}}

\put(0,50){\line(1,0){25}}
\put(75,50){\line(1,0){25}}

\put(0,0){\line(0,1){100}}
\put(25,25){\line(0,1){50}}
\put(75,25){\line(0,1){50}}
\put(100,0){\line(0,1){100}}

\put(50,50){\line(0,1){25}}
\put(50,50){\line(1,0){25}}

\put(50,0,){\line(0,1){25}}
\put(50,75){\line(0,1){25}}

\put(50,50){\framebox(25,25){Bill}}

\end{picture}
\caption{Example with $n=2$: a legal tiling of a 4x4 courtyard.}
\end{center}
\end{figure}

Let's try to prove by induction that such a tiling exists.  As usual,
we first try to lift the inductive hypothesis directly from the
theorem statement.

\begin{theorem}
For all $n \geq 0$ there exists a tiling of a $2^n \times 2^n$
courtyard with Bill in a central square.
\end{theorem}

\begin{proof}
{\em (doomed attempt)} The proof is by induction.  Let $P(n)$ be the
proposition that there exists a tiling of a $2^n \times 2^n$ courtyard
with Bill in the center.  In the base case, $P(0)$ is true because
Bill fills the whole courtyard.  For $n \geq 0$, assume that there is
a tiling of a $2^n \times 2^n$ courtyard with Bill in the center to
prove that there is is a legal tiling of a $2^{n+1} \times 2^{n+1}$
courtyard with Bill in the center...
\end{proof}

Now we're in trouble!  The ability to tile a smaller courtyard with Bill
in the center is of no obvious help in tiling a larger courtyard with Bill
in the center.  The usual recipe for finding an inductive proof will not
work!

Sometimes, making the induction hypothesis {\em stronger} makes a proof
{\em easier}.  For example, we could make $P(n)$ the proposition that for
every position of Bill in a $2^n \times 2^n$ courtyard, there exists a
tiling of the remainder.  This hypothesis is ``stronger'' in the sense
that the earlier claim was just a special case.  However, when we have to
prove $P(n) \implies P(n+1)$, we will be in better shape because we can
\emph{assume} $P(n)$, which is now a more general, more useful statement.

\begin{method}
If you can not show that $P(n) \implies P(n+1)$ in a proof by
induction, change the induction hypothesis; in particular,
strengthening the hypothesis may make the proof easier.
\end{method}

Even with this new hypothesis, finding the right way to prove that
$P(n) \implies P(n+1)$ requires some work.

\begin{proof}
{\em (successful attempt)} The proof is by induction.  Let $P(n)$ be
the proposition that if any one square of a $2^n \times 2^n$ courtyard
must be left blank, then there exists a tiling of the remainder.  In
the base case, $P(0)$ is true because if the one and only square is
left blank, then there exists a tiling of the remainder (which is
nothing).  For $n \geq 0$, assume that if any one square of a $2^n
\times 2^n$ courtyard must be left blank, then there exists a tiling
of the remainder.  We will use this to prove that if any one square of
a $2^{n+1} \times 2^{n+1}$ courtyard must be left blank, then there
exists a tiling of the remainder.

Divide the $2^{n+1} \times 2^{n+1}$ courtyard into four quadrants,
each $2^n \times 2^n$.  One will contain the square that must be left
blank and can be tiled by induction.  Now place a tile in the center
of the courtyard so that it covers one square in each remaining
quadrant.  All that remains is to tile each of these three quadrants,
excluding the one square in each that is already covered.  But this
can also be done by induction.  This proves that $\forall n \geq 1\
P(n) \implies P(n+1)$.  The theorem follows as a special case in
which a central square is left blank during tiling and is later
covered by a statue of Bill.
\end{proof}

This proof has two nice properties.  First, we have a stronger result; if
Bill wants his statue on the edge of the courtyard, away from the pigeons,
we can accommodate him.  Second, not only does the proof guarantee that a
tiling exists, it actually gave a \emph{recursive procedure} for producing
one.  For example: To tile a $2^3 \times 2^3$ square leaving the upper
right corner empty, divide it into 4, put one tile in the center, and
recursively tile the 4 pieces, each with one square missing. (See Figure
\ref{tiling2})

\begin{figure}[h]
\begin{center}
\begin{center}
\scalebox{0.5}{\includegraphics{figures/tilings}}
\end{center}
\caption{A valid tiling for an 8x8 square leaving the upper right corner empty}\label{tiling2}
\end{center}
\end{figure}
\fi

\iffalse
\subsubsection{A False Proof}

\begin{falsethm}
All horses are the same color.
\end{falsethm}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that in any set
of $n$ horses, all the horses are the same color.  This is true in the
base case $n = 1$, since there is only one horse in the set.  For $n \geq
1$, assume that in every set of $n$ horses, all are the same color in
order to prove that in every set of $n+1$ horses, all are the same color.
Consider a set of $n+1$ horses $h_1, h_2, \dots, h_{n+1}$.  By induction,
$h_1, h_2, \dots, h_n$ all are the same color.  Likewise, $h_2, \dots,
h_{n+1}$ all are the same color.  Therefore, $h_1, h_2, \dots, h_{n+1}$
must all share the same color, namely the color of $h_2$.  This proves
that $P(n) \implies P(n+1)$ for any $n$, and so completes the proof.
\end{proof}

Where is the bug?---it's in the sentence beginning ``Therefore.''  The
``\dots'' notation helps create confusion about an implicit assumption
that the sets $\set{h_1,h_2, \dots, h_n}$ and $\set{h_2, \dots, h_{n+1}}$
overlap at $h_2$, and therefore are colored the same.  But if $n = 1$,
then the first set is just $\set{h_1}$ and the second is $\set{h_2}$, and
they do not overlap at all.

Because of this bug, we have really only proven $P(1)$, and $P(n)
\implies P(n+1)$ for $n\geq 2$.  But we haven't proved that $P(1)\implies
P(2)$, which of course does not hold.

\subsubsection{Another False Proof}

\begin{falsethm}
A camel can always carry all the straw in a barn.
\end{falsethm}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate, ``The camel can
carry $n$ pieces of straw.''  The base case $P(1)$ is true because a camel
can certainly carry one piece of straw.  In the inductive step, assume
that the camel can carry $n$ pieces of straw to prove that it can carry
$n+1$ pieces.  But if it can carry $n$ pieces of straw, then surely it can
carry $n+1$: one little piece of straw won't make any difference.
Therefore $P(n) \implies P(n+1)$, completing the proof.
\end{proof}

The flaw here is in the bogus assertion that the camel can carry $n+1$
straws if it can carry $n$.  Just because it is hard to say exactly for
which $n$ this is false, we have no doubt that there is an $n$ that
finally exceeds the camel's carrying ability.  There will always be ``a
straw that broke the camel's back.''

\iffalse
There is a field called ``fuzzy logic'' in which truth is not a 0/1
thing, but is rather represented by a real value between 0 and 1.
There is an analogue of induction in which the truth value decreases a
bit with each implication.  We will not be using fuzzy logic in this
class, however; at least, not intentionally.
\fi
\fi

\section{Strong Induction}\label{strong induction}

``Strong'' induction\footnote{Strong Induction is the same as what Rosen
calls the \emph{Second Principle of Induction}} is a variation of the
induction proof method.  Strong induction is quite similar to ordinary
induction, but is sometimes easier to use when solving problems.

The difference between ordinary induction and strong induction is subtle.
Both proofs can be written with nearly the same structure.  The only
difference is that in an ordinary induction proof we assume only $P(n)$ in
order to prove $P(n+1)$.  In a strong induction proof, we get to assume
all of $P(0), P(1), \dots, P(n)$ in order to prove $P(n+1)$.  This can be
a big help.  When we try to prove $P(n+1)$ in the inductive step, we do
not have just one fact in hand, but rather a whole list of facts!

\subsection{The Strong Induction Axiom}
Like ordinary induction, strong induction can be expressed as an
axiom:

\begin{axiom*}[Strong Induction]
If $P(0)$ is true and $\forall n \geq 0\ (P(0) \wedge P(1) \wedge \dots
\wedge P(n)) \implies P(n+1)$, then $P(n)$ is true for all $n \geq 0$.
\end{axiom*}

The expression $(P(0) \wedge P(1) \wedge \dots \wedge P(n)) \implies
P(n+1)$ might be a little hard to decrypt.  It just means that $P(n+1)$
logically follows if we accept all the statements $P(0), P(1), \dots,
P(n)$.  Writing this as a rule with logical formulas makes this explicit

\begin{rul}\label{strongindrule}[Strong Induction]
\Rule{P(0), \quad \forall n \in \naturals [(\forall m \le n\ P(m)) \implies
P(n+1)]}
{\forall n \in \naturals\; P(n)}
\end{rul}
Strong induction is as obvious a principle as ordinary induction, so we
could confidently take it as another axiom.  Actually, we don't have to
make it an axiom, because we could prove the correctness of strong
induction by very elementary reasoning starting from the induction axiom.

There's also another interesting way to justify strong induction without
using ordinary induction at all.  The proof is by contradiction: suppose
that some statement in the list $P(0), P(1), \dots, P(n), \dots$ was
actually false.  Since there's some false statement in the list, there
must be a \emph{first} one, say $P(k)$ for some $k>0$, that is false.
(The number $k$ has to be $> 0$ because we know $P(0)$ is true.)  Now we
know that $P(0), P(1), \dots, P(k-1)$ are true, since $P(k)$ is the first
false statement.  But since $P(k)$ logically followed from the preceding
statements $P(0), P(1), \dots, P(k-1)$, it must be true, contradicting our
assumption that it was false.  So there can't be
any false statement in the list, that is, $P(n)$ is true for all $n \in
\naturals$.

Of course, we do not prove axioms; we just accept them as facts.  But in
this case we didn't need to \emph{assume} a strong induction axiom,
because we were able to prove the correctness of strong induction, and we
did it without even using induction!  How come?  Well, if you look back at
the previous argument, you can see we made a key assumption: that there
exists a \emph{first} false statement, $P(k)$.  This assumption is an
instance of another axiom called the \emph{Least Number Principle}\footnote{This is the same as what Rosen calls the \emph{Well Ordering Principle}} which
says that in any set of one or more natural numbers, there must be a
\emph{least} (smallest) number.  So we have proved the soundness of strong
induction, and could similarly prove the soundness of ordinary induction
too, by elementary reasoning from the Least Number Principle.  This may
help you think more clearly about why induction works.

\subsection{Postage Stamp Example}

Now we're ready to solve a problem using strong induction.

\iffalse In this example, the base case will not be $P(0)$, but rather
$P(k)$ for some integer $k$.  For this reason, we will need a slight
variant of the strong induction axiom:

\begin{axiom*}
Let $P(n)$ be a predicate and $k$ be an integer.  If $P(k)$ is true
and $\forall n \geq k\ (P(k) \wedge P(k+1) \wedge \dots \wedge P(n))
\implies P(n+1)$, then $P(n)$ is true for all $n \geq k$.
\end{axiom*}
\fi

{\bf Problem:} Given an unlimited supply of 3 cent and 5 cent stamps,
what postages are possible?

{\bf Solution:} Let's first try to guess the answer and then try to
prove it.  A table that shows the values of all possible combinations
of 3 and 5 cent stamps will help.  The column heading is the number of
5 cent stamps and the row heading is the number of 3 cent stamps.

\[
\begin{array}{c|ccccccc}
  & 0 & 1 & 2 & 3 & 4 & 5 & \dots\\ \hline
0 & 0 & 5 &10 &15 &20 &25 & \dots\\
1 & 3 & 8 &13 &18 &23 & \dots  & \\
2 & 6 &11 &16 &21 & \dots  &   & \\
3 & 9 &14 &19 &24 & \dots  &   & \\
4 &12 &17 &22 & \dots  &   &   & \\
5 &15 &20 & \dots  &   &   &   & \\
\dots & \dots & \dots 
\end{array}
\]

Looking at the table, a reasonable guess is that the possible postages are
0, 3, 5, and 6 cents and every value of 8 or more cents.  Let's try to
prove this last part using strong induction.

\begin{claim}\label{3-5}
For all $n \geq 8$, it is possible to produce $n$ cents of postage from
3\textcent\ and 5\textcent\ stamps.
\end{claim}

Now let's preview the proof.  The induction hypothesis will be
\begin{eqnarray}\label{P}
P(n) & \eqdef & \text{if } n \geq 8, \text{ then $n$\textcent\ postage can be
produced using 3\textcent\ and 5\textcent\ stamps}
\end{eqnarray}

A proof by strong induction will have the same four-part structure as an
ordinary induction proof.  The base case, $P(0)$, won't be interesting
because $P(n)$ is \emph{vacuously} true for all $n <8$.

In the inductive step we have to show how to produce $n+1$ cents of
postage, assuming the strong induction hypothesis that we know how to
produce $k$\textcent\ of postage for all values of $k$ between 8 and $n$.
A simple way to do this is to let $k= n-2$ and produce $k$\textcent\ of
postage; then add a 3\textcent\ stamp to get $n+1$ cents.

But we have to be careful; there is a pitfall in this method.  If $n+1$ is
8, 9 or 10, then we can not use the trick of creating $n+1$ cents of
postage from $n-2$ cents and a 3 cent stamp.  In these cases, $n-2$ is
less than 8.  None of the strong induction assumptions help us make less
than 8\textcent\ postage.  Fortunately, making $n+1$ cents of postage in
these three cases can be easily be done directly.

\begin{proof}
The proof is by strong induction.  The induction hypothesis, $P(n)$, is
given by~(\ref{P}).

\textbf{Base case} $n=0$: $P(0)$ is true vacuously.

In the inductive step, we assume that it is possible to produce postage
worth $8, 9, \dots, n$ cents in order to prove that it is possible to
produce postage worth $n+1$ cents.

There are four cases:

\begin{enumerate}
\item $n+1 < 8$:  So $P(n+1)$ holds vacuously.

\item $n+1 = 8$: $P(n+1)$ holds because we produce $8$\textcent postage
using one 3\textcent and one 5\textcent stamp.

\item $n+1 = 9$: $P(n+1)$ holds by using three 3\textcent stamps.

\item $n+1 = 10$: $P(n+1)$ holds by using two 5\textcent stamps.

\item $n+1 > 10$: We have $n \geq 10$, so $n-2 \geq 8$ and by strong
induction we may assume we can produce exactly $n-2$ cents of postage.
With an additional 3\textcent stamp we can therefore produce $n+1$ cents
of postage.
\end{enumerate}
So in every case, $P(0) \wedge P(1) \wedge \dots P(n) \implies P(n+1)$.
By strong induction, we have concluded that $P(n)$ is true for all $n \in
\naturals$.
\end{proof}

\subsubsection{Induction with nonzero base cases}

To conform to the standard format, we organized the proof of
Claim~\ref{3-5} with a base case of 0.  But since we only were interested
in 8 or more cents postage, it would have made more sense to start the
induction at 8 instead of 0, to treat 8, 9 and 10 as \emph{three} base
cases, and to consider the inductive step only for $n+1 > 10$.  From now
on, we will allow induction proofs formatted with several base cases in
this way.

At the other extreme, we can formulate strong induction with no base case
at all---just an inductive step.  Namely, we could replace the strong
induction \ruleref{strongindrule} with another logical rule:

\begin{rul}\label{strongnobase}[Strong Induction without base case]
\Rule{\forall n \in \naturals\ (\forall m < n\; P(m)) \implies P(n)}
{\forall n \in \naturals\; P(n)}
\end{rul}

Notice that the base case antecedent, $P(0)$, is missing from
\ruleref{strongnobase}.  That's because it's hidden in the single,
``induction-step'' antecedent of the rule.  Namely, when $n=0$ the
antecedent requires that $P(0)$ holds as long as $P(m)$ holds for all
natural numbers $m <0$.  But we can say that $P(m)$ \emph{does} hold for
\emph{all} such natural numbers $m<0$ since there aren't any!  In
practice, using this form of strong induction means that even though the
proof has no base case, doing the inductive step requires handling $n=0$
as a separate case.

\subsection{Strong Induction False Proof}

In the preceding proof, we were careful not to accidently assume more than
is permitted by the strong induction axiom.  Now let's be sloppy and see
what fun facts we can prove!

\begin{falsethm}
All Fibonacci numbers are even.
\end{falsethm}

Remember that the Fibonacci numbers are denoted by $F_0, F_1, F_2,
\dots$ where $F_0 = 0$, $F_1 = 1$, and $F_i = F_{i-1} + F_{i-2}$ for
$i \geq 2$.  The first few Fibonacci numbers are $0, 1, 1, 2, 3, 5, 8,
13, \dots$.

\begin{proof}

The proof is by strong induction.  Let $P(n)$ be the predicate that
$F_n$ is even.  In the base case, $P(0)$ is true because $F_0 = 0$,
which is even.  In the inductive step, for $n \geq 0$ assume that
$F_0, F_1, \dots, F_n$ are all even in order to prove that $F_{n+1}$
is even.  By definition, $F_{n+1} = F_n + F_{n-1}$.  Since both $F_n$
and $F_{n-1}$ are even, $F_{n+1}$ is even.
\end{proof}

Where is the bug?  If $n = 0$, then the statement ``By definition,
$F_{n+1} = F_n + F_{n-1}$'' is false.  In this case, $F_{n+1} = F_1$,
which equals 1 by definition.  We forgot a special case!

We really only proved $P(0)$ and $P(0) \wedge P(1) \implies P(2),
P(1) \wedge P(2) \implies P(3), \dots$.  We forgot to check one
little thing, $P(1)$, and reached an infinite number of false
conclusions!


\subsection{Winning the Game of Nim}

The game of Nim is defined as follows: Some positive number of sticks
are placed on the ground.  Two players take turns removing one, two,
or three sticks.  The player to remove the last stick loses.

\begin{theorem}
The first player has a winning strategy iff the number of sticks, $n$, is
not $4k+1$ for any $k \in \naturals$.
\end{theorem}

A strategy is a rule for how many sticks to remove when there are $n$
left.  We show that if $n=4k+1$, then player 2 has a strategy that will
force a win for him, otherwise, player 1 has a strategy that will force a
win for him.

\begin{proof}
The induction hypothesis is: for all $k \in \naturals$, if $n=4k+1$, then the
first player loses, and if $n = 4k$, $4k + 2$, or $4k + 3$, the first
player wins.  This exhausts all possible cases for $n$.

We proceed by strong induction, using starting from $1$.

\textbf{Base case}: $n = 1$. 
The first player has no choice but to remove $1$ stick and lose, which
is what the theorem says for this case.

\textbf{Strong inductive step}:
Suppose the theorem is true for numbers $1$ through $n$ and show that it
is true for $n+1$. 
For the inductive step, there are four cases: 
\begin{itemize}
\item $n+1=4k+1$: show that the first player loses.  We've already handled
the base case ($1$) so we can assume $n+1 \geq 5$.  Consider what the
first player might do to win: he can choose to remove 1, 2 or 3 sticks.
If he removes one stick, the remaining number of sticks is $n = 4k$.  By
strong induction, the player who plays at this point has a winning
strategy.  So the player who played first will lose.

Similarly, if the first player removes two sticks, the remaining number is
$4(k-1)+3$.  Again, he loses, by the same reasoning.  Similarly, by
removing $3$ sticks, he loses.  So, however the first player moves, he
loses.

\item $n+1 = 4k$: show that the first player can win.

Have the first player remove 3 sticks: the second player then sees
$4(k-1)+1$ sticks, and loses, by the strong inductive hypothesis.

\item $n+1 = 4k+2$: show that the first player can win.

Have the first player remove 1 stick: the second player then sees
$4k + 1$ sticks, and loses as in the previous case. 

\item $n+1 = 4k+3$: show that the first player can win.

Have the first player remove 2 sticks: again, the second player sees
$4k + 1$ sticks and loses.
\end{itemize}
\end{proof}


\iffalse

\section{Induction and Tournaments}

Suppose there is a tournament with $n$ players.  The tournament is
round-robin, i.e. every player has a match against every other player.
For every match there is a winner; there are no ties.

Confusing thing: When math people talk about tournaments--- and they
often do--- they mean a tournament in which all matches have already
been played, even though everything is discussed in the present tense
(``$a$ defeats $b$'').

\subsection{A Simple Way to Rank Players}

Our first goal is to find a ranking or ordering of the players such
that the $i$th ranked player defeats the $(i+1)$st ranked player for
each $i$.  It is okay if, say, the 5th ranked player loses to the 9th
ranked player; we just want to insure that the 5th ranked player wipes
the floor with the 6th ranked player.

Does such a ranking always even exist?  Let's check a small example.
Suppose there are only three players.  Suppose player $p_1$ defeats
$p_2$, $p_2$ defeats $p_3$, and $p_3$ defeats $p_1$, forming a sort of
cycle.  In this tournament, several rankings meet our goal, for
example $p_1$, $p_2$, $p_3$.  In fact, there is a strong induction
proof that such a ranking exists for every tournament.

\begin{theorem}
Given an $n$-player round-robin tournament, there exists a ranking of
the players $p_1, p_2, \dots, p_n$ such that $p_i$ defeats $p_{i+1}$
for $1 \leq i < n$.
\end{theorem}

In the proof, we will use the notation $|S|$, which may be unfamiliar;
this denotes the number of elements in the set $S$.

As usual, we can take the inductive hypothesis directly from the
theorem statement.  The problem in the inductive step will be to prove
that every $n+1$ player tournament has a ranking.  We get to assume
that every tournament with fewer players has a ranking.  The most
natural approach is to isolate one player $x$, to assert that a
ranking for the remaining $n$ players exists by induction, and then to
show that $x$ can be added to the ranking of the other $n$ players.
This is not as easy as it sounds-- inserting $x$ into the ranking is
tricky-- but it does work.  We use a different approach in the proof
below.

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the predicate that in
every $n$-player round-robin tournament, there exists a ranking such
that $p_i$ defeats $p_{i+1}$ for $1 \leq i < n$.  In the base case,
there are no players and so there is nothing to prove; thus, $P(0)$ is
true.

In the inductive step, assume that such a ranking exists for every
tournament with up to $n$ players in order to prove that such a
ranking exists in a tournament with $n+1$ players.  Choose an
arbitrary player $x$.  Let $B(x)$ be the set of players that beat $x$,
and let $L(x)$ be the set of players that lose to $x$.  Note that both
of these sets have at most $n$ players and that either might be empty.
Let $k = |B(x)|$, the number of players that beat $x$.

By induction, there exists a suitable ranking of the players in
$B(x)$.  Call this $p_1, \dots, p_k$.  Similarly, there exists a
ranking of the players in $L(x)$.  Call this $p_{k+2}, \dots, p_n$.
Let $p_{k+1} = x$.  Then $p_1, \dots, p_{k-1}, p_k, p_{k+1}, \dots
p_{n}$ is a ranking of all the players.

All that remains is to check that each player beats the next-ranked
player.  Player $p_{k-1}$ beats $p_k$ since $p_{k-1} \in B(x)$, and
every player in the set $B(x)$ beats $p_k$.  Similarly, player $p_k$
beats $p_{k+1}$ since $p_{k+1} \in L(x)$, and $p_k$ beats every player
in $L(x)$.  All other cases follow by induction.
\end{proof}

This proof translates naturally into an algorithm for finding a
ranking.  Choose an arbitrary player $x$, compute sets $B(x)$ and
$L(x)$, rank these sets recursively, and then merge the results into
an overall ranking.

\subsection{A Better Way to Rank Players}

There is a problem with the preceding way of ranking players.  Suppose
that in every match between players whose ranks are not consecutive,
the lower ranked player wins.  In this case, the {\em highest} ranked
player loses to all but one other and so has the {\em worst} overall
record!  This is not a fair ranking!

We would like to find a ranking where the $i$th player beats the
$(i+1)$st player {\em and} players with better records get better
rankings.  Unfortunately, this is not always possible.  However, there
is always a ranking where the $i$th player beats the $(i+1)$st player
and one of the players with the best win-loss record is ranked first.
(Several players might tie for the best win-loss record.)

\begin{theorem}
In any $n$-player round-robin tournament there exists a ranking of the
players $p_1, p_2, \dots p_n$, such that $p_i$ defeats $p_{i+1}$ for
$1 \leq i < n$ and $p_1$ is a player with the best win-loss record.
\end{theorem}

Let's try to emulate the previous proof.

{\em Proof. } {\em (first try)} The proof is by strong induction.  Let
$P(n)$ be the theorem statement.  In the base case, there is a single
player, so $P(1)$ is true.  In the inductive case, we assume $P(1),
P(2), \dots, P(n)$ to prove $P(n+1)$.  Choose a player $x$ that loses
to the best player.  Let $B(x)$ be the set of players that beat $x$,
and let $L(x)$ be the set of players that lost to $x$\dots.

How do we continue?  The best player is now in the set $B(x)$.  Since
we intend to rank the players of $B(x)$ by induction, the best player
overall must have the best record even when only matches within $B(x)$
are considered.  This might not be true.  Maybe the best player only
has a good overall record because he or she beat so many players that
are now in $L(x)$.  So we are stuck.

There are many ways that we might try to proceed:

\begin{itemize}
\item Strengthen the induction hypothesis.  Let $P(n)$ claim that we
can find a ranking with {\em any} player in the first position, not
just the one with the best win-loss record.  This approach fails
because, for example, we can not make a player who lost every match
rank first.  This induction hypothesis is too strong.

\item Pull out the player with the best win-loss record.  We could
then rank the remaining $n$ players by induction.  However, we have no
guarantee that the player with the best win-loss record defeats the
first player in that ranking; we might not be able to construct a
proper ranking on $n+1$ players.

\item Choose player $x$ so that the best player overall has the best
record among those who defeated $x$.  This solves the immediate
problem that stopped us in the first proof attempt, but how do we know
that such a player $x$ always exists?
\end{itemize}

No ``right'' strategy leaps out; probably considerable trial and error
is unavoidable.

The basic plan is to pull out one player, rank the players in the
resulting ``subtournament'' by induction, and then put the extra
player back to create a complete ranking.  Let $z$ be the player with
best overall win/loss record that we want ranked first.  The key
problem is to ensure that $z$ has the best win/loss record even within
the ``subtournament''.  One solution is to pull out a player $x$ that
defeated $z$.  This makes $z$ look better; if his win/loss record was
best before, it will still be best when matches against $x$ are
ignored.  This is the basis for the following proof.

\begin{proof} {\em (second try)}
Let $z$ be a player with the best win-loss record.

The proof is by {\em ordinary} induction.  Let $P(n)$ be the theorem
statement.  In the base case, $P(1)$, there are no matches and so
there is nothing to prove.  In the inductive case, assume $P(n)$ to
prove $P(n+1)$.  Now there are two cases:

{\em Case 1:} If $z$ is undefeated, then we can find a ranking of the
remaining $n$ players using the preceding theorem.  Call this $p_2,
p_3, \dots, p_{n+1}$ and let $p_1 = z$.  Then the overall ranking
$p_1, p_2, \dots, p_{n+1}$ is satisfactory; the best player is ranked
first, $p_1$ defeats $p_2$ because $p_1$ defeats all other players,
and $p_i$ defeats $p_{i+1}$ for all $2 \leq i < n$ by the preceding
theorem.

{\em Case 2:} Otherwise, there exists a player $x$ that defeats $z$.
If $z$ is a player with the best overall record against all players,
then $z$ must be a player with the best overall record when $x$ is
removed from the tournament.  By induction there is a ranking $p_1,
p_2, \dots, p_n$ of all players excluding $x$ where $p_1 = z$.  All
that remains is to fit $x$ into this order.

Suppose that $x$ is inserted in the ranking just below the
lowest-ranked player that beat him.  (There must be such a player
since otherwise $x$ would have won all his matches in the
$(n+1)$-player tournament which contradicts the definition that $z$
has the best record.)  Then $z$ remains first in the ranking and all
that remains to check is that each player defeated the next-lower
ranked player.

By the way that $x$ was inserted into the ranking, the player ranked
immediately above $x$ defeated him.  Since this was the lowest-ranked
player to defeat $x$, $x$ must in turn have defeated the player ranked
below himself, if there is one.  That every other player defeated the
next-lower ranked player follows from the inductive construction of
the ranking.
\end{proof}
\fi

\section{Induction, Strong Induction, and Least Number Principle}

We argued above that strong induction is better than ordinary induction,
but it's worth observing now that it's only ``better'' from the point of
view of writing up a proof, not because it can be used to prove
\emph{more} theorems.  It is always possible to convert a proof using one
form of induction into a proof using the other.

Of course the conversion from induction to strong induction is trivial
because an ordinary induction proof already \emph{is} a strong induction
proof---think about that!  It's conversion the other way that's
interesting.

\subsection{Converting Strong Induction to Ordinary Induction [Optional]}

\begin{small}
Here is a recipe for converting, piece-by-piece, a strong induction proof
that some proposition, $P(n)$, holds for all $n$, into an ordinary
induction proof.

\begin{itemize}

\item For the new, ordinary induction proof, use the hypothesis $Q(n)$ where
\begin{eqnarray*}
Q(n) & \eqdef & \forall m \le n\; P(m).
\end{eqnarray*}

\item In the base case, the strong induction proof establishes $P(0)$.  In
the new proof, we can use exactly the same argument to establish $Q(0)$,
since $Q(0)$ is equivalent to $P(0)$.

\item In the inductive step, the strong induction proof shows that
$\forall m \le n\ P(m) \implies P(n+1)$.  In other words, the old
inductive step proof concludes that
\[
Q(n) \implies P(n+1).
\]
But since $Q(n)$ implies itself, we can add an additional conclusion to
the proof, namely,
\[
Q(n) \implies (Q(n) \land P(n+1)).
\]

\item But $(Q(n) \land P(n+1))$ is equivalent to $Q(n+1)$, so we can add
as a final conclusion that
\[
Q(n) \implies Q(n+1).
\]
\end{itemize}
So by adding the previous two conclusions at the end of the induction case
of the strong induction proof, we wind up with an ordinary induction proof
of $\forall n\; Q(n)$.

\end{small}

\subsection{Least Number Principle}

Another proof method closely related to induction depends on the
\begin{axiom*}[Least Number Principle]
Every nonempty subset, $S \subseteq \naturals$, has a smallest element.
\end{axiom*}

The Least Number Principle (LNP) looks nothing like the induction axiom,
and it may seem obvious but useless.

But as for obvious, note that this axiom would be false if the set of
non-negative integers, $\naturals$, were replaced by, say, the set, $\integers$, of
\emph{all} integers, or the set, $\rationals^{+}$, of positive rational
numbers.  Neither of these sets has a least element.  So the LNP is
capturing something special about the natural numbers.

As for useless, recall that at the end of Section~\ref{strong induction}
we used the LNP to ``prove'' the strong induction axiom.  If you look back
at this proof, you can read it as a recipe for converting any strong
induction proof into an LNP proof---similar to the recipe we gave for
converting a strong induction into ordinary induction.  So LNP is at
least as useful as strong induction!

Conversely, we can use strong induction to prove the LNP.  This allows us
to convert any LNP proof into a strong induction proof, if we choose.  In
short, a proof using induction, strong induction, or the LNP to prove some
proposition can always be converted in a proof using any the other
methods.  Mathematicians like LNP, because it is often ``prettier'' (fewer
symbols) than an induction proof.  On the other hand, as it often involves
proof by contradiction, using the LNP is not always the best approach.
The choice of method is really a matter of style---but style does matter.

\begin{optional}
To prove the LNP by strong induction, let $P(n)$ be the predicate that
every set of natural numbers containing the number $n$ also contains a
smallest element.  So if we prove $\forall n\; P(n)$, then we have proved
the LNP, since a nonempty set has to contain {\em some} element $n$.

\begin{proof}
We prove $\forall n\; P(n)$ by strong induction.  The induction hypothesis
is $P(n)$.

\textbf{Base case} $n = 0$: If a set contains $0$, then $0$ is its smallest
element.

\textbf{strong inductive step}: Assume $\forall m \le n\; P(m)$, and prove
$P(n+1)$.

Consider any set, $S$, containing the integer, $n+1$.  If $n+1$ is
actually the smallest element of $S$, then we are done.  Otherwise, $S$
must contain a smaller element $m < n+1$.  But then $m\le n$, and the
strong induction hypothesis implies that $S$ contains a smallest element,
and we are done in this case too.
\end{proof}

\end{optional}

\iffalse
This argument can be made precise; if one accepts the LNP as an axiom,
then strong induction can be derived as a proposition.  This suggests that
the LNP is at least as powerful as our very best weapon, strong induction!

An example of an LNP proof is given below.  Define a {\em cycle}
in a tournament to be a sequence of players such that each defeats the
next and the last defeats the first.  The {\em length} of a cycle is the
length of the sequence of players.  A $n$-{\em cycle} is a cycle of length
$n$.  For example, $p_1$ defeats $p_2$, $p_2$ defeats $p_3$, $p_3$ defeats
$p_4$, and $p_4$ defeats $p_1$ is a 4-cycle.

\begin{theorem}
If a tournament contains a cycle, then it contains a 3-cycle.
\end{theorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that the tournament contains a cycle, but no 3-cycle.
By the the LNP axiom we can let $n$ be the length of the
shortest cycle.  By assumption $n \geq 3$.  Consider three consecutive
players in the cycle, $p_1$, $p_2$, and $p_3$.  If $p_1$ defeats
$p_3$, then $p_2$ can be removed to create a cycle of length $n-1$.
This contradicts the assumption that the shortest cycle had length
$n$.  If $p_3$ defeats $p_1$, then $p_1$, $p_2$, and $p_3$ form a
3-cycle, again a contradiction.
\end{proof}


Can the same statement be proven by induction, or is the LNP actually more
powerful?  In fact, this theorem does have a very similar proof by
induction, and more generally the LNP and induction are equivalent.  Here
is the induction proof:

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that every
tournament with an $n$-cycle contains a 3-cycle.  We can prove the
theorem by showing that $P(n)$ holds for all $n \geq 3$.

The base case, $P(3)$, is trivial.  In the inductive step, for $n \geq
3$, assume that every tournament with an $n$-cycle contains a 3-cycle
in order to prove that every tournament with an $(n+1)$-cycle contains
a 3-cycle.  In a tournament with an $(n+1)$ cycle, consider three
consecutive players, $p_1$, $p_2$, and $p_3$.  If $p_3$ defeats $p_1$,
then $p_1$, $p_2$, and $p_3$ form a 3-cycle and we are done.
Otherwise, if $p_1$ defeats $p_3$, then $p_2$ can be removed from the
original cycle to create an $n$-cycle.  By induction, there must be a
3-cycle.
\end{proof}
\fi

\section{The Fundamental Theorem of Arithmetic}

Number Theory, the study of the integers, is one of the oldest
branches of mathematics.  Many easily-stated problems in number theory
required centuries of effort to solve and many others remain unsolved.
Number theory is of growing importance in computer science, because it
is the basis of cryptographic systems used for secret communications,
file encryption, and digital signatures.

In this section, we'll use strong induction and the least-number
principle to establish a cornerstone of number theory called the
Fundamental Theorem of Arithmetic, which you may have encountered in
high school.  We'll begin with a couple definitions.

\begin{definition}
An integer $a$ {\em divides} an integer $b$ (denoted $a \mid b$) if
there exists an integer $k$ such that $ak = b$.
\end{definition}

For example, $7 \mid 21$, since $7 \cdot 3 = 21$.

\begin{definition}
An integer $n > 1$ is a {\em prime} if 1 and $n$ are the only positive
integers that divide it.  An integer $n > 1$ that is not prime is said
to be {\em composite}.
\end{definition}

The first few primes are 2, 3, 5, 7, 11, \ldots.  We'll also need one
simple fact.  This fact is not difficult to prove from first
principles, but there's no reason to do that now.

\begin{fact}
If a prime $p$ divides $ab$, then either $p \mid a$ or $p \mid b$.
\end{fact}

For example, $7 \mid 15 \cdot 14$.  It follows that 7 must divide
either 15 or 14.  Using an induction argument (that we'll not give
here), one can generalize this fact:

\begin{fact}
If a prime $p$ divides $a_1 a_2 \cdots a_n$, then $p \mid a_i$ for
some $1 \leq i \leq n$.
\end{fact}

Now we're ready for the main event.

\begin{theorem}[Fundamental Theorem of Arithmetic]
Every positive integer $n$ can be written in a unique way as a product
of primes:

\begin{eqnarray*}
n & = & p_1 p_2 \cdots p_j
\hspace{1in}
(p_1 \leq p_2 \leq \ldots \leq p_j)
\end{eqnarray*}
\end{theorem}

\begin{proof}
We must prove two things: (1) every positive integer can be expressed
as a product of primes and (2) this expression is unique.

First, we use strong induction to prove that every positive integer
$n$ is a product of primes.  As base case, $n = 1$ is the product of
an empty set of primes.  For the inductive step, suppose that every $k
< n$ is a product of primes.  We must show that $n$ is also a product
of primes.  If $n$ is itself prime, then this is true trivially.
Otherwise, $n = a b$ for some $a, b < n$.  By strong induction $a$ and
$b$ are both products of primes.  Therefore, $a \cdot b = n$ is also a
product of primes.  Thus, the claim is proved by induction.

Next, we use the least-number principle to prove that every positive
integer $n$ can be written as a product of primes in a unique way.
Assume for the purpose of obtaining a contradiction that $n$ can be
written in two different ways:

\begin{eqnarray*}
n & = & p_1 p_2 \cdots p_j \\
  & = & q_1 q_2 \cdots q_k
\end{eqnarray*}

Then $p_1 \mid n$ and so $p_1 \mid q_1 q_2 \cdots q_k$.  But this
implies that $p_1$ divides one of the primes $q_i$.  But since $q_i$
is a prime, it must be that $p_1 = q_i$.  Deleting $p_1$ from the
first product and $q_i$ from the second, we find that $n / p_1$ is a
positive integer smaller than $n$ that can be written as a product of
primes in two distinct ways.  This contradicts our assumption, and
proves the claim.
\end{proof}

Note that if 1 were considered a prime, the Fundamental Theorem of
Arithmetic would be false, which would be a real shame.  Thus, 1 is
usually regarded as neither prime nor composite.
\end{document}
