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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\newcommand{\primes}{\text{Primes}}

\begin{document}
\lecturenotes{3}{Induction}

\section{Induction}

A professor brings to class a bottomless bag of assorted miniature
candy bars.  She offers to share in accordance with two rules.  First,
she numbers the students 0, 1, 2, 3, and so forth for convenient
reference.  Now here are the two rules:

\begin{enumerate}
\item Student 0 gets candy.
\item For all $n \in \naturals$, if student $n$ gets candy,
then student $n + 1$ also gets candy.
\end{enumerate}

 You can think of the second rule as a compact way of writing a whole
sequence of statements, one for each natural value of $n$:

\begin{itemize}
\item If student 0 gets candy, then student 1 also gets candy.
\item If student 1 gets candy, then student 2 also gets candy.
\item If student 2 gets candy, then student 3 also gets candy, and so forth.
\end{itemize}

Now suppose you are student 17.  By these rules, are you entitled to a
miniature candy bar?  Well, student 0 gets candy by the first rule.
Therefore, by the second rule, student 1 also gets candy, which means
student 2 gets candy as well, which means student 3 get candy, and so
on.  So the professor's two rules actually guarantee candy for
\textit{every} student, no matter how large the class.  You win!

This reasoning generalizes to a principle called \term{induction}:

\textbox{
\textbf{Principle of Induction.}  Let $P(n)$ be a predicate.  If

\begin{itemize}
\item $P(0)$ is true, and
\item for all $n \in \naturals$, $P(n)$ implies $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \naturals$.
}

Here's the correspondence between the induction principle and sharing
candy bars.  Suppose that $P(n)$ is the predicate, ``student $n$ gets
candy''.  Then the professor's first rule asserts that $P(0)$ is true, and
her second rule is that for all $n \in \naturals$, $P(n)$ implies
$P(n+1)$.  Given these facts, the induction principle says that $P(n)$ is
true for all $n \in \naturals$.  In other words, everyone gets candy.

The intuitive justification for the general induction principle is the
same as for everyone getting a candy bar under the professor's two rules.
So the Principle of Induction is universally accepted as an obvious, sound
proof method.  What's not so obvious is how much mileage we get by using
it.

\section{Using Induction}

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

Induction often works directly in proving that some statement about
natural numbers holds for all of them.  For example, here is a classic
formula:

\begin{theorem}
\label{th:sum-to-n}
For all $n \in \natural$,
\begin{equation}\label{hyp}
1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}
\end{equation}
\end{theorem}

The left side of equation~\eqref{hyp} represents the sum of all the
numbers from 1 to $n$.  You're supposed to guess the pattern and mentally
replace the dots ($\cdots$) with the other terms.  We could eliminate the
need for guessing by rewriting the left side with \term{summation
notation}:
\[
\sum_{i=1}^n i
\qquad \text{or} \qquad
\sum_{1 \leq i \leq n} i
\qquad \text{or} \qquad
\sum_{i \in \set{1, \dots, n}} i
\]
Each of these expressions denotes the sum of all values taken on by
the expression to the right of the sigma as the variable, $i$, ranges
from 1 to $n$.  The meaning of the sum in Theorem~\ref{th:sum-to-n} is
not so obvious in a couple of special cases:

\begin{itemize}

\item If $n = 1$, then there is only one term in the summation, and so
$1 + 2 + 3 + \cdots + n = 1$.  Don't be misled by the appearance of 2
and 3 and the suggestion that $1$ and $n$ are distinct terms!

\item If $n \leq 0$, then there are no terms at all in the summation,
and so $1 + 2 + 3 + \cdots + n = 0$.

\end{itemize}

The dots notation is convenient, but watch out for these special cases
where the notation is misleading!

Now let's use the induction principle to prove Theorem~\ref{th:sum-to-n}.
Suppose that we define predicate $P(n)$ to be ``$1 + 2 + 3 + \cdots + n =
n(n+1)/2$''.  Recast in terms of this predicate, the theorem claims that
$P(n)$ is true for all $n \in \naturals$.  This is great, because the
induction principle lets us reach precisely that conclusion, provided we
establish two simpler facts:

\begin{itemize}
\item $P(0)$ is true.
\item For all $n \in \naturals$, $P(n)$ implies $P(n+1)$.
\end{itemize}

So now our job is reduced to proving these two statements.  The first
is true because $P(0)$ asserts that a sum of zero terms is equal to
$0(0+1)/2 = 0$.

The second statement is more complicated.  But remember the basic plan
for proving the validity of any implication: \textit{assume} the
statement on the left and then \textit{prove} the statement on the
right.  In this case, we assume $P(n)$:
\begin{align*}
1 + 2 + 3 + \cdots + n & = \frac{n(n+1)}{2}
\end{align*}
in order to prove $P(n+1)$:
\begin{align*}
1 + 2 + 3 + \cdots + n + (n+1) & = \frac{(n+1)(n+2)}{2}
\end{align*}
These two equations are quite similar; in fact, adding $(n+1)$ to both
sides of the first equation and simplifying the right side gives the
second equation:
\begin{align*}
1 + 2 + 3 + \cdots + n + (n+1)
    & = \frac{n(n+1)}{2} + (n+1) \\
    & = \frac{(n+2)(n+1)}{2}
\end{align*}
Thus, if $P(n)$ is true, then so is $P(n+1)$.  This argument is valid
for every natural number $n$, so this establishes the second fact
required by the induction principle.  In effect, we've just proved
that $P(0)$ implies $P(1)$, $P(1)$ implies $P(2)$, $P(2)$ implies
$P(3)$, etc. all in one fell swoop.

With these two facts in hand, the induction principle says that the
predicate $P(n)$ is true for all natural $n$.  And so the theorem is
proved!

\subsection{A Template for Induction Proofs}

The proof of Theorem~\ref{th:sum-to-n} was relatively simple, but even
the most complicated induction proof follows exactly the same
template.  There are five components:

\begin{enumerate}

\item \textbf{State that the proof uses induction.}  This immediately
conveys the overall structure of the proof, which helps the reader
understand your argument.

\item \textbf{Define an appropriate predicate $P(n)$.}  The eventual
conclusion of the induction argument will be that $P(n)$ is true for all
natural $n$.  Thus, you should define the predicate $P(n)$ so that your
theorem is equivalent to (or follows from) this conclusion.  Often the
predicate can be lifted straight from the claim, as in the example above.
The predicate $P(n)$ is called the ``induction hypothesis''.  Sometimes
the induction hypothesis will involve several variables, in which case you
should indicate which variable serves as $n$.

\item \textbf{Prove that $P(0)$ is true.}  This is usually easy, as in the
example above.  This part of the proof is called the ``base case'' or
``basis step''.  (Sometimes the base case will be $n=1$ or even some
larger number, in which case the starting value of $n$ also should be
stated.)

\item \textbf{Prove that $P(n)$ implies $P(n+1)$ for every natural
number $n$.}  This is called the ``inductive step'' or ``induction
step''.  The basic plan is always the same: assume that $P(n)$ is true
and then use this assumption to prove that $P(n+1)$ is true.  These
two statements should be fairly similar, but bridging the gap may
require some ingenuity.  Whatever argument you give must be valid for
every natural number $n$, since the goal is to prove the implications
$P(0) \rightarrow P(1)$, $P(1) \rightarrow P(2)$, $P(2) \rightarrow
P(3)$, etc. all at once.

\item \textbf{Invoke induction.}  Given these facts, the induction
principle allows you to conclude that $P(n)$ is true for all natural
$n$.  This is the logical capstone to the whole argument, but many
writers leave this step implicit.

\end{enumerate}

Explicitly labeling the \textit{base case} and \textit{inductive step}
may make your proofs more clear.

\subsection{A Clean Writeup}

The proof of Theorem~\ref{th:sum-to-n} given above is perfectly valid;
however, it contains a lot of extraneous explanation that you won't
usually see in induction proofs.  The writeup below is closer to what
you might see in print and should be prepared to produce yourself.

\begin{proof}
We use induction.  The induction hypothesis, $P(n)$, will be
equation~\eqref{hyp}.

\textbf{Base case:} $P(0)$ is true, because both sides of
equation~\eqref{hyp} equal zero when $n=0$.

\textbf{Inductive step:} Assume that $P(n)$ is true, where
$n$ is any natural number.  Then
\begin{align*}
1 + 2 + 3 + \cdots + n + (n+1)
    & = \frac{n(n+1)}{2} + (n+1) & \text{by induction hypothesis}\\
    & = \frac{(n+1)(n+2)}{2}  & \text{by simple algebra}
\end{align*}
which proves $P(n+1)$.

So it follows by induction that $P(n)$ is true for all natural $n$.
\end{proof}

Induction was helpful for \textit{proving the correctness} of this
summation formula, but not helpful for \textit{discovering} the
formula in the first place.  There are some tricks for finding such
formulas, which we'll show you in a few weeks.

\subsection{A Fibonacci Identity}

For another simple example of the use of induction, we'll consider the
\emph{Fibonacci numbers}\footnote{Fibonacci was a thirteenth century
mathematician who came up with his numbers in modelling growth of a rabbit
population.  A simple model for rabbit population growth assumes that at
the age of one month, a pair of rabbits will give birth to another pair of
rabbits, and will continue producing a pair of rabbits every month after
that.  We let $F_n$ be the total number of rabbit pairs at the start of
the $n$th month, and $B_n$ be the number of breeding pairs, that is, pairs
that are at least one month old.  Now the pairs at the $n$th month are the
$F_{n-1}$ pairs we had the previous month, plus the $B_{n-1}$ newborn
pairs produced by the previous month's breeding pairs, so $F_n = F_{n-1} +
B_{n-1}$.  Also, the set of breeding pairs at the $n$th month is simply
the set of \emph{all} the pairs we had the previous month, so $B_n =
F_{n-1}$.  Replacing $B_{n-1}$ by $F_{n-2}$ yield~\eqref{Fibeq}.}.

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,\notag\\
F_1 & \eqdef & 1,\notag\\
F_i & \eqdef & F_{i-1} + F_{i-2}, \text{ for }i \geq 2.\label{Fibeq}
\end{eqnarray}
The first few Fibonacci numbers are
\[
0, 1, 1, 2, 3, 5, 8, 13, 21,\dots.
\]
Fibonacci numbers come up naturally in several ways, 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{equation}\label{hypfib}
\sum_{i=0}^n F_i^2 = F_n F_{n+1}.
\end{equation}
Second, we want to identify the gap between $P(n)$ and $P(n+1)$.  The
predicate $P(n+1)$ states that $\sum_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2}$.
Now the plan is to use $P(n)$ to reduce this statement to a simpler
assertion.  An easy way is to subtract the equation in predicate $P(n)$.
Taking the $P(n+1)$ equation ``minus'' $P(n)$ equation gives:
\[
F_{n+1}^2 = F_{n+1} F_{n+2} - F_n F_{n+1}.
\]

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

\begin{proof}
The proof is by induction.  Let $P(n)$ be the equation~\eqref{hypfib}.

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

\textbf{Inductive step:}  We assume equation~\eqref{hypfib} holds for some
$n \geq 0$, and prove that $\sum_{i=0}^{n+1} F_i^2 = F_{n+1} F_{n+2}$.

For all $n \geq 0$, the equation $F_n + F_{n+1} = F_{n+2}$ holds by the
definition of the Fibonacci numbers.  Multiplying both sides by $F_{n+1}$
and rearranging terms gives $F_{n+1}^2 = F_{n+1} F_{n+2} - F_n F_{n+1}$.
Adding this identity to equation~\eqref{hypfib} gives:
\begin{eqnarray*}
F_{n+1}^2 + \sum_{i=0}^n F_i^2 & = & (F_{n+1} F_{n+2} - F_n F_{n+1}) + F_n
F_{n+1}, \quad\text{ so} \\
\sum_{i=0}^{n+1} F_i^2 & = & F_{n+1} F_{n+2},
\end{eqnarray*}
as required.

So by induction, we conclude that equation~\eqref{hypfib} holds for all $n
\in \naturals$.
\end{proof}



\subsection{Courtyard Tiling}

Induction served purely as a proof technique in the preceding examples.
But induction sometimes can serve as a more general reasoning tool.

MIT recently constructed a new computer science building.  As the project
went further and further over budget, there were some radical fundraising
ideas.  One plan was to install a big courtyard with dimensions $2^n
\times 2^n$:

\begin{center}
\begin{picture}(100,100)(-20,-20)
\put(40,-10){\makebox(0,0){$2^n$}}
\put(-10,40){\makebox(0,0){$2^n$}}
\put(0,0){\line(1,0){80}}
\put(0,10){\line(1,0){80}}
\put(0,20){\line(1,0){80}}
\put(0,30){\line(1,0){80}}
\put(0,40){\line(1,0){80}}
\put(0,50){\line(1,0){80}}
\put(0,60){\line(1,0){80}}
\put(0,70){\line(1,0){80}}
\put(0,80){\line(1,0){80}}
\put(0,0){\line(0,1){80}}
\put(10,0){\line(0,1){80}}
\put(20,0){\line(0,1){80}}
\put(30,0){\line(0,1){80}}
\put(40,0){\line(0,1){80}}
\put(50,0){\line(0,1){80}}
\put(60,0){\line(0,1){80}}
\put(70,0){\line(0,1){80}}
\put(80,0){\line(0,1){80}}
\end{picture}
\end{center}

One of the central squares would be occupied by a statue of a wealthy
potential donor.  Let's call him ``Bill''.  (In the special case $n = 0$,
the whole courtyard consists of a single central square; otherwise, there
are four central squares.)  A complication was that the building's
unconventional architect, Frank Gehry, insisted that only special L-shaped
tiles be used:

\begin{center}
\thicklines
\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}}
\thinlines
\put(25,25){\line(1,0){25}}
\put(25,25){\line(0,-1){25}}
\end{picture}
\end{center}

A courtyard meeting these constraints exists, at least for $n = 2$:

\begin{center}
\begin{picture}(100,100)
\thicklines
\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(62.5,62.5){\makebox(0,0){\textbf{B}}}
\end{picture}
\end{center}

For larger values of $n$, is there a way to tile a $2^n
\times 2^n$ courtyard with L-shaped tiles and a statue in the center?
Let's try to prove that this is so.

\begin{theorem}\label{bill}
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.

\textbf{Base case:} $P(0)$ is true because Bill fills the whole courtyard.

\textbf{Inductive step:} Assume that there is a tiling of a
$2^n \times 2^n$ courtyard with Bill in the center for some $n \geq
0$.  We must prove that there is a way to tile a $2^{n+1} \times
2^{n+1}$ courtyard with Bill in the center \dots.
\end{proof}

Now we're in trouble!  The ability to tile a smaller courtyard with Bill
in the center isn't much help in tiling a larger courtyard with Bill in
the center.  We haven't figured out how to bridge the gap between $P(n)$
and $P(n+1)$.

So if we're going to prove Theorem~\ref{bill} by induction, we're going to
need some \emph{other} induction hypothesis than simply the statement
about $n$ that we're trying to prove.  We'll discuss doing this in class
on Wednesday.

\iffalse

When this happens, your first fallback should be to look for a
\textit{stronger} induction hypothesis; that is, one which implies
your previous hypothesis.  For example, we could make $P(n)$ the
proposition that for \textit{every} location of Bill in a $2^n \times
2^n$ courtyard, there exists a tiling of the remainder.

This advice may sound bizzare: ``If you can't prove something, try to
prove something more grand!''  But for induction arguments, this makes
sense.  In the inductive step, where you have to prove $P(n) \implies
P(n+1)$, you're in better shape because you can {\em assume} $P(n)$,
which is now a more general, more useful statement.  Let's see how
this plays out in the case of courtyard tiling.

\begin{proof}
{\em (successful attempt)} The proof is by induction.  Let $P(n)$ be
the proposition that for every location of Bill in a $2^n \times 2^n$
courtyard, there exists a tiling of the remainder.

\textbf{Base case:} $P(0)$ is true because Bill fills the
whole courtyard.

\textbf{Inductive step:} Asume that $P(n)$ is true for some
$n \geq 0$; that is, for every location of Bill in a $2^n \times 2^n$
courtyard, 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 quadrant contains Bill (\textbf{B} in the diagram
below).  Place a temporary Bill (\textbf{X} in the diagram) in each of
the three central squares lying outside this quadrant:

\begin{center}
\begin{picture}(148,148)(-20,-20)
\thinlines
\put(0,0){\line(1,0){128}}
\put(0,0){\line(0,1){128}}
\put(128,128){\line(-1,0){128}}
\put(128,128){\line(0,-1){128}}
\put(64,0){\line(0,1){128}}
\put(0,64){\line(1,0){128}}
\put(56,72){\makebox(0,0){\textbf{X}}}
\put(56,56){\makebox(0,0){\textbf{X}}}
\put(72,56){\makebox(0,0){\textbf{X}}}
\put(48,80){\line(1,0){16}}
\put(48,48){\line(1,0){32}}
\put(80,48){\line(0,1){16}}
\put(48,48){\line(0,1){32}}
\put(96,96){\framebox(16,16){\textbf{B}}}
\put(32,-10){\makebox(0,0){$2^n$}}
\put(96,-10){\makebox(0,0){$2^n$}}
\put(-10,32){\makebox(0,0){$2^n$}}
\put(-10,96){\makebox(0,0){$2^n$}}
\end{picture}
\end{center}

Now we can tile each of the four quadrants by the induction
assumption.  Replacing the three temporary Bills with a single
L-shaped tile completes the job.  This proves that $P(n)$ implies
$P(n+1)$ for all $n \geq 0$.  The theorem follows as a special case.
\end{proof}

This proof has two nice properties.  First, not only does the argument
guarantee that a tiling exists, but also it gives an algorithm for
finding such a tiling.  Second, we have a stronger result: if Bill
wanted a statue on the edge of the courtyard, away from the pigeons,
we could accommodate him!

Strengthening the induction hypothesis is often a good move when an
induction proof won't go through.  But keep in mind that the stronger
assertion must actually be \textit{true}; otherwise, there isn't much
hope of constructing a valid proof!  Sometimes finding just the right
induction hypothesis requires trial, error, and insight.  For example,
mathematicians spent almost twenty years trying to prove or disprove
the conjecture that ``Every planar graph is
5-choosable''\footnote{5-choosability is a slight generalization of
5-colorability.  Although every planar graph is 4-colorable and
therefore 5-colorable, not every planar graph is 4-choosable.  If this
all sounds like nonsense, don't panic.  We'll discuss graphs,
planarity, and coloring in two weeks.}.  Then, in 1994, Carsten
Thomassen gave an induction proof simple enough to explain on a
napkin.  The key turned out to be finding an extremely clever
induction hypothesis; with that in hand, completing the argument is
easy!
\fi


\subsection{A Faulty Induction Proof}

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

Notice that no $n$ is mentioned in this assertion, so we're going to have
to reformulate it in a way that makes an $n$ explicit.  In particular,
we'll (falsely) prove that

\begin{falsethm}\label{horses}
In every set of $n \geq 1$ horses, all are the same color.
\end{falsethm}

This a statement about all integers $n \geq 1$ rather $\geq 0$, so it's
natural to use a slight variation on induction: prove $P(1)$ in the base
case and then prove that $P(n)$ implies $P(n+1)$ for all $n \geq 1$ in the
inductive step.  This is a perfectly valid variant of induction and is
{\em not} the problem with the proof below.

\begin{proof}
The proof is by induction.  The induction hypothesis, $P(n)$, will be
\begin{equation}\label{horsehyp}
\text{In every set of $n$ horses, all are the same color.}
\end{equation}

\textbf{Base case:} ($n=1$).  $P(1)$ is true, because in a set of horses
of size 1, there's only one horse, and this horse is definitely the same
color as itself.

\textbf{Inductive step:} Assume that $P(n)$ is true for some $n \geq 1$.
that is, assume that in every set of $n$ horses, all are the same color.
Now consider a set of $n+1$ horses:
%
\[
h_1,\ h_2,\ \dots,\ h_n,\ h_{n+1}
\]
%
By our assumption, the first $n$ horses are the same color:
%
\[
\underbrace{h_1,\ h_2,\ \dots,\ h_n,}_{\text{same color}}\ h_{n+1}
\]
%
Also by our assumption, the last $n$ horses are the same color:
%
\[
h_1,\ \underbrace{h_2,\ \dots,\ h_n,\ h_{n+1}}_{\text{same color}}
\]
%
Therefore, horses $h_1, h_2, \dots, h_{n+1}$ must all be the same
color, and so $P(n+1)$ is true.  Thus, $P(n)$ implies $P(n+1)$.

By the principle of induction, $P(n)$ is true for all $n \geq 1$.
\end{proof}

We've proved something false!  Is Math broken?  Should we all become
poets?

The error in this argument is in the sentence that begins,
``Therefore, horses $h_1$, $h_2$, $\dots$, $h_n$, $h_{n+1}$ must all
be the same color.''  The ``$\dots$'' notation creates the impression
that the sets $h_1, h_2, \dots, h_n$ and $h_2, \dots, h_n, h_{n+1}$
overlap.  However, this is not true when $n = 1$.  In that case, the
first set is just $h_1$ and the second is $h_2$, and these do not
overlap at all!

This mistake knocks a critical link out of our induction argument.  We
proved $P(1)$ and we \emph{correctly} proved $P(2) \implies P(3)$, $P(3)
\implies P(4)$, etc.  But we failed to prove $P(1) \implies P(2)$, and so
everything falls apart: we can not conclude that $P(2)$, $P(3)$, etc., are
true.  And, of course, these propositions are all false; there are horses
of a different color.

Students sometimes claim that the mistake in the proof is because $P(n)$
is false for $n \geq 2$, and the proof assumes something false, namely,
$P(n)$, in order to prove $P(n+1)$.  You should think about how to explain
to such a student why this claim would get no credit on a 6.042 exam.

\section{Strong Induction}

\subsection{The Strong Induction Principle}

A useful variant of induction is called {\em strong induction}.  Strong
induction and ordinary induction are used for exactly the same thing:
proving that a predicate $P(n)$ is true for all $n \in \naturals$.

\textbox{
\textbf{Principle of Strong Induction. }  Let $P(n)$ be a predicate.  If

\begin{itemize}
\item $P(0)$ is true, and
\item for all $n \in \naturals$, $P(0)$, $P(1)$, \dots, $P(n)$
\emph{together} imply $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \naturals$.
}

The only change from the ordinary induction principle is that strong
induction allows you to assume more stuff in the inductive step of your
proof!  In an ordinary induction argument, you assume that $P(n)$ is true
and try to prove that $P(n+1)$ is also true.  In a strong induction
argument, you may assume that $P(0)$, $P(1)$, \dots, and $P(n)$ are
\textit{all} true when you go to prove $P(n+1)$.  These extra assumptions
can only make your job easier.

\subsection{Products of Primes}

As a first example, we'll use strong induction to prove one of those
familiar facts that is almost, but maybe not entirely, obvious:
\begin{lemma}\label{prim}
Every integer greater than 1 is a product of primes.
\end{lemma}
Note that, by convention, any number is considered to be a product
consisting of one term, namely itself.  In particular, every prime is
considered to be a product whose terms are all primes.

\begin{proof}

We will prove Lemma~\ref{prim} by strong induction, letting the induction
hypothesis, $P(n)$, be
\[
n+2 \text{ is a product of primes}.
\]
So Lemma~\ref{prim} will follow if we prove that $P(n)$ holds for all $n
\geq 0$.

\textbf{Base Case:} $P(0)$ is true because $0+2$ is prime, and so is a
product of primes by convention.

\textbf{Inductive step:} Suppose that $n \geq 0$ and that $i+2$ is a
product of primes for every natural number $i < n+1$.  We must show that
$P(n+1)$ holds, namely, that $n+3$ is also a product of primes.  We argue
by cases:

If $n+3$ is itself prime, then it is a product of primes by convention, so
$P(n+1)$ holds in this case.

Otherwise, $n + 3$ is not prime, which by definition means $n+3 = km$ for
some natural numbers $k,m$ such that $2 \leq k,m < n+3$.  So $k-2$ is a
natural number less than $n+1$, which means that $(k-2)+2$ is a product of
primes by induction hypothesis.  That is, $k$ is a product of primes.
Likewise, $m$ is a product of primes.  So $km = n+3$ is also a product of
primes.  Therefore, $P(n+1)$ holds in this case as well.

So $P(n+1)$ holds in any case, which completes the proof by strong
induction that $P(n)$ holds for all natural numbers, $n$.

\end{proof}

Despite the name, strong induction is actually no more powerful than
ordinary induction.  In other words, any theorem that can be proved with
strong induction could also be proved with ordinary induction (using a
slightly more complicated indcution hypothesis).  But strong induction can
make some proofs a bit easier.  On the other hand, if $P(n)$ is easily
sufficient to prove $P(n+1)$, then it's better to use ordinary induction
for simplicity.

\subsection{Making Change}

The country Inductia, whose unit of currency is the Strong, has coins
worth 6S (6 Strongs), 10S and 15S.  Although the Inductians have some
trouble making small change like 11S or 29S, it turns out that they can
collect coins to make change for any number of Strongs greater than 29S.

Strong induction makes this easy to prove for $n+1 > 35$, because then
$(n+1)-6 > 29$, so by strong induction the Inductians can make change for
exactly $((n+1)-6)$S, and then they can add a 6S coin to get $(n+1)$S.  So
the only thing to do is check that they can make change for all the
amounts from 30 to 35, which is not too hard to do.

Here's a detailed writeup using the official format:

\begin{proof}

We prove the Inductians can make change for any amount greater than 29S by
strong induction.  The induction hypothesis, $P(n)$ will be:
\begin{quote}
If $n > 29$, then there is a collection of coins whose value is $n$
Strongs.
\end{quote}

Notice that $P(n)$ is an implication.  When the hypothesis of an
implication is false, we know the whole implication is true.  In this
situation, the implication is said to be \emph{vacuously} true.
So $P(n)$ will be vacuously true whenever $n \leq 29$.

We now proceed with the induction proof:

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

\textbf{Inductive step:}  We assume $P(i)$ holds for all $i \leq n$, and
prove that $P(n+1)$ holds.  We argue by cases:

\textbf{Case} ($n+1 \leq 29$): $P(n+1)$ is vacuously true in this case.

\textbf{Case} ($n+1$ = 30): $P(30)$ holds because the Inductians can use
five 6S coins.

\textbf{Case} ($n+1$ = 31):  Use a 6S coin, a 10S coin and a 15S coin.

\textbf{Case} ($n+1$ = 32): Use two 6S coins, and two 10S coins.

\textbf{Case} ($n+1$ = 33):   Use three 6S coin, and a 15S coin.

\textbf{Case} ($n+1$ = 34): Use a four 6S coins, and a 10S coin.

\textbf{Case} ($n+1$ = 35): Use a two 10S coins and a 15S coin.

\textbf{Case} ($n+1 > 35$): Then $n \geq (n+1) -6 > 29$, so by the strong
induction hypothesis, the Inductians can make change for $((n+1)-6)$S.
Now by adding a 6S coin, they can make change for $(n+1)$S.

So in any case, $P(n+1)$ is true,and we conclude by strong induction that
for all $n > 29$, the Inductians can make change for $n$S.

\end{proof}


\subsection{Unstacking}

In class on Friday, you will see strong induction used to analyze the
properties of a simple game involving stacks of blocks.

\iffalse
Here is another exciting 6.042 game that's surely about to sweep the
nation!

You begin with a stack of $n$ boxes.  Then you make a sequence of
moves.  In each move, you divide one stack of boxes into two nonempty
stacks.  The game ends when you have $n$ stacks, each containing a
single box.  You earn points for each move; in particular, if you
divide one stack of height $a + b$ into two stacks with heights $a$
and $b$, then you score $ab$ points for that move.  Your overall score
is the sum of the points that you earn for each move.  What strategy
should you use to maximize your total score?

As an example, suppose that we begin with a stack of $n = 10$ boxes.
Then the game might proceed as follows:
%
\[
\begin{array}{cccccccccccl}
\multicolumn{10}{c}{\textbf{Stack Heights}} & \quad & \textbf{Score} \\
\underline{10}&&&&&&&&& && \\
5&\underline{5}&&&&&&&& && 25 \text{ points} \\
\underline{5}&3&2&&&&&&& && 6 \\
\underline{4}&3&2&1&&&&&& && 4 \\
2&\underline{3}&2&1&2&&&&& && 4 \\
\underline{2}&2&2&1&2&1&&&& && 2 \\
1&\underline{2}&2&1&2&1&1&&& && 1 \\
1&1&\underline{2}&1&2&1&1&1&& && 1 \\
1&1&1&1&\underline{2}&1&1&1&1& && 1 \\
1&1&1&1&1&1&1&1&1&1 && 1 \\ \hline
\multicolumn{10}{r}{\textbf{Total Score}} & = & 45 \text{ points}
\end{array}
\]
%
On each line, the underlined stack is divided in the next step.  Can
you find a better strategy?

\subsubsection{Analyzing the Game}

Let's use strong induction to analyze the unstacking game.  We'll prove
that your score is determined entirely by the number of boxes ---your
strategy is irrelevant!

\begin{theorem}
Every way of unstacking $n$ blocks gives a score of $n(n-1)/2$ points.
\end{theorem}

There are a couple technical points to notice in the proof:

\begin{itemize}

\item The template for a strong induction proof is exactly the same as
for ordinary induction.

\item As with ordinary induction, we have some freedom to adjust
indices.  In this case, we prove $P(1)$ in the base case and prove
that $P(1), \dots, P(n-1)$ imply $P(n)$ for all $n \geq 2$ in the
inductive step.

\end{itemize}

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
every way of unstacking $n$ blocks gives a score of $n(n-1)/2$.

\textbf{Base case:} If $n = 1$, then there is only one
block.  No moves are possible, and so the total score for the game is
$1(1 - 1)/2 = 0$.  Therefore, $P(1)$ is true.

\textit{Inductive step:} Now we must show that $P(1)$,
\dots, $P(n-1)$ imply $P(n)$ for all $n \geq 2$.  So assume that
$P(1)$, \dots, $P(n-1)$ are all true and that we have a stack of $n$
blocks.  The first move must split this stack into substacks with
sizes $k$ and $n-k$ for some $k$ strictly between 0 and $n$.  Now the
total score for the game is the sum of points for this first move plus
points obtained by unstacking the two resulting substacks:
%
\begin{align*}
\text{total score}
    & = \text{(score for 1st move)} \\
    & \quad + \text{(score for unstacking $k$ blocks)} \\
    & \quad + \text{(score for unstacking $n - k$ blocks)} \\
    & = k(n-k) + \frac{k(k-1)}{2} + \frac{(n-k)(n-k-1)}{2} \\
    & = \frac{2nk - 2k^2 + k^2 - k + n^2 - nk - n - nk + k^2 +k}{2} \\
    & = \frac{n(n-1)}{2}
\end{align*}
%
The second equation uses the assumptions $P(k)$ and $P(n-k)$ and the
rest is simplification.  This shows that $P(1)$, $P(2)$, \dots,
$P(n)$ imply $P(n+1)$.

Therefore, the claim is true by strong induction.
\end{proof}
\fi

\section{The Well Ordering Principle}

Another proof method closely related to induction depends on the

\textbox{
\textbf{Well Ordering Principle.}
Every nonempty subset of natural numbers has a smallest element.
}

The Well Ordering Principle 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 Well Ordering Principle is capturing something special about the
natural numbers.

As for useless, it turns out that there's a routine way to transform any
proof using the Well Ordering Principle into a proof using Strong
Induction, and vice-versa.  (We won't take the time to describe the
transformations, though they are not hard.)  So Well Ordering could have
been used instead of induction in all the previous proofs.

In fact, looking back, we implicitly relied on the Well Ordering Principle
in the proof in Week 2 Notes that $\sqrt{2}$ is irrational.  That proof
assumed that any rational number, $q$, could be written as a fraction in
\textit{lowest terms}, that is, $q = m/n$ where $m$ and $n$ are integers
with no common factors.  How do we know this is always possible?

First, we can assume $m\geq 0$ (otherwise, replace $m/n$ by $-m/(-n)$), so
the set of natural numbers, $m$, such that $q = m/n$ for some integer,
$n$, is not empty.  Therefore, by Well Ordering, there must be a least
natural number, $m_0$, such that $q=m_0/n_0$ for some integer, $n_0$.  Now
if $m_0$ and $n_0$ had a common factor, $p>1$, then $(m_0/p)/(n_0/p)$
would be another way to express $q$ as a quotient of integers.  But since
$0 \leq (m_0/p) < m_0$. this contradicts the minimality of $m_0$.

We've using the Well-ordering Principle on the sly from early on!

Mathematicians often use Well Ordering because it often leads to shorter
proofs than induction.  On the other hand, Well Ordering proofs typically
involve proof by contradiction, so using it is not always the best
approach.  The choice of method is really a matter of style---but style
does matter.

\end{document}


\iffalse

\subsection{The Game of Nim}

Nim is an interesting game involving two players and some pennies.  We
will describe a strategy for playing Nim, and use strong induction to
verify that the strategy guarantees a win.

The game begins with a bunch of pennies, arranged in one or more rows.
For example, here we have three rows of pennies:

\[
\begin{array}{l}
\circ\ \circ\ \circ\ \\
\circ\ \circ\ \circ\ \circ\ \\
\circ\ \circ\ \circ\ \circ\ \circ\ 
\end{array}
\]

The two players take turns.  On each turn, a player must remove one or
more pennies, all from a single row.  The player who takes the last
penny wins.  For example, suppose that the first player removes two
pennies from the first row:

\[
\begin{array}{l}
\circ\ \\
\circ\ \circ\ \circ\ \circ\ \\
\circ\ \circ\ \circ\ \circ\ \circ\ 
\end{array}
\]

Now the second player removes all the pennies from the last
row, leaving this configuartion:

\[
\begin{array}{l}
\circ\ \\
\circ\ \circ\ \circ\ \circ\ 
\end{array}
\]

The first player then takes three pennies from the last row:

\[
\begin{array}{l}
\circ\ \\
\circ\ 
\end{array}
\]

The second player is now in trouble; she must take exactly
one of these two pennies.  Either way, the first player takes
the last penny and wins the game.

There is a compact way to describe a configuration in Nim: list the
number of pennies in each row.  For example, the starting
configuartion in the game above is $(3,4,5)$.  The game then passed
through the configurations $(1,4,5)$, $(1,4,0)$, and $(1,1,0)$.

\subsubsection{Nimsums}

A Harvard professor, Charles Bouton, discovered the optimal strategy
for Nim in 1901.  Bouton's strategy relies on a special mathematical
operation called a {\em Nimsum}.  The Nimsum of natural numbers $c_1,
\dots, c_k$ is itself a natural number that is computed as follows:

\begin{itemize}

\item Regard $c_1, \dots, c_k$ as binary numbers.

\item The $i$-th bit of the Nimsum is the \term{xor} of the $i$-th
bits of $c_1, \dots, c_k$.

\end{itemize}

(Xor is pronounced ``eks-or'' and is short for ``exclusive-or''.  The
xor of bits $b_1$ and $b_2$ is denoted $b_1 \oplus b_2$ and defined as
follows:

\[
\begin{array}{cc|c}
b_1 & b_2 & b_1 \oplus b_2 \\ \hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}
\]

As a consequence of this definition, the xor of bits $b_1,
\dots, b_k$ is 0 if the sum of the $b_i$ is even and 1 if the sum is
odd.  For example, $1 \oplus 0 \oplus 1 \oplus 1 = 1$ because $1 + 0 +
1 + 1 = 3$ is odd, but $1 \oplus 1 \oplus 0 \oplus 0 = 0$ because $1 +
1 + 0 + 0 = 2$ is even.)

As an example, the Nimsum of 3, 4, and 5 is computed as follows:

\[
\begin{array}{rcccr}
3 & = & 011 \\
4 & = & 100 \\
5 & = & 101 \\ \hline
  &   & 010 & = & 2
\end{array}
\]

Here, we xor each column of bits to obtain the Nimsum $010$,
which is the binary representation of 2.

\subsubsection{The Winning Strategy}

Suppose that $(c_1, \dots, c_k)$ is a configuration in Nim; that is,
there are a total of $k$ rows, and the $i$-th row contains $c_i$
pennies.  This configuration is called:

\begin{itemize}

\item {\em safe} if the Nimsum of $c_1, \dots, c_k$ is nonzero

\item {\em unsafe} if the Nimsum of $c_1, \dots, c_k$ is zero

\end{itemize}

In this way, all possible configurations in Nim are now partitioned
into two groups: the safe configurations and the unsafe
configurations.  Bouton's strategy is as follows:

\begin{itemize}

\item If you see a safe configuration on your turn, then select a move
that leaves your opponent with an unsafe configuration.

\item If you see an unsafe configuration on your turn, you're doomed.
Every possible move leaves your opponent with a safe configuration;
select among them arbitrarily and prepare to lose.

\end{itemize}

Thus, if the first player sees a safe position, she selects a move
that leaves the second player an unsafe position.  Every move
available to the second player then leaves the first player with
another safe position.  This cycle repeats until the first player wins
the entire game.

\subsubsection{An Example}

Let's use Bouton's strategy in one example game before trying to prove
a general theorem.  The bizarre French movie ``Last Year at
Marienbad'' features a Nim game beginning in the configuration $(1, 3,
5, 7)$.  Let's analyze this configuration by computing the Nimsum:

\[
\begin{array}{rcccr}
1 & = & 001 \\
3 & = & 011 \\
5 & = & 101 \\
7 & = & 111 \\ \hline
  &   & 000 & = & 0
\end{array}
\]

Since the Nimsum is zero, this is a hopeless situation for
the first player.  In particular, no matter what she does, the second
player is left with a safe configuration; that is, one in which the
Nimsum is nonzero.  For example, suppose that the first player removes
the entire fourth row.  Then the Nimsum becomes:

\[
\begin{array}{rcccr}
1 & = & 001 \\
3 & = & 011 \\
5 & = & 101 \\
0 & = & 000 \\ \hline
  &   & 111 & = & 7
\end{array}
\]

This is a safe configuration.  To maintain her advantage, the second
player needs to leave the first player in an unsafe position; that is,
a position with Nimsum zero.  Only one move accomplishes this:
removing three pennies from the third row:

\[
\begin{array}{rcccr}
1 & = & 001 \\
3 & = & 011 \\
2 & = & 010 \\
0 & = & 000 \\ \hline
  &   & 000 & = & 0
\end{array}
\]

Now the first player is again confronted with an unsafe position, one
with a Nimsum of zero.  No matter what she does, the second player
will be left with a safe position.  For example, suppose that the
first player takes all three pennies from the second row.  Then the
second player is left with:

\[
\begin{array}{rcccr}
1 & = & 001 \\
0 & = & 000 \\
2 & = & 010 \\
0 & = & 000 \\ \hline
  &   & 011 & = & 3
\end{array}
\]

Sure enough, this is a safe position.  One again, the second player
needs to leave the first player in an unsafe position.  Removing one
penny from the third row accomplishes this:

\[
\begin{array}{rcccr}
1 & = & 001 \\
0 & = & 000 \\
1 & = & 001 \\
0 & = & 000 \\ \hline
  &   & 000 & = & 0
\end{array}
\]

The first player is clearly going to lose.  She must take one of the
two remaining pennies, leaving the second player to take the other and
win the game.

\subsubsection{Proof of Correctness}

Now let's prove that Bouton's strategy works.  We'll need two lemmas.

\begin{lemma}
\label{lem:unsafe}
If a player sees an unsafe configuration on her turn, then every
possible move leaves her opponent with a safe configuration.
\end{lemma}

\begin{proof}
Suppose that the player sees an unsafe configuration; that is, a
configuration $(c_1, \dots, c_k)$ with Nimsum zero.  Then the player
must remove pennies from some row $j$, leaving $c_j' < c_j$ pennies
behind.  In binary, the numbers $c_j$ and $c_j'$ must differ in some
bit position.  But then the Nimsum of the resulting configuration has
a 1 in that bit position.  Therefore, the Nimsum is nonzero, meaning
that the resulting configuration is safe.
\end{proof}

\begin{lemma}
\label{lem:safe}
If a player sees a safe configuration on her turn, then she has a move
that leaves her opponent with an unsafe configuration.
\end{lemma}

\begin{proof}
Suppose that the player sees a configuration $(c_1, \dots, c_k)$ with
Nimsum $s \neq 0$.

Let $i$ be the position of the most-significant 1 in the binary
representation of $s$.  Since the $i$-th position of $s$ is nonzero,
there must be some row size $c_j$ that is nonzero in the $i$-th
position as well.  Suppose that the player removes all but $c_j'$
pennies from the $j$-th row, where $c_j'$ differs from $c_j$ in
exactly those positions where $s$ has a 1.

We must check that $c_j'$, the number of pennies the player leaves
behind, is less than $c_j$, the number of pennies originally in the
$j$-th row.  This is true because $c_j$ has a 1 in the $i$-th
position, $c_j'$ has a 0 in this position, and the two numbers agree
in all higher positions.

Modifying the game configuration by changing $c_j$ by $c_j'$ reduces
the Nimsum to zero, because $c_j$ and $c_j'$ disagree in exactly those
positions where the original Nimsum had a 1.
\end{proof}

An example may clarify the preceding argument.  Suppose that a player
sees the configuration $(1, 2, 4, 4)$.  We can compute the Nimsum as
follows:

\[
\begin{array}{rcccr}
1 & = & 001 \\
2 & = & 010 \\
4 & = & 100 \\
4 & = & 100 \\ \hline
  &   & 011 & = & 3
\end{array}
\]

The Nimsum is 011 in binary.  The most significant 1 is in
the second position from the right.  The number of pennies in the
second row, 010 in binary, also has a 1 in this position.  We should
leave 001 pennies in this row, since this differs from the number of
pennies there now (010) in every position where the Nimsum (011) has a
1.  Now we compute the Nimsum of the resulting configuration:

\[
\begin{array}{rcccr}
1 & = & 001 \\
1 & = & 001 \\
4 & = & 100 \\
4 & = & 100 \\ \hline
  &   & 000 & = & 0
\end{array}
\]

As expected, this is an unsafe position.

We're ready to prove the main result.

\begin{theorem}
If the current player has a safe position, then she can guarantee a
win.  Otherwise, the other player can guarantee a win.
\end{theorem}

The proof uses induction, with the statement of the theorem as the
induction hypothesis.  This hypothesis is quite complicated!  Suppose
that we define three smaller propositions:
\begin{eqnarray*}
A & \eqdef & \text{current player has a safe position} \\
B & \eqdef & \text{current player can guarantee a win} \\
C & \eqdef & \text{next player can guarantee a win}
\end{eqnarray*}


In these terms, the induction hypothesis is $(A \rightarrow
B) \wedge (\overline{A} \rightarrow C)$.  Induction hypotheses
containing implications are always a bit tricky, but this one has {\em
two} implications!  Some square-bracketed comments are included in the
proof to clairfy the structure.

\begin{proof}
The proof is by strong induction on $n$, the total number of pennies
remaining.  Let $P(n)$ be the proposition that in all Nim
configurations with $n$ pennies, if the current player has a safe
position, then she can guarantee a win and, otherwise, the other
player can guarantee a win.

\textbf{Base case:} ($n = 0$).  That is, no pennies remain.  This is an
unsafe position.  Therefore, the first implication is trivially true
because the if-part is false.  The second implication is also true,
because when the current player is left with no pennies, the other player
has just won the game.  [In other words, the proposition $(A \rightarrow
B) \wedge (\overline{A} \rightarrow C)$ is true because $A$ is false and
$C$ is true.]

\textbf{Inductive step:} We must show that for all $n \geq 0$, the
propositions $P(0), \dots, P(n)$ imply $P(n+1)$.  Assume $P(0), \dots,
P(n)$ and consider a configuration with $n + 1$ pennies remaining.  Now we
must show two things:

\begin{enumerate}

\item {\em If the configuration is safe, the current player can
guarantee a win.}  Suppose that the configuration is safe.  By
Lemma~\ref{lem:safe}, the current player has a move that leaves the
next player with an unsafe configuration involving fewer than $n + 1$
pennies.  If $m < n + 1$ pennies remain, then assumption $P(m)$
implies that the player {\em after} the next player (which is the
current player) can guarantee a win.  [This shows $A \rightarrow B$.]

\item {\em If the configuration is unsafe, the next player can
guarantee a win.}  Suppose that the configuration is unsafe.  By
Lemma~\ref{lem:unsafe}, every move leaves the next player with a safe
configuration involving $m < n + 1$ pennies.  The assumption $P(m)$
then implies that the next player can guarantee a win.  [This shows
$\overline{A} \rightarrow C$.]

\end{enumerate}

Putting these arguments together gives $P(n+1)$.  [That is, $A
\rightarrow B$ and $\overline{A} \rightarrow C$ together imply $(A
\rightarrow B) \wedge (\overline{A} \rightarrow C)$.]  Therefore, the
theorem follows by the principle of induction.
\end{proof}
\fi


\iffalse

\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 the Well Ordering 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 \divides b$) if
there exists an integer $k$ such that $ak = b$.
\end{definition}

For example, $7 \divides 21$, since $7 \cdot 3 = 21$.  We can specify the
primes nicely using ``divides.''

\begin{lemma*}
An integer, $n$, is a {\em prime} iff [$n > 1$, and 1 and $n$ are the only
positive integers that divide it].
\end{lemma*}
An integer $n > 1$ that is not prime is said to be {\em composite}.

In addition to this Lemma, 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 $p$ is  a prime,  divides $ab$, then either $p \divides a$ or $p \divides b$.
\end{fact}

For example, $7 \divides 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 \divides 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.\footnote{Similar to \emph{defining} (in
Section~\ref{sec:ellipsis}) the sum of an empty set of numbers to
be~0, we \emph{define} the product of an empty set of numbers to
be~1.}  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. 
The proof is by contradiction: Assume, contrary to the claim, that
there exist positive integers that can be written as products of
primes in more than one ways. By the least-number principle, one of
these integers is the \emph{smallest} to have this property. Call this
integer $n$, and let 
\begin{eqnarray*}
n & = & p_1 p_2 \cdots p_j \\
  & = & q_1 q_2 \cdots q_k
\end{eqnarray*}
be two of the (possibly many) ways to write it as a product of
primes.  Then $p_1 \divides n$ and so $p_1 \divides 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 \emph{smaller} than $n$ that can be written as a
product of primes in two distinct ways. But this contradicts the
selection of $n$ as the smallest positive integer with this property.

This concludes the proof of the theorem.
\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.
\fi
