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

\showsolutions
%\hidesolutions

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

\begin{document}

\recitation{2}{September 15, 2004}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\insolutions{

%[\stamp]

\section{Induction}

Recall the principle of 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}$.
}

As an example, let's try to find a simple expression equal to the
following sum and then use induction to prove our guess correct.
%
\[
1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \ldots + n \cdot (n+1)
\]

To help find an equivalent expression, we could try evaluating the sum
for some small $n$ and (with the help of a computer) some larger $n$:
%
\[
\begin{array}{c|c|c}
n & \text{sum} & 3 \times \text{sum} \\ \hline
0 & 0 & 0 \\
1 & 2 & 6 \\
2 & 8 & 24 \\
3 & 20 & 60 \\
4 & 40 & 120 \\
5 & 70 & 210 \\
\ldots & \ldots & \ldots \\
10 & 440 & 1320 \\
100 & 343400 \approx 10^6 / 3 & 1030200\\
1000 & 334334000 \approx 10^9 / 3 & 1003002000
\end{array}
\]
%
Unfortunately, the small sums are not too illuminating.  However, the
larger sums suggest we consider an expression similar to $n^3 / 3$.
So in the third column we've multiplied each sum by 3 in hopes of
spotting a sequence generated by an expression something like $n^3$.
From the first few terms, you might guess that these new numbers are
equal to $n (n+1) (n+2)$.  Alternatively, you might notice that the
last couple numbers are equal to $n^3 + 3 n^2 + 2 n$, which factors to
$n (n + 1) (n + 2)$.  So now we have a conjecture:

\begin{conjecture*}
For all positive integers, $n$:
%
\[
1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \ldots + n (n+1)
    = \frac{n (n+1) (n+2)}{3}
\]
\end{conjecture*}

Let's use induction to verify this conjecture.  Remember that an
induction proof has five parts, though the last one is often omitted:

\begin{enumerate}
\item Say that the proof is by induction.
\item Define the induction hypothesis, a predicate $P$ defined on the
natural numbers.
\item Handle the base case: prove that $P(0)$ is true.
\item Handle the inductive step: prove that $P(n)$ implies $P(n+1)$
for all integers $n \ge 0$.
\item Conclude that $P(n)$ is true for all $n \in \mathbb{N}$ by the
principle of induction.
\end{enumerate}

We noted in Lecture that while the base case is usually $n=0$, it could be
any nonnegative integer, $k$, in which case the conclusion would simply be
that $P(n)$ holds for all $n \ge k$.

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that:
%
\begin{equation}\label{1223}
1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \ldots + n (n+1) = \frac{n (n+1) (n+2)}{3}
\end{equation}

\noindent \textit{Base case $n=1$:} $P(1)$ is true, because the lefthand
side of~\eqref{1223} is $1 \cdot 2 = 2$, and the righthand side is $(1\cdot
2 \cdot 3)/ 3 = 2$.

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n+1)$ for all $n \ge 1$.  So assume that $P(n)$ is true,
where $n$ denotes a positive integer.  Then we can reason as
follows:
%
\begin{align*}
\lefteqn{1 \cdot 2 + 2 \cdot 3 + \dots + (n+1) (n+2)}\\
    & = [1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1)] + (n+1) (n+2)\\
    & = \frac{n(n+1)(n+2)}{3} + (n+1) (n+2) & \text{by ind.\ hypothesis~\eqref{1223}}\\
    & = \frac{n(n+1)(n+2) + 3(n+1)(n+2)}{3} \\
    & = \frac{(n+1)(n+2)(n+3)}{3}
\end{align*}
%
\iffalse The first step uses the assumption $P(n)$, and the remaining steps are
simplifications.\fi
%
This shows that $P(n+1)$ is true, and so $P(n)$ implies $P(n+1)$ for all
$n \ge 1$.

By the induction principle, $P(n)$ is true for all $n \ge 1$,
which proves the claim.
\end{proof}

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

\newpage
}

\section{Problem:  A Geometric Sum}

Perhaps you encountered this classic formula in school:
%
\[
1 + r + r^2 + r^3 + \ldots + r^n = \frac{1 - r^{n+1}}{1 - r}
\]
%
Use induction to prove that it is correct for all real values $r \neq 1$.

\bigskip

\noindent\textit{Prepare a complete, careful solution.  You'll be
passing your proof to another group for ``constructive criticism''!'}

\solution{
\begin{proof}
We use induction.  Let $P(n)$ be the proposition that the following
equation holds for all $r \neq 1$:
%
\[
1 + r + r^2 + r^3 + \ldots + r^n = \frac{1 - r^{n+1}}{1 - r}
\]
%
\noindent \textit{Base case:} $P(0)$ is true, because both sides of
the equation are equal to 1.

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n + 1)$ for all $n \in \mathbb{N}$.  So assume that $P(n)$ is true,
where $n$ denotes an arbitrary natural number.  We can reason as
follows:
%
\begin{align*}
1 + r + r^2 + r^3 + \ldots + r^n + r^{n+1}
  & = \frac{1 - r^{n+1}}{1 - r} + r^{n+1} \\
  & = \frac{1 - r^{n+1} + (1 - r) \cdot r^{n+1}}{1 - r} \\
  & = \frac{1 - r^{n+2}}{1 - r}
\end{align*}
%
The first equation follows from the assumption $P(n)$, and the
remaining steps are simplifications.  This proves that $P(n+1)$ is
also true.  Therefore, $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}$.
\end{proof}

\noindent \textbf{Note:} You may have encountered a different proof of
this formula.  We'll write down a sequence of equations and then
explain the reasoning.
%
\begin{align*}
S & = 1 + r + r^2 + r^3 + \ldots + r^n \\
r S & = r + r^2 + r^3 + \ldots + r^{n+1} \\
S - r S & = 1 - r^{n+1} \\
S & = \frac{1 - r^{n+1}}{1 - r}
\end{align*}
%
We define $S$ on the first line, multiply by $r$ to get the second
equation, subtract the second equation from the first to get the
third, and then solve for $S$.  This gives the formula above!

This argument is great!  It is a derivation of the formula rather than
just a verification.  But, at some level, we've only hidden the use of
induction, since the operations we're doing on $n$-term sums are
justified using--- you guessed it--- induction.}

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

\newpage

\section{Problem: A False Proof}

In lecture, we proved that:
%
\[
1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}
\]
%
But now we're going to prove a \textit{contradictory} theorem!

\begin{false-theorem}
For all $n \geq 0$,
%
\[
2 + 3 + 4 + \ldots + n = \frac{n(n+1)}{2}
\]
\end{false-theorem}

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that $2 + 3 + 4 +
\ldots + n = n(n+1)/2$.

\noindent \textit{Base case:} $P(0)$ is true, since both sides of the
equation are equal to zero.  (Recall that a sum with no terms is
zero.)

\noindent \textit{Inductive step:} Now we must show that $P(n)$
implies $P(n+1)$ for all $n \geq 0$.  So suppose that $P(n)$ is true;
that is, $2 + 3 + 4 + \ldots + n = n(n+1)/2$.  Then we can reason as
follows:
%
\begin{align*}
2 + 3 + 4 + \ldots + n + (n+1)
    & = \bigl[2 + 3 + 4 + \ldots + n\bigr] + (n+1) \\
    & = \frac{n(n+1)}{2} + (n+1) \\
    & = \frac{(n+1)(n+2)}{2}
\end{align*}
%
Above, we group some terms, use the assumption $P(n)$, and then
simplify.  This shows that $P(n)$ implies $P(n+1)$.  By the principle
of induction, $P(n)$ is true for all $n \in \mathbb{N}$.
\end{proof}

Where exactly is the error in this proof?

\noindent \textit{Discuss your explanation with your recitation
instructor.  We don't want you to conclude that there is something
wrong with induction proofs in general!}

\solution{The short answer is that we failed to prove $P(0) \implies
P(1)$, just as in the colored horses problem in lecture.  In fact,
once again, the error is rooted in the misleading nature of the
``$\ldots$'' notation.

More precisely, in the inductive step we are required to prove that
$P(n)$ implies $P(n+1)$ for all $n \geq 0$.  However, the argument
given above breaks down when $n = 0$.  Let's look more closely at the
first equation in the indutive step to see why:
%
\[
2 + 3 + 4 + \ldots + n + (n+1)
     = \bigl[2 + 3 + 4 + \ldots + n\bigr] + (n+1)
\]
%
This seems completely innucuous; after all, we've only grouped terms!
However, the left side contains \textit{no terms} when $n = 0$.  The
``$\ldots$'' is compeletely misleading in this case; 2, 3, 4, and
$n+1$ are actually \textit{not} in the sum.  This misimpression
becomes an error when we ``pull out'' the $(n+1)$ term on the right
side, disregarding the fact that no such term actually existed on the
left.  Thus, for $n = 0$, the equation we've just written down says:
%
\[
\underbrace{2 + 3 + 4 + \ldots + n + (n+1)}_{= 0}
     = \bigl[\underbrace{2 + 3 + 4 + \ldots + n}_{= 0}\bigr] +
       \underbrace{(n+1)}_{= 1}
\]
%
The assertion $0 = 0 + 1$ is false, and so we have not shown that
$P(0)$ implies $P(1)$.  There is no way to fix this problem and
correctly prove that $P(0)$ implies $P(1)$, because actually $P(0)$ is
true and $P(1)$ is false.

Thus, we've only established $P(0)$, $P(1) \implies P(2)$, $P(2)
\implies P(3)$, and so forth.  The induction argument falls apart
because of the missing link $P(0) \not\implies P(1)$.}

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

\newpage

\section{Problem: The Volcanic Island}

There is a village on a volcanic island with $b \geq 1$ blue-eyed
people and $g \geq 0$ green-eyed people.  There are no mirrors and no
one ever discusses eye color.  Therefore, everyone knows the colors of
everyone elses' eyes, but not their own.  Good thing, because an
islander who learns that he or she has blue eyes must leap into the
volcano at the end of the same day!

The villagers live in happy ignorance for years.  But one day an
explorer arrives and loudly proclaims, ``I see that at least one
person here has blue eyes.''  Assuming that all the villagers are
master logicians, what happens?

\solution[\vspace{1in}]{All the blue-eyed villagers jump into the
volcano at the end of the $b$th day.}

\noindent Use induction to prove that your conclusion is correct.  We
suggest a hypothesis $P(n)$ that asserts all of the following are true
on day $n$:

\begin{enumerate}
\item If $b > n$, then \underline{\hspace{5in}}.
\item If $b = n$, then \underline{\hspace{5in}}.
\item If $b < n$, then \underline{\hspace{5in}}.
\end{enumerate}

(We leave the task of filling in the blanks to you.)

\solution{Note that a green-eyed villager shouldn't ever conclude that she
has blue eyes, since she doesn't, and we're assuming the villagers always
reason correctly from what they know (and what they know from the explorer
is also true).  So no green-eyed person should ever jump into the volcano.

\begin{theorem}
All the blue-eyed people jump into the volcano on day $b$.
\end{theorem}

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that all of the
following are true on day $n$:

\begin{enumerate}
\item If $b > n$, then all blue-eyed people survive the day.
\item If $b = n$, then all blue-eyed people jump into the volcano.
\item If $b < n$, then all blue-eyed people are already dead.
\end{enumerate}

\noindent \textit{Base case:} We must verify that the three parts of
$P(n)$ hold on day $n = 1$.

\begin{enumerate}

\item Suppose $b > 1$.  Consider events on day 1 from the perspective
of a blue-eyed villager.  The explorer says that someone has blue
eyes, and she can indeed see at least one other person with blue eyes.
Therefore, the facts available to her are consistent with her having
either blue or green eyes.  So she survives the day.

\item Suppose $b = 1$.  The single blue-eyed villager sees no one else
with blue eyes, concludes that he must have blue eyes, and jumps into the
volcano.  No one else jumps in because everyone else does see the
blue-eyed villager and they have no reason at this point to think they too
are blue-eyed.

\item This statement is vacuously true, because the if-part ($b < 1$)
is false; the problem statement says that $b \geq 1$.

\end{enumerate}

\noindent Therefore, $P(1)$ is true.

\noindent \textit{Inductive step:} Now suppose that $P(n)$ is true
where $n \geq 0$.  We must verify the three parts of $P(n+1)$.

\begin{enumerate}

\item Suppose $b > n + 1$.  Then $b > n$ so all the blue-eyed people
survived the preceding day by part 1.\ of $P(n)$.  Furthermore, each
blue-eyed villager can see at least $n + 1 > n$ other blue-eyed
people, so the observation that everyone survives is consistent with
she herself having either blue or green eyes by $P(n)$ as well.
Thus, each blue-eyed villager survives the day.

\item Suppose $b = n + 1$.  Then $b > n$, so all the blue-eyed people
survived the preceding day by part 1.\ of $P(n)$.  Thus, on day $n + 1$
each blue-eyed villager knows $b > n$ 
%\textbf{[ARM: isn't this using strong induction?]}
, but sees only $n$ other people with blue eyes.  Thus,
each blue-eyed villager realizes that she has blue eyes and jumps into the
volcano.

\item Suppose $b < n + 1$.  Then either $b = n$ (in which case all
blue-eyed people jumped into the volcano on day $n$ by part 2.\ of
$P(n)$) or else $b < n$ (in which case all blue-eyed-people were
already dead on day $n$ by part 3.\ of $P(n)$).  In either case, all the
blue-eyed people are already toast.

\end{enumerate}

\noindent Therefore $P(n)$ implies $P(n+1)$ for all $n \geq 0$.

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

\iffalse
\noindent If there are at least two blue-eyed people, then the
explorer didn't tell the villagers anything that they didn't already
know, so why was his arrival significant?

\solution{The explorer changes what the villagers know about what
their compatriots are thinking.  For example, suppose that there are
only two villagers, $X$ and $Y$, both with blue eyes.  Before the
explorer arrives, both $X$ and $Y$ know that there is a villager with
blue eyes.  But neither knows that the \textit{other} realizes this.
In contrast, after the explorer makes his statement, each villager
knows that the other knows that someone has blue eyes.}
\fi

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

\end{document}

