# Estimation of sums with number theory functions

Problem 1. Let $d(k)$ denote the number of divisors of $k\in\mathbb{N}$. Prove that: $$\sum_{k=1}^{n}d(k)=n\ln n +O(n)$$

Problem 2. Show estimation below: $$\sum_{k=1}^{n}\phi(k)=\frac{3}{\pi^2}\cdot n^2+O(n\log n)$$ where $\phi$ is Euler's totient function of course.

I just started having fun with asymptotics and can't manage with these two. They seem very interesting, because this is the first time I've seen asymptotics and number theory together (I know, I haven't seen too much of math, yet) and I'm very curious how these problems can be solved. They also made me wonder if is there any asymptotic estimation for sum with another interesting function: $\sum_{k=1}^{n}\sigma(k)$, where $\sigma(k)$ is the sum of divisors of $k$?

-
For $\sum_{1}^n d(k)$, note that $1$ is a divisor of $n$ numbers between $1$ and $n$, and $2$ is a divisor of about $\frac{n}{2}$ numbers, and $3$ is a divisor of about $\frac{n}{3}$ numbers, and so on. So our sum is about $n+\frac{n}{2}+\frac{n}{3}+\cdots+ \frac{n}{n}$. That takes care of things, since at each stage the "about" is off by at most $1$, adding up to at most $n$. –  André Nicolas Aug 23 '12 at 19:41
For the second problem, you are just counting the number of coprime pairs $1\leq a < b \leq n$. This problem has appeared on math.se before, e.g. math.stackexchange.com/questions/64498/…. –  Sean Eberhard Aug 23 '12 at 23:32

Number theoretic functions such as the divisor function $d(k)$ jump around quite a bit. Summation often makes the behaviour much smoother. The most familiar example is the function $f(k)$ which is $1$ if $k$ is prime, and $0$ if it is not. Then $\sum_1^n f(k)$ is asymptotically equal to $\frac{n}{\log n}$.

Similarly, $\sum_1^n d(k)$ is well-behaved. The beginnings of the analysis are straightforward. But there is a large literature on the fine details, stretching from the nineteenth century to now.

In the numbers $1$ to $n$, the divisor $1$ occurs $n$ times. The divisor $2$ occurs exactly $\lfloor n/2\rfloor$ times. The divisor $3$ occurs
$\lfloor n/3\rfloor$ times, and so on. Thus $$\sum_1^n d(k)=n+ \left\lfloor \frac{n}{2}\right\rfloor+ \left\lfloor \frac{n}{3}\right\rfloor+\cdots +\left\lfloor \frac{n}{n}\right\rfloor.$$ If we replace $\lfloor n/i\rfloor$ by $n/i$, we make an error of at most $1$ in each term, so $$\sum_1^n d(k)=n+ \frac{n}{2}+ \frac{n}{3}+\cdots + \frac{n}{n}+O(n).$$ By comparing the sum with an integral, one can show that there is a constant $\gamma$, the Euler-Mascheroni constant such that $$\lim_{n\to\infty} \left(1+\frac{1}{2}+\cdots+\frac{1}{n}\right)-\log n=\gamma.$$ It follows that $$\sum_1^n d(k)=n\log n +O(n).$$ Much more is known! The main term is, as we saw, $n\log n$. But a more detailed analysis, that goes back to Dirichlet, shows that $$\sum_1^nd(k)=n\log n +(2\gamma-1)n+O(n^{1/2}).$$

-
$$\sum_{k=1}^n\sigma(k)=\pi^2n^2/12+O(n\log n)$$ This is Theorem 324 in Hardy and Wright, An Introduction to the Theory of Numbers, a book dear to the hearts of Number Theorists worldwide. The proof is not too difficult, but a bit too long for me to want to type it out here.