\documentstyle[amstex]{article}
\input{macros-course}

\begin{document}

By fixing $n$ and experimenting with a few values for $m$ a pattern arises.  we guess the identity
$$
\sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} = 1+\frac{m}{n-m+1}
$$

which we will verify by induction.

The base case for $m=0$ is trivial.

Assume that the above expression holds for some $m$.  We will show it for $m+1$.

\begin{eqnarray*}
\sum_{k=0}^{m+1} \frac{{m+1 \choose k}}{{n \choose k}} \\
& = & \frac{{m+1 \choose 0}}{{n \choose 0}} + 
\sum_{k=1}^{m+1} \frac{{m+1 \choose k}}{{n \choose k}} \\
& = & 1+ \sum_{k=1}^{m+1} \frac{\frac{m+1}{k}}{\frac{n}{k}}
\frac{{m \choose k-1}}{{n-1 \choose k-1}} \\
& = & 1 + \frac{m+1}{n} \sum_{k=0}^{m} \frac{{m \choose k}}{{n-1 \choose k}}\\
& = & 1 + \frac{m+1}{n} \left(1+\frac{m}{n-m} \right)\\
& = & 1+\frac{m+1}{n-m}\\ 
\end{eqnarray*}

which is the desired expression.

\end{document}
