\begin{problem}
The average running time of a well-known randomized procedure is:

\[
1 + \frac{n}{n-1} + \frac{n}{n-2} + \frac{n}{n-3} + \ldots + \frac{n}{2} + n
& \sim & \fbox{\hspace{1in}}
\]

Fill in the box with a suitable {\em closed-form} expression.
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let $k$ be an integer, and let $n$ be a positive integer.  Prove:

If there exists an integer $k^{-1}$ such that

\begin{eqnarray*}
k \cdot k^{-1} \equiv 1 \pmod{n}
\end{eqnarray*}

then $k$ and $n$ are relatively prime.

Warning: This proof requires only a few steps, so each one is worth a
lot of points!  Consider using the back of this page for scratchwork
and writing a final draft below.

\solution{
If the congruence holds, then:

\[
n \mid (k \cdot k^{-1} - 1)
\]

by the definition of congruence.  By the definition of $\mid$, there
exists an integer $c$ such that:

\[
c n = k \cdot k^{-1} - 1
\]

Rearranging terms gives:

\[
k \cdot k^{-1} - c n & = & 1
\]

The greatest common divisor of $k$ and $n$ is equal to the smallest
positive integer expressible as a linear combination of $k$ and $n$.
Since we've expressed 1 as a linear combination of $k$ and $n$, we
know that $\gcd(k, n) \leq 1$.  Since $\gcd$ is positive by
definition, it must be that $\gcd(k, n) = 1$.  This means that $k$ and
$n$ are relatively prime.}

\end{problem}