\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\begin{document} 
\inclassproblems{3, Wed.}                    % !! start the paper

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

\begin{problem}
Use induction to prove that
\begin{equation}\label{P}
1^3 + 2^3 + \cdots + n^3  =  \paren{\frac{n(n+1)}{2}}^2.
\end{equation}
for all $n \geq 1$.

\iffalse
(1 + 2 + \cdots + n)^2.
\hint
\href{http://theory.csail.mit.edu/classes/6.042/fall05/ln2.pdf}
{Week 2 Notes} includes a proof that $(1 + 2 + \cdots + n)^2 =
\paren{\frac{n(n+1)}{2}}^2$.  You may assume this in your proof here.
\fi

Remember to formally 
\begin{enumerate}
\item Declare proof by induction.
\item Identify the induction hypothesis $P(n)$.
\item Establish the base case.
\item Prove that $P(n)\Rightarrow P(n+1)$.
\item Conclude that $P(n)$ holds for all $n\geq 1$.  
\end{enumerate}
as in the five part template.  

\solution{We proceed by induction.  The induction hypothesis, $P(n)$, will
be the equation~\eqref{P}.

\textbf{Base case:} First, we must show that $P(1)$ is true.  This is 
immediate, since:

\begin{eqnarray*}
1^3 & = & \left(\frac{1 (1+1)}{2}\right)^2
\end{eqnarray*}

\textbf{Inductive step:} Next, we must show that $P(n)$ implies $P(n + 1)$ for 
all $n \geq 1$.  Assuming that $P(n)$ is true, we can reason as follows:

\begin{eqnarray*}
1^3 + 2^3 + \cdots + n^3 + (n + 1)^3
    & = & \left(\frac{n(n+1)}{2}\right)^2 + (n + 1)^3 \\
    & = & \left(\frac{(n + 1)(n+2)}{2}\right)^2
\end{eqnarray*}

The first step uses the assumption $P(n)$, and the second
uses only algebra.  This shows that $P(n + 1)$ is true.  
Therefore, $P(n)$ is true for all $n \geq 1$ by induction.}

\end{problem}

\instatements{\newpage}

\begin{problem}

\bparts

\ppart Prove by induction that a $2^n \times 2^n$ courtyard with a $1
\times 1$ statue of Bill in {\em any position} can be covered with
$L$-shaped tiles.

\solution{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:} 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}

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.

This proof has two nice properties.  First, not only does the argument
guarantee that a tiling exists, but also it gives a recursive procedure
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!}

\ppart {\em (Discussion Question)} In part~(a) we saw that it can be
easier to prove a stronger theorem.  Does this surprise you?  How would
you explain this phenomenon?

\solution{It might seem that it ought to be harder to prove a more general
theorem than a less general one, but sometimes not.  For example, the more
general result might actually be easier because it involves fewer
assumptions, and this can help in avoiding the complications of unnecesary
hypotheses.

But for an induction proof in particular, using a more general induction
hypothesis means we can make a stronger \emph{assumption} in the induction
step (namely, we can assume a stronger $P(n)$), which can make it easier
to prove the conclusion of the induction step (namely, $P(n+1)$).}

\eparts

\end{problem}

\begin{problem}
Notes 2 contains 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 innucuous; after all, we've only grouped terms!
However, the left side contains \textit{no terms} when $n = 0$.  The
``$\cdots$'' 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 + \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}

\end{document}
