\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\{#1\}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }

\begin{document}

\begin{center}
{\Large Notes for Tutorial 6} \\
6.042 - March 14 and March 17, 2003 \\
\bigskip
\end{center}

Ideally, every student should come out of this tutorial knowing how to
write a simple induction proof.  Fat chance, but give it a shot!
There are five parts to these notes:

\begin{itemize}
\item A miniquiz/review of induction.
\item A fallacious proof involving missing base cases.
\item A fallacious proof involving buildup error.
\item A complicated induction problem.
\item Followup miniquiz.
\end{itemize}

\section*{Miniquiz}

The purpose of this easy quiz is to see if your students understand
how to do an elementary induction.  Walk around and see how they're
doing.  Afterward, work out a careful proof on the board and take
their questions.  I'd suggest that you write out the proof {\em
completely} on the board and discuss not only correctness, but
clarity.

\begin{claim}
The following equation holds for all natural numbers $n$:

\beqn
1^2 + 2^2 + 3^2 + \ldots + n^2 & = & \frac{n(2n+1)(n+1)}{6}
\eeqn
\end{claim}

In the proof below, I've italicized some points that you might want to
bring up.  Even before getting into the proof, you might want to
recall the induction principle:

\[
\begin{array}{l}
P(0) \\
\forall n \ P(n) \rightarrow P(n+1) \\ \hline
\forall n \ P(n)
\end{array}
\]

Remember to interpret all these symbols for them.  Also, I'd suggest
that you tell them to take notes on a separate page, because you're
going to collect their first-attempt proofs.  (Don't do this until the
end so that they can consult their work during the discussion.)

\begin{proof}

{\em Step 1: A good proof starts by describing the overall method:
induction, contradiction, proving contrapositive, etc.  It is a good
idea to mention the variable you're ``inducting'' on, if there is any
possible ambiguity.}

The proof is by induction on $n$.

{\em Step 2: Define your predicate or ``induction hypothesis''.  Never
leave the induction hypothesis unstated!  In rare cases, if the
predicate is really complicated and appears very clearly in the claim,
you might get a cleaner proof by just referring back to the claim in
your definition.  But don't do this unless you have to.}

Let $P(n)$ be the predicate $\sum_{k=1}^n k^2 = n(2n+1)(n+1)/6$.

{\em Notice that $P(n)$ is {\bf not} an ordinary, real-valued
function, it is a predicate-- a statement that involves $n$ and is
either true or false.  Very often students write something like ``Let
$P(n) = n(2n+1)(n+1)/6$'' or ``$P(n+1) = P(n) + (n+1)^2$''.  If anyone
does that this year, they will be fed to a pack of hungry lions.}

{\em Step 3: Prove the base case, $P(0)$.  (Of course, we won't always
use this as the base case, but I suggest you defer this issue until a
bit later, since it is somewhat involved.)}

First, we prove the base case, $P(0)$:

\beqn
\sum_{k=1}^0 k^2 & = & \frac{0(2\cdot 0 + 1) (0 + 1)}{6}
\eeqn

\noindent The left side is equal to zero, because the sum contains no
terms.  Since the right side is also zero, equality holds and $P(0)$
is true.

{\em Usually the base case is trivial, but not always.  And messing up
the base case invalidates your whole proof!  (As we shall see...)}

{\em Step 4: Prove that $P(n)$ implies $P(n+1)$ for all $n \geq 0$.
This is done by assuming that $P(n)$ is true, where your only
guarantee is that $n \geq 0$, and using that fact to show that
$P(n+1)$ is true as well.  This is usually the hard part of an
induction proof.}

Next, we show that for all $n \geq 0$, $P(n)$ implies $P(n+1)$.
Suppose that $P(n)$ is true, where $n \geq 0$.  Then we have:

\beqn
1^2 + 2^2 + 3^2 + \ldots + n^2 + (n+1)^2
    & = & \frac{n(2n+1)(n+1)}{6} + (n+1)^2 \\
    & = & \frac{2n^3 + 3 n^2 + n}{6} + \frac{6n^2 + 12n + 6}{6} \\
    & = & \frac{2n^3 + 9 n^2 + 13 n + 6}{6} \\
    & = & \frac{(n+1)(2(n+1)+1)(n+2)}{6}
\eeqn

{\em When your proof contains a sequence of equations, it is a good
idea to explain each step.  Otherwise, the reader is left with this
task, which can be much harder than the writer realizes.  (Probably
you have a story or two...)  Even some equation sequences in Rosen are
pretty cryptic because he doesn't always do this!  (e.g., what is he
*doing* with the summations in the proof of $\ex{XY} = \ex{X} \cdot
\ex{Y}$?)  In the last step, the factoring would be pretty hard to
come up with, but is easy for a reader to verify.  In this case, we
can readily guess the factorization, because we know what the answer
*should* be!}

The first step uses the induction hypothesis, $P(n)$.  In the second
step, we expand products.  Then we combine terms and refactor.  This
shows that $P(n+1)$ holds.  Therefore, $P(n)$ holds for all $n \geq
0$ by induction.
\end{proof}

\subsection*{A Note on Indexing}

Now might be a good time to point out that sometimes we want to prove
a result for all numbers $n \geq k$ where $k$ is not zero.  For
example:

\begin{claim}
For all $n \geq 12$, I can form $n$ cents of postage using only 3 cent
and 7 cent stamps.
\end{claim}

Strictly speaking, to apply the induction axiom, we should write a
proposition like this: Let $P(n)$ be the proposition that I can form
$n + 12$ cents of postage.  Now $P(0)$ is the base case, as required
in the induction axiom.

But it is simpler to let $P(n)$ be the proposition that I can form $n$
cents of postage and treat $P(12)$ as the base case.  (Then we must
show that for all $n \geq 12$, $P(n)$ implies $P(n+1)$.)

This amounts to the same thing; we could always translate an argument
that starts with $P(12)$ to an argument that starts with $P(0)$ by
replacing each $n$ in the original argument with an $n + 12$ in the
new argument.  So, knowing that we can do it, why bother?  Feel free
to use whatever number you like as your base case.  We know what you
mean.

To clarify this point, I suggest you write the old and new definitions
of $P(n)$ one right above the other so they can see the difference:
$n$ vs. $n + 12$:

\begin{tabular}{ll}
$P(n) = $ ``I can form $n + 12$ cents of postage\ldots & (base case $P(0)$) \\
$P(n) = $ ``I can form $n$ cents of postage\ldots & (base case $P(12)$)
\end{tabular}

\section{Fallacy:  All Horses Are the Same Color}

This proof (attached) illustrates how easily carelessness can conceal
errors in induction proofs.  This proof is attached on a separate
page.

This proof and the next one are much less explicit than students
should be, e.g. the predicate $P(n)$ is not defined very explicitly.
This is because we're showing {\em bogus} proofs!  The previous
example illustrated a {\em good} proof!

The problem is that $P(1)$ does not imply $P(2)$.  The $\ldots$
notation makes it look like $h_1, h_2, \ldots, h_{n}$ and $h_2,
\ldots, h_{n+1}$ contain some horses in common, but they don't when $n
= 1$.

\section{Fallacy: Wonders of the Internet}

Find the fallacy in the attached Wonders of the Internet proof.

The problem is that the induction hypothesis (not stated explicitly!)
is an implication, a statement of the form ``$p \rightarrow q$''.  In
particular, $P(n)$ is the predicate ``IF each of $n$ computers is
connected to another one of those $n$ computers, THEN they are all in
a single network.''

The error in the proof is that we assume $q$, when we should assume $p
\rightarrow q$.  That is, we assume that every set of $n$ computers
form a single network.  We dropped the condition!  To see why this is
critical, consider this elaboration of the last figure in the proof:

\bigskip
\centerline{\resizebox{!}{2.5in}{\includegraphics{tut6-netn2.eps}}}
\bigskip

Here we have $n+1$ computers, each connected to one of the other $n+1$
computers.  However, when we consider just the first $n$ computers---
as in the proof--- the condition that each is connected to one of the
other $n$ computers does not hold!  So the first $n$ computers need
not form a connected network.  In fact, like so many claims about the
internet, this one is false!

It might be worth pointing out that the pictures are misleading.
Always be wary of pictures in proofs!

\section{Strengthen the Hypothesis:  Life On Xoros 19}

See the attached problem about reproduction on Xoros 19.  This should
be a group effort.  Much of the challenge in this problem is in
digesting a complex set of rules down to a provable induction
hypothesis.  Don't give this part away!

A key point for students is that {\em proving a stronger induction
hypothesis is often easier}.  In general, one statement is {\em
stronger} than another if the first implies the second.  For example,
the hypothesis is that you live in Cambridge is stronger than the
hypothesis that you live in Massachusetts.

Again, I suggest that you (or, better, the students) write out the
{\em entire proof on the board}, and discuss the structure of an
induction proof, issues of clarity, etc.

\begin{proof}
We shall prove that there are always at least as many B-lings as
A-lings.  This implies the claim.

The proof is by induction on the generation number.  (We number
generations starting with zero.)  Let $P(n)$ be the proposition that
there are at least as many B-lings as A-lings in generation $n$.  In
the base case, $P(0)$ is true because there are 800 B-lings and only
200 A-lings initially.

Now, we assume $P(n)$ in order to prove $P(n+1)$.  For generation $n$,
let $a$ be the number of A-lings, and let $b$ be the number of
B-lings.  By our induction hypothesis, $a \leq b$.  Therefore, there
are no A-A pairs formed, there are $a$ A-B pairs formed, and there are
$\lfloor \frac{b - a}{2} \rfloor$ $B-B$ pairs formed.  As a result,
the number of A-lings in generation $n+1$ is $a + \lfloor \frac{b -
a}{2} \rfloor$, and the number of B-lings is $a + 2 \lfloor \frac{b -
a}{2} \rfloor$.  Therefore, there are at least as many B-lings as
A-lings in generation $n+1$.  Thus, for all $n \geq 0$, $P(n)$ implies
$P(n+1)$, and the claim is proved by induction.
\end{proof}

\section*{Miniquiz 2}

If you have extra time, see if you've pounded anything into their
heads!  Have them write the clearest induction proof they can of the
following claim:

\begin{claim}
The following equation holds for every integer $n \geq 2$:

\beqn
\prod_{i=2}^n \left(1 - \frac{1}{i}\right)
    & = & \frac{1}{n}
\eeqn
\end{claim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setcounter{section}{0}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{All Horses Are the Same Color}

\begin{claim}
All the horses in the world are the same color.
\end{claim}

\begin{proof}
We will prove that in every finite, nonempty set of horses, all are
the same color.  Since the set of all the horses in the world is
finite and nonempty, the claim follows.

The proof is by induction.  The induction hypothesis that in every set
of $n$ horses, all are the same color.  For the base case, note that
in every set containing a single horse, all are the same color
trivially.  Now assume that the induction hypothesis holds for every
set of $n \geq 1$ horses in order to prove that it holds for every set
of $n+1$ horses.  Consider an arbitrary set of $n+1$ horses, $h_1,
h_2, \ldots, h_{n+1}$.  By induction, $h_1, h_2, \ldots, h_{n}$ are
all the same color.  Similarly, $h_2, \ldots, h_{n+1}$ are all the
same color.  Therefore, horse $h_1$ is the same color as horses $h_2,
\ldots, h_n$, which are the same color as horse $h_{n+1}$.  It follows
that in every set of $n+1$ horses, all are the same color.  Therefore,
by induction, in every finite, nonempty set of horses, all are the
same color.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{The Wonders of the Internet}

\begin{theorem}
If every computer is connected to at least one other computer, then
all computers are connected in a single network.
\end{theorem}

\begin{proof}
We shall use induction to prove the claim for every set of $n \geq 2$
computers.  For the base case ($n = 2$), there is clearly only one
possible configuration of computers, and indeed all are connected in a
single network:

\bigskip
\centerline{\resizebox{2in}{!}{\includegraphics{tut6-net2.eps}}}
\bigskip

Now suppose that the induction hypothesis holds for a set of $n$
computers.  We shall show that it also holds for a set of $n+1$
computers.  The situation is illustrated in the figure below:

\bigskip
\centerline{\resizebox{!}{2.5in}{\includegraphics{tut6-netn.eps}}}
\bigskip

\noindent By the induction hypothesis, the first $n$ computers are
connected in a single network.  The $(n+1)$-st computer must be
connected to one of these and is therefore also a part of this single
network.  Therefore, the claim follows by induction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Life On Xoros 19}

There are two types of creature on planet Xoros 19, A-lings
and B-lings. Furthermore, every creature belongs to a particular
generation.  The creatures in each generation reproduce according to
certain rules and then die off.  The subsequent generation consists
entirely of their offspring.

The creatures of Xoros 19 pair with a mate in order to reproduce.
First, as many A-B pairs as possible are formed.  The remaining
creatures form A-A pairs or B-B pairs, depending on whether there is
an excess of A-lings or of B-lings.  If there are an odd number of
creatures, then one in the majority species dies without reproducing.
The number and type of offspring is determined by the types of the
parents

\begin{itemize}
\item If both parents are A-lings, then they have three A-ling
offspring.

\item If both parents are B-lings, then they have two B-ling offspring
and one A-ling offspring.

\item If there is one parent of each type, then they have one
offspring of each type.
\end{itemize}

There are 200 A-lings and 800 B-lings in the first generation.  Use
induction to prove that the number of A-lings will always be {\em at
most twice} the number of B-lings.

\end{document}
