\hyperdef{in}{duction}{\section{Ordinary Induction}}

The reasoning that led us to conclude every student gets a candy bar is 
essentially all there is to induction.
\textbox{ 
\noindent \textbf{The Principle of Induction.}

\noindent Let $P(n)$ be a predicate.  If
%
\noindent \begin{itemize}
\item $P(0)$ is true, and
\item $P(n) \QIMPLIES P(n+1)$ for all nonnegative integers, $n$,
\end{itemize}
%
\noindent then
\noindent \begin{itemize}
\item $P(m)$ is true for all nonnegative integers, $m$.
\end{itemize}
}
\iffalse
So our claim that all the Professor's students get a candy bar was simply
an application of the Induction Rule with $P(n)$ defined to be the
predicate, ``student $n$ gets a candy bar.''
\fi

Since we're going to consider several useful variants of induction in
later sections, we'll refer to the induction method described above as
\term{ordinary induction} when we need to distinguish it.  Formulated as 
a proof rule, this would be
\begin{rul*} \textbf{Induction Rule}
\Rule{P(0), \quad \forall n \in \naturals\, [P(n) \QIMPLIES P(n+1)]}
{\forall m \in \naturals.\, P(m)}
\end{rul*}

This general induction rule works for the same intuitive reason that all
the students get candy bars, and we hope the explanation using candy bars
makes it clear why the soundness of the ordinary induction can be taken
for granted.  In fact, the rule is so obvious that it's hard to see what
more basic principle could be used to justify it.\footnote{But see
section~\ref{CP0303:versusWO}.}  What's not so obvious is how much mileage 
we get by using it.

\subsection{Using Ordinary Induction}

Ordinary induction often works directly in proving that some statement
about nonnegative integers holds for all of them.  For example, here is a
classic formula:

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

The left side of equation~\eqref{C0301:hyp} represents the sum of all the
numbers from 1 to $n$.  Here the dots ($\cdots$) indicate a pattern you're
supposed to be able to guess so you can mentally fill in the remaining
terms. However, the meaning of this sum 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.  By
convention, the sum in this case is 0.
%
\end{itemize}
%
So while the dots notation is convenient, you have to watch out for these
special cases where the notation is misleading!  (In fact, whenever you
see the dots, you should be on the lookout to be sure you understand the
pattern.)

We could eliminate the need for guessing by rewriting the left side
of~\eqref{C0301:hyp} with \term{summation notation}:
\[
\sum_{i=1}^n i
\qquad \text{or} \qquad
\sum_{1 \leq i \leq n} i.
\]
Both of these expressions denote 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$.  Both these summation expressions make it clear 
what~\eqref{C0301:hyp} means when $n=1$.  The second expression makes 
it clear that when $n=0$, there are no terms in the sum, though you 
still have to know the convention that a sum of no numbers equals 0 
(the \emph{product} of no numbers is 1, by the way).

Now let's use the induction principle to prove Theorem~\ref{C0301: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) \QIMPLIES 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{equation}\label{C0301:Pn}
1 + 2 + 3 + \cdots + n  = \frac{n(n+1)}{2}
\end{equation}
in order to prove $P(n+1)$:
\begin{equation}\label{C0301:Pn1}
1 + 2 + 3 + \cdots + n + (n+1) = \frac{(n+1)(n+2)}{2}
\end{equation}
These two equations are quite similar; in fact, adding $(n+1)$ to both
sides of equation~\eqref{C0301:Pn} and simplifying the right side 
gives the equation~\eqref{C0301:Pn1}:
\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 nonnegative integer $n$, so this establishes the second fact
required by the induction principle.  Therefore, the induction principle
says that the predicate $P(n)$ is true for all nonnegative $n$, so the 
theorem is proved.

\iffalse
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.
\fi

\iffalse
\begin{notesproblem}
Prove by induction on $n$ that
\hyperdef{geometric}{sum}{\begin{equation}\label{geometric-n}
1+r+r^2+\cdots+r^n = \frac{r^{n+1}-1}{r-1}
\end{equation}}
for all $n \in \naturals$ and numbers $r\neq 1$.
\end{notesproblem}
\fi

\subsection{A Template for Induction Proofs}
\label{C0301:templ-induct-proofs}

The proof of Theorem~\ref{C0301: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
nonnegative $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 nonnegative
integer $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 nonnegative integer $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 nonnegative
  $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 clearer.

\subsection{A Clean Writeup}

The proof of Theorem~\ref{C0301: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{C0301:hyp}.

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

\textbf{Inductive step:} Assume that $P(n)$ is true, where
$n$ is any nonnegative integer.  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 nonnegative $n$.
\end{proof}

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

\subsection{Powers of Odd Numbers}

\begin{fact*}
The $n$th power of an odd number is odd, for all nonnegative integers, $n$.
\end{fact*}
The proof in Chapter~\ref{C01} that $\sqrt[n]{2}$ is irrational used this 
``obvious'' fact.  Instead of taking it for granted, we can prove this fact
by induction.
The proof will require a simple Lemma.
\begin{lemma*}
The product of two odd numbers is odd.
\end{lemma*}
To prove the Lemma, note that the odd numbers are, by definition, the
numbers of the form $2k+1$ where $k$ is an integer.  But
\[
(2k+1)(2k'+1) = 2(2kk' + k + k')+1,
\]
so the product of two odd numbers also has the form of an odd number,
which proves the Lemma.

Now we will prove the Fact using the induction hypothesis
\[
P(n) \eqdef \text{if $a$ is an odd integer, then so is $a^{n}$}.
\]

The base case $P(0)$ holds because $a^{0} =1$, and 1 is odd.

For the inductive step, suppose $n\geq 0$, $a$ is an odd number and $P(n)$
holds.  So $a^n$ is an odd number.  Therefore, $a^{n+1} = a^{n}a$ is a
product of odd numbers, and by the Lemma $a^{n+1}$ is also odd.  This
proves $P(n+1)$, and we conclude by induction that $P(n)$ holds for
nonnegative integers $n$.

\iffalse
An alternative proof of Lemma~\ref{finmin} that every partial order on a
nonempty finite set has a minimal element can be based on induction.  This
time there is no $n$ mentioned, so we better find one.

We'll use the induction hypothesis
\[
P(n) \eqdef \text{a strict partial order on a set of size $n$ has a minimal
  element}.
\]

As a base case, we'll use $n=1$.  Now $P(1)$ holds because in a
one-element partial order, the element is minimal (and maximal) by
definition.

For the inductive step, assume $P(n)$ holds and consider a strict partial
order, $R$, on a set, $A$, of size $n+1$ for $n \geq 1$.  We will prove
that $A$ has a minimal element.

Now $A$ has 2 or more elements, so pick one and call it $a_0$.  If $a_0$
is a minimal element, then we are done.  Otherwise, let $A'$ be the set $A
- \set{a_0}$ and $R'$ be the relation $R$ restricted to $A'$.

Now it's easy to check that $R'$ is a strict partial order on set $A'$
whose size is $n$.  So by induction, there is an $R'$-minimal element, $m
\in A'$.  We claim that $m$ is also a minimal element of $A$.

Now there is no element $a' \in A'$ such that $a'\,R\,m$, so to prove
$m$ is minimal in $A$,  as long as it is not true that $a_0\,R\, m$

This element $m$ will also be minimal in $A$ unless

Since $a_0$ is not minimal, there is an element $a_1 \in A'$ such that
$a_1\,R\,a_0$.

\fi

\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 the Stata Center which houses the Computer
Science and AI Laboratory.  During development, the project went further
and further over budget, and there were some radical fundraising ideas.
One rumored 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, supposedly 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.

%Hide after lecture:

%We'll describe some hypotheses that do work in class this week.

%end hide

%\iffalse  %Unhide after lecture:

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 bizarre: ``If you can't prove something, try to
prove something grander!''  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 powerful 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:} Assume 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  %end UnHide after lecture

\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{falseproof}

The proof is by induction on $n$.  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}}
\]
%
So $h_1$ is the same color as the remaining horses besides $h_{n+1}$, and
likewise $h_{n+1}$ is the same color as the remaining horses besides
$h_1$.  So $h_1$ and $h_{n+1}$ are the same color.  That is, 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{falseproof}

We've proved something false!  Is Math broken?  Should we all become
poets?  No, this proof has a mistake.
%hide after lecture:
% We'll explain where in class.
%end hide

%\iffalse %UNHIDE after lecture

The error in this argument is in the sentence that begins, ``So $h_1$ and
$h_{n+1}$ are the same color.''  The ``$\dots$'' notation creates the
impression that there are some remaining horses besides $h_1$ and
$h_{n+1}$.  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 there are no
remaining horses besides them.  So $h_1$ and $h_2$ need not be the same
color!

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.

%\fi %end unhide

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.


\endinput