        \problemdata       % Takes 5 *mandatory* arguments
        {sums-induction}             % latex-friendly label for the prob.
        {induction}  % The topic(s) of the problem content.
        {Rosen, \S 3.2}               % Source (if known)
        {S02 ps2-1} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).



\begin{problem}
\begin{problemparts}
\problempart Rosen, \S 3.2, Exercise 8.
Prove by induction that
\begin{equation}\label{sum3}
1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2,
\end{equation}
for all $n \in \naturals$.

\solution{

\begin{proof} (by Induction).  The induction hypothesis is $P(n) \eqdef 
\text{ equation~(\ref{sum3})}$.

\textbf{Base Case}: ($n = 1$).  The LHS of~(\ref{sum3}) in this case is
$1^3$ and the RHS is $((1 \cdot 2)/2)^2$.  Since both these quantities
equal 1, equation~(\ref{sum3}) holds, and $P(1)$ is proved.  (Remark:
using the convention that an \emph{empty sum} equals 0, the base case
$n=0$ would be even easier to prove.)

\textbf{Inductive Step}: Let $n$ be any natural number, $\geq 1$, and
assume $P(n)$ in order to prove $P(n+1)$.

So by assumption, we have
\[
1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2.
\]
Adding $(n+1)^3$ to both sides of this equation, gives
\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3 
&= & \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\
&= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\
&= &\frac{(n^2+4n+4)(n+1)^2}{4}\\
&= &\left(\frac{(n+1)((n+1)+1)}{2}\right)^2.
\end{eqnarray*}
So we have proved $P(n+1)$.
\end{proof}

{\bf Common errors }

A common error is to assume the hypothesis and then to prove it by
reducing both sides of the equation to something that is obviously equal.
This is not a good proof technique.

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3  &=& \left(\frac{(n+1)(n+2)}{2}\right)^2 \\
\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3  &=& \left(\frac{(n+1)(n+2)}{2}\right)
^2 \\      
\frac{n^2(n^2+2n+1)}{4} + n^3 + 3n^2+ 3n +1 &=& \frac{(n^2+3n+2)^2}{4} \\
\frac{(n^4 +2n^3 +n^2) + (4n^3 + 12n^2 + 12n + 4)}{4} &=& 
   \frac { n^4 +3n^3 + 2n^2 + 3n^3 +9n^2 +6n +2n^2 + 6n +4}{4} \\
\frac{n^4 + 6n^3 +13n^2 +12n + 4}{4} &=& 
   \frac{n^4 + 6n^3 +13n^2 +12n + 4}{4} 
\end {eqnarray*}

A technique which is similar but which is not at all correct is to start
with the equation you wanted to prove and then perform the same operations
on both sides of the equation until they're equal.  A simple example is:
\begin{eqnarray*}
n^2+3n+1 &= &n^2+3n+1\\
3n+1 &= & 3n+1\\
1 &= & 1\\
\end{eqnarray*}
This is OK for a quick check, but does not quite work as a proof, since it
is possible to get equality at the end even if the starting sides of the
equation were not equal. For example
\begin{eqnarray*}
n^2+3n+1 &= &2n^2+5n+8\\
0 \cdot (n^2+3n+1) &= & 0 \cdot (2n^2+5n+8)\\
0 & = & 0
\end{eqnarray*}

Remember that in an ideal direct proof, each step should follow from
the previous one, until the final step which is what we want to prove.
}

\problempart Rosen, \S 3.2, Exercise 18.  
\begin{equation}\label{1n2}
\forall\ n>1,\quad 1+\frac{1}{4}+\cdots+\frac{1}{n^2}  <  2-\frac{1}{n}.
\end{equation}

\solution{
\begin{proof}
(by Induction).  The induction hypothesis is $P(n) \eqdef\text{ the
inequality~(\ref{1n2})}$.

\textbf{Base Case}: ($n = 2$).  The LHS of~(\ref{1n2}) in this case is
$1 + 1/4$ and the RHS is $2 - 1/2$.  Since LHS $= 5/4 < 6/4 = 3/2 =$ RHS, 
inequality~(\ref{1n2}) holds, and $P(2)$ is proved.

\textbf{Inductive Step}: Let $n$ be any natural number greater than $1$, and
assume $P(n)$ in order to prove $P(n+1)$.

So by assumption, we have
\[
1+\frac{1}{4}+\cdots+\frac{1}{n^2}  <  2-\frac{1}{n}.
\]
Adding $1/(n+1)^2$ to both sides of this inequality yields
\begin{eqnarray*}
1+\frac{1}{4}+\cdots+\frac{1}{n^2}+\frac{1}{(n+1)^2}& < & 2-\frac{1}{n}
             +\frac{1}{(n+1)^2}\\
& = & 2 - \left(\frac{1}{n} - \frac{1}{(n+1)^2}\right)\\
& = & 2 - \left(\frac{n^2 + 2n + 1-n}{n(n+1)^2}\right)\\
& = & 2 - \frac{n^2 + n}{n(n+1)^2}-\frac{1}{n(n+1)^2}\\
& = & 2 - \frac{1}{n+1} - \frac{1}{n(n+1)^2}\\
& < & 2 - \frac{1}{n+1}.
\end{eqnarray*}
So we have proved $P(n+1)$.
\end{proof}}
\end{problemparts}
\end{problem}
