\documentclass[12pt,twoside]{article}
\usepackage{light}

\newtheorem{false-theorem}[theorem]{False Theorem}

\begin{document}

\lecture{Induction, I.}{September 14, 2004}

\section{A Warmup Puzzle}

In principle, a proof should establish the truth of a proposition with
absolute certainty.  In practice, however, many purported proofs
contain errors: overlooked cases, logical slips, and even algebra
mistakes.  But in a well-written proof, even if there is a bug, one
should at least be able to pinpoint a specific statement that does not
logically follow.  See if you can find the first error in the
following argument.

\begin{false-theorem}
$420 > 422$
\end{false-theorem}

\begin{proof}
We will demonstrate this fact geometrically.  We begin with a $20
\times 21$ rectangle, which has area $420$:

\begin{center}
\begin{picture}(130,130)(-20,-20)
\thicklines
\put(0,0){\line(1,0){110}}
\put(0,0){\line(0,1){110}}
\put(110,110){\line(-1,0){110}}
\put(110,110){\line(0,-1){110}}
\thinlines
\put(0,110){\line(1,-1){110}}
\put(55,-10){\makebox(0,0){21}}
\put(-10,55){\makebox(0,0){20}}
\end{picture}
\end{center}

\noindent Now we cut along the diagonal as indicated above and slide
the upper piece parallel to the cut until it has moved exactly 2 units
leftward.  This leaves a couple stray corners, which are 2 units wide
and just over 2 units high.

\begin{center}
\begin{picture}(150,168)(-20,-20)
\thicklines
\put(0,0){\line(1,0){100}}
\put(0,0){\line(0,1){120}}
\put(90,132){\line(-1,0){100}}
\put(90,132){\line(0,-1){120}}
\put(100,0){\line(-5,6){110}}
\thinlines
\put(0,120){\line(0,1){12}}
\put(90,12){\line(0,-1){12}}
\put(50,-10){\makebox(0,0){19}}
\put(-10,50){\makebox(0,0){20}}
\put(12,125){\makebox(0,0){$> 2$}}
\put(78,8){\makebox(0,0){$> 2$}}
\put(-5,140){\makebox(0,0){$2$}}
\put(95,-10){\makebox(0,0){$2$}}
\end{picture}
\end{center}

\noindent Finally, we snip off the two corners and place them together
to form an additional small rectangle:

\begin{center}
\begin{picture}(160,152)(-20,-20)
\thicklines
\put(0,0){\line(1,0){90}}
\put(0,0){\line(0,1){132}}
\put(90,132){\line(-1,0){90}}
\put(90,132){\line(0,-1){132}}
\thinlines
\put(90,12){\line(-5,6){90}}
\put(50,-10){\makebox(0,0){19}}
\put(-10,50){\makebox(0,0){20}}
\put(12,126){\makebox(0,0){$> 2$}}
\put(102,6){\makebox(0,0){$> 2$}}
\thicklines
\put(150,70){\line(1,0){10}}
\put(150,70){\line(0,1){12}}
\put(160,82){\line(-1,0){10}}
\put(160,82){\line(0,-1){12}}
\thinlines
\put(160,70){\line(-5,6){10}}
\put(155,60){\makebox(0,0){2}}
\put(136,76){\makebox(0,0){$> 2$}}
\end{picture}
\end{center}

\noindent Now we have two rectangles, a large one with area just over
$(20 + 2) \times 19 = 418$ and a small one with area just over $2
\times 2 = 4$.  Thus, the total area of the resulting figure is a bit
over $418 + 4 = 422$.  By conservation of area, 420 is equal to just a
little bit more than 422.
\end{proof}

Where is the error?

\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 \mathbb{N}$, if student $n$ gets candy,
then student $n + 1$ also gets candy.
\end{enumerate}

\noindent 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 \mathbb{N}$, $P(n)$ implies $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \mathbb{N}$.
}

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 \mathbb{N}$, $P(n)$ implies
$P(n+1)$.  Given these facts, the induction principle says that $P(n)$
is true for all $n \in \mathbb{N}$.  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.  Mathematicians find this intuition so compelling that
induction is always either taken as an axiom or else proved from more
primitive axioms, which are themselves specifically designed so that
induction \textit{is} provable.  In any case, the induction principle
is a core truth of mathematics.

\section{Using Induction}

Induction is by far the most important proof technique in computer
science.  Generally, induction is used to prove that some statement
holds for all natural values of a variable.  For example, here is a
classic formula:

\begin{theorem}
\label{th:sum-to-n}
For all $n \in \mathbb{N}$:
%
\[
1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}
\]
\end{theorem}

The left side of the equation represents the sum of all the numbers
from 1 to $n$.  You're supposed to guess the pattern and mentally
replace the $\ldots$ 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, \ldots, 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 special cases:

\begin{itemize}

\item If $n = 1$, then there is only one term in the summation, and so
$1 + 2 + 3 + \ldots + 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 + \ldots + n = 0$.

\end{itemize}

\noindent The $\ldots$ 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 + \ldots + n = n(n+1)/2$''.  Recast in terms of this
predicate, the theorem claims that $P(n)$ is true for all $n \in
\mathbb{N}$.  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 \mathbb{N}$, $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 + \ldots + n & = \frac{n(n+1)}{2}
\end{align*}
%
in order to prove $P(n+1)$:
%
\begin{align*}
1 + 2 + 3 + \ldots + 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 + \ldots + 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''.

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

\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.  Let $P(n)$ be the predicate:
%
\begin{align*}
1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}
\end{align*}

\noindent \textit{Base case:} $P(0)$ is true, because both sides of
the equation are zero.

\noindent \textit{Inductive step:} Assume that $P(n)$ is true, where
$n$ is any natural number.  Then $P(n+1)$ is also true, because:
%
\begin{align*}
1 + 2 + 3 + \ldots + n + (n+1)
    & = \frac{n(n+1)}{2} + (n+1) \\
    & = \frac{(n+1)(n+2)}{2}
\end{align*}
%
The first step uses the assumption $P(n)$, and the second follows by
simplification.

Therefore, $P(n)$ is true for all natural $n$ by induction, and the
theorem is proved.
\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.

\section{A Divisibility Theorem}

An integer $a$ \term{divides} an integer $b$ if $b$ is a multiple of
$a$.  This is denoted $a \mid b$.  For example, $3 \mid (5^3 - 5)$,
since $5^3 - 5 = 120$ is a multiple of 3.  More generally, we have the
following theorem:

\begin{theorem}
$\forall\ n \in \mathbb{N} \quad 3 \mid (n^3 - n)$
\end{theorem}

Let's try to prove this with induction.  The first challenge is always
selecting the right induction hypothesis, $P(n)$.  Your first instinct
should be to lift the induction hypothesis directly from the claim.  Thus,
in this case, we should first try letting $P(n)$ be the predicate ``$3
\mid (n^3 - n)$''.  (This doesn't always work out -- as we'll see in a
later example -- but it does work in this case.)

Now we must address the base case by proving that $P(0)$ is true.  As
is often the case, this is easy: $3 \mid (0^3 - 0)$, since 0 is a
multiple of 3.  (Specifically, $3 \cdot 0 = 0$.)

Our next task, the inductive step, is typically the most difficult
part of an induction proof.  We must show that $P(n)$ implies
$P(n+1)$.  Thus, as usual when proving an implication, we
\textit{assume} $P(n)$ in order to \textit{prove} $P(n+1)$.  Writing
out what these two expressions actually mean is often helpful.  In
this case, we assume $P(n)$:
%
\[
3 \mid (n^3 - n)
\]
%
in order to prove $P(n+1)$:
\[
3 \mid ((n+1)^3 - (n+1))
\]
These two statements look somewhat similar, but how can we use the
first to prove the second?  For lack of any other ideas, let's
multiply out the expression in the second statement:
%
\begin{align*}
3 \mid ((n+1)^3 - (n+1))
  & \iff 3 \mid (n^3 + 3n^2 + 3n + 1 - n - 1) \\
  & \iff 3 \mid (n^3 + 3n^2 + 2n) \\
\end{align*}
%
Aha!  Notice that the last expression is equal to $n^3 - n$ plus $3n^2
+ 3n$.  Since $3n^2 + 3n$ is a multiple of 3 and $n^3 - n$ is a
multiple of 3 by assumption, their sum must also be a multiple of 3.
Therefore, $((n+1)^3 - (n+1)$ must also be a multiple of 3.

Playing around with $P(n)$ and $P(n+1)$ in this way, trying to
understand how the two are related, is pretty typical when one is
searching for an induction argument.  However, what we've done so far
is only scratchwork.  What remains is to organize our reasoning into a
clear proof.

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that $3 \mid (n^3 -
n$).

\noindent \textit{Base case:} $P(0)$ is true because $3 \mid 0^3 - 0$.

\noindent \textit{Inductive step:} Assume that $P(n)$ is true, where
$n$ is any natural number.  Then:
%
\begin{align*}
3 \mid (n^3 - n)
& \implies 3 \mid (n^3 - n) + 3 (n^2 + n) \\
& \implies 3 \mid n^3 + 3n^2 + 3n + 1 - n - 1 \\
& \implies 3 \mid (n+1)^3 - (n+1)
\end{align*}
%
The first implication relies on the fact that $3 (n^2 + n)$ is
divisible by 3.  The remaining implications involve only rewriting the
expression on the right.  The last statement is $P(n+1)$, so we've
proved that $P(n)$ implies $P(n+1)$ for all $n \in \mathbb{N}$.

By the principle of induction, $P(n)$ is true for all $n \in
\mathbb{N}$, which proves the claim.
\end{proof}

This proof would look quite mysterious to anyone not privy to the
scratchwork we did beforehand.  In particular, one might ask how we
had the foresight to introduce the magic term $3 (n^2 + n)$.  Of
course, this was not foresight at all; we just worked backward
initially!

\section{A Faulty Induction Proof}

Sometimes we want to prove that a statement is true for, say, all
integers $n \geq 1$ rather than all integers $n \geq 0$.  In this
circumstance, we can 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{false-theorem}
All horses are the same color.
\end{false-theorem}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that in
every set of $n$ horses, all are the same color.

\noindent \textit{Base case:} $P(1)$ is true, because all horses in a
set of 1 must be the same color.

\noindent \textit{Inductive step:} Assume that $P(n)$ is true, where
$n$ is a positive integer; 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,\ \ldots,\ h_n,\ h_{n+1}
\]
%
By our assumption, the first $n$ horses are the same color:
%
\[
\underbrace{h_1,\ h_2,\ \ldots,\ 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,\ \ldots,\ h_n,\ h_{n+1}}_{\text{same color}}
\]
%
Therefore, horses $h_1, h_2, \ldots, 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$.  The
theorem is a special case where $n$ is equal to the number of horses
in the world.
\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$, $\ldots$, $h_n$, $h_{n+1}$ must all
be the same color.''  The ``$\ldots$'' notation creates the impression
that the sets $h_1, h_2, \ldots, h_n$ and $h_2, \ldots, 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 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(3)$, $P(4)$,
etc. are true.  And, of course, these propositions are all false;
there are horses of a different color.

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

\noindent 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}

\noindent A courtyard meeting these constraints exsists, 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}

\noindent 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}
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.

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

\noindent \textit{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...
\end{proof}

Now we're in trouble!  The ability to tile a smaller courtyard with
Bill in the center does not help tile a larger courtyard with Bill in
the center.  We can not bridge the gap between $P(n)$ and $P(n+1)$.
The usual recipe for finding an inductive proof will not work!

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.

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

\noindent \textit{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}

\noindent 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!

\section{Another Faulty Proof}

\begin{false-theorem}
I can lift all the sand on the beach.
\end{false-theorem}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate, ``I can lift
$n$ grains of sand.''  The base case $P(1)$ is true because I can
certainly lift one grain of sand.  In the inductive step, assume that
I can lift $n$ grains of sand to prove that I can lift $n+1$ grains of
sand.  If I can lift $n$ grains of sand, then surely I can lift $n+1$;
one grain of sand will not make any difference.  Therefore $P(n)
\implies P(n+1)$.  By induction, $P(n)$ is true for all $n \geq 1$.
The theorem is the special case where $n$ is equal to the number of
grains of sand on the beach.
\end{proof}

The flaw here is in the bogus assertion that I can lift $n+1$ grains
of sand because I can lift $n$ grains.  It is hard to say for exactly
which $n$ this is false, but certainly there is some value!

There is a field of mathematics 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.  That might better model the
situation here, since my lifts would probably gradually grow more and
more sorry-looking as $n$ approached my maximum.  We will not be using
fuzzy logic in this class, however.  At least not intentionally.
\end{document}
