\problemdata     
{S01-PS6-1}           
{summations}              
{S01-PS6} 		
{S01 Karger}




\begin{problem}


In this problem we will estimate the \emph{average} number of
divisors a ``typical'' number has.  More precisely, let $a(n)$ denote
the average number of divisors of the numbers from $1$ to $n$.
\begin{problemparts}
\ppart Let $f_{ij}=1$ if $i \mid j$, and 0 otherwise.  Explain why
\begin{displaymath}
  a(n) = \frac{1}{n} \sum_{j=1}^n \sum_{i=1}^n f_{ij}
\end{displaymath}

\solution{
For a fixed~$j$, $\sum_{i=1}^n f_{ij}$ is
  the number of divisors of~$j$.}

\ppart For a given~$i$, what is the value of $\sum_{j=1}^n f_{ij}$?

\solution{ $\lfloor n/i \rfloor$.}

\ppart Give a closed form estimate of $a(n)$ that is accurate to
within plus or minus 2 for any~$n$.

\solution{
 By the solution above,
  \begin{displaymath}
    a(n) =
    \frac{1}{n} \sum_{j=1}^n \sum_{i=1}^n f_{ij} =
    \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n f_{ij} =
    \sum_{i=1}^n \frac{\lfloor n/i \rfloor}{n}\,.
  \end{displaymath}
  Since
  \begin{displaymath}
    \frac{n-i}{i} \leq \biggl\lfloor\frac{n}{i}\biggr\rfloor \leq 
    \frac{n}{i}\,
  \end{displaymath}
  we obtain the bound
  \begin{displaymath}
    \sum_{i=1}^n \biggl(\frac{1}{i} - \frac{1}{n}\biggr) \leq
    a(n) \leq
    \sum_{i=1}^n \frac{1}{i}\,,
  \end{displaymath}
  or, equivalently, $H_n - 1 \leq a(n) \leq H_n$, where $H(n)$~denotes
  the $n$th harmonic number. From the lecture notes, we now the bound
  $\ln(n+1) \leq H_n \leq \ln n + 1$. Combining these bounds, we obtain
  \begin{displaymath}
    \ln(n+1) - 1 \leq a(n) \leq \ln n + 1.
  \end{displaymath}
}

\end{problemparts}

\end{problem}