\problemdata
{S00 ps1}
{close form formula}
{logic}

\begin{problem}
Find a closed-form formula for 
\[
\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}
\]
by examining the values of this expression for small values of $n$.
Use mathematical induction to prove your formula holds for all natural
numbers.

\solution{
Let $s(n) = \frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}$. 
For small values of $n$, we have:
\begin{center}
\begin{tabular}{l|c}
$n$ & $s(n)$ \\
\hline
$0$ & $0$ \\
$1$ & $1/2$ \\
$2$ & $2/3$ \\
$3$ & $3/4$ 
\end{tabular}
\end{center}
So we guess that $s(n) = n/(n+1)$. 

Let $P(n)$ be the proposition that $s(n) =  n/(n+1)$.
We want to prove, by induction, $\forall n \in \mathbb{N}\;P(n)$.

\begin{enumerate}

\item (Base case: Prove $P(0)$.)  The base case is established by the table
above. 

\item (Inductive case: Prove $\forall n \in \mathbb{N}\;(P(n) \implies
P(n+1))$.) Substituting our definition of $P(n)$, we must show 
$s(n) = \frac{n}{n+1} \implies s(n+1) = \frac{n+1}{n+2}$ 
for all natural numbers $n$.  
\begin{tabbing}
XXXXXXti\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
 1. Fix $n \geq 0$.\\
 2. Assume $s(n)= \frac{n}{n+1}$\\ 
 3. $s(n+1)$ 
\>  $ = s(n) +  \frac{1}{(n+1)(n+2)}$
  \>   (definition of $s(n)$) \\[.5ex] 

\>  $=\frac{n}{n+1}+\frac{1}{(n+1)(n+2)}$
  \>  (inductive hypothesis) \\[.5ex]  
\>  $=\frac{(n+1)^2}{(n+1)(n +2)}$            
  \>  (algebra)\\[.5ex]   
\>  $=\frac{(n+1)}{(n+2)}$
  \>  (division, note: $n+1 \not = 0$)\\ 
 4. QED 
\>\>  (implication)
\end{tabbing}

\item QED (induction)
\end{enumerate}
}
\end{problem}