\input{latex-macros/handout-preamble.tex}
\inhandout{
\decideaboutsolutions
\usesimpleproblems
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem starts here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
\PTAGfilename{CP0301_false_geometric_series_proof}
\PTAGhistory{S09_cp4t}
\PTAGkeywords{induction}
%
  \href{http://theory.csail.mit.edu/classes/6.042/spring09/ln4.pdf}{Week 4
    Notes} contain a proof by induction that:
%
\[
1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}
\]
%
But now we're going to prove a \textit{contradictory} theorem!

\begin{falsethm*}
For all $n \geq 0$,
%
\[
2 + 3 + 4 + \cdots + n = \frac{n(n+1)}{2}
\]
\end{falsethm*}

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that $2 + 3 + 4 +
\cdots + 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 + \cdots + n = n(n+1)/2$.  Then we can reason as
follows:
%
\begin{align*}
2 + 3 + 4 + \cdots + n + (n+1)
    & = \bigl[2 + 3 + 4 + \cdots + 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
``$\cdots$'' 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 + \cdots + n + (n+1)
     = \bigl[2 + 3 + 4 + \cdots + n\bigr] + (n+1)
\]
%
This seems completely innocuous; after all, we've only grouped terms!
However, the left side contains \textit{no terms} when $n = 0$.  The
``$\cdots$'' is completely 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 + \cdots + n + (n+1)}_{= 0}
     = \bigl[\underbrace{2 + 3 + 4 + \cdots + 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)$.}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem ends here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{latex-macros/handout-postamble.tex}
