\problemdata     
{induction-1}           
{induction, proofs}              
{}              
{S01-PS2} 		
{S01 Karger}        	


\begin{problem} 
Use induction to prove that the following equation holds for all
$n \geq 2$.

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

\solution{


\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above equation holds.  In the base case, $P(2)$ is true because
$(1 - \frac{1}{2}) = \frac{1}{2}$.  In the inductive step, for $n \geq
2$ assume $P(n)$ to prove $P(n+1)$ as follows.

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

The first step uses the induction hypothesis, and the second and third
steps are simplifications.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
\end{proof} 
}

\end{problem}