\documentclass[12pt]{article}
\pagestyle{empty}
\parindent=0in
\parskip=10pt

\newtheorem{claim}{Claim}
\newenvironment{proof}{{\bf Proof:}}{\hfill \rule{5pt}{5pt}}
\newenvironment{altproof}{{\bf Alternate Proof:}}{\hfill \rule{5pt}{5pt}}

\begin{document}
{\large
Math 251 \hfill Homework Solution \hfill 2 February 2004} \\*[-5pt]
\rule{\textwidth}{1pt}

\begin{claim}
For any real number $r \neq 1$ and every integer $n \geq 0$, 
\begin{eqnarray}
\sum_{k=0}^n r^k & = & {1-r^{n+1} \over 1-r}
\label{assertion}
\end{eqnarray}
\end{claim}

\begin{proof}
For each non-negative integer $n$, let
\begin{eqnarray*}
T_n & = & 1 + r + r^2 + \cdots + r^n
\end{eqnarray*}
Then we have
\begin{eqnarray*}
(1-r)T_n & = & (1-r)(1 + r + r^2 + \cdots + r^n) \\
         & = & 
\begin{array}[t]{rcrcrcccrcr}
1 & + & r & + & r^2 & + & \cdots & + & r^n &   &   \\
  & - & r & - & r^2 & - & \cdots & - & r^n & - & r^{n+1}
\end{array} \\
         & = & 1 - r^{n+1}
\end{eqnarray*}
so that
\begin{eqnarray}
(1-r)T_n & = & 1 - r^{n+1}
\label{multiplicativeform}
\end{eqnarray}
Now since $r \neq 1$, we can divide both sides of 
(\ref{multiplicativeform}) by $1-r$ to get
\begin{eqnarray*}
T_n & = & {1 - r^{n+1} \over 1-r}
\end{eqnarray*}
and since ${\displaystyle T_n = \sum_{k=0}^n r^k}$, we have proved
(\ref{assertion}).
\end{proof}

\begin{altproof}
We proceed by induction on $n$.

For the base case, take $n=0$.  On the left side of (\ref{assertion}),
we have ${\displaystyle \sum_{k=0}^0 r^k}$, which is just $r^0$, or
$1$ (we are assuming that $0^0 = 1$ for this problem).  On the right
side of (\ref{assertion}), we have ${\displaystyle {1-r \over 1-r}}$,
which, for $r \neq 1$, is also equal to $1$.

Thus, (\ref{assertion}) holds in the base case.

For the inductive step, we assume that (\ref{assertion}) holds for
some value of $n \geq 0$, and show that 
\begin{eqnarray}
\sum_{k=0}^{n+1} r^k & = & {1 - r^{(n+1)+1} \over 1-r}
\label{inductivestep}
\end{eqnarray}

We have
\begin{eqnarray}
\sum_{k=0}^{n+1} r^k & = & \left ( \sum_{k=0}^n r^k \right ) + r^{n+1} 
\label{newleftside} \\
& = & \left ( {1 - r^{n+1} \over 1 - r} \right ) + r^{n+1}
\label{inductiveresult}
\end{eqnarray}
by the inductive hypothesis.

Now the right side of (\ref{inductiveresult}) is just
\begin{eqnarray}
{1 - r^{n+1} \over 1-r} + r^{n+1} 
& = & {1 - r^{n+1} + (1-r)r^{n+1} \over 1 - r} \\
& = & {1 - r^{n+1} + r^{n+1} - r^{(n+1)+1} \over 1 - r} \\
& = & {1 - r^{(n+1)+1} \over 1 - r}
\label{newrightside}
\end{eqnarray}

Putting lines (\ref{newleftside}) through (\ref{newrightside})
together, we get
\begin{eqnarray*}
\sum_{k=0}^{n+1} r^k & = & {1 - r^{(n+1)+1} \over 1 - r}
\end{eqnarray*}
which is just line (\ref{inductivestep}).  Thus, by the principle of
mathematical induction, claim (\ref{assertion}) holds for all integers
$n \geq 0$.
\end{altproof}

\end{document}