# Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$.

One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that

$$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln x)^{r - 1} + O\left(x(\ln x)^{r - 2}\right)$$

The base case $r = 2$ is easy with reversing the order of summation.

The only other progress that I made was the fact that $\sum_{n\le x}\tau_{r}(n) = \sum_{d\le x}\left\lfloor\frac{x}{d}\right\rfloor\tau_{r- 1}(d)$, but I don't know how to proceed.

We can write

$$\tau_{r+1}(n)= \sum_{d\mid n} \tau_r(d),$$

$$\sum_{n\leqslant x} \tau_{r+1}(n) = \sum_{d\leqslant x} \left\lfloor \frac{x}{d}\right\rfloor \tau_r(d),$$

but we can also write

$$\tau_{r+1}(n) = \sum_{d\mid n} \tau_r\left(\frac{n}{d}\right),$$

and that gives us

\begin{align} \sum_{n\leqslant x} \tau_{r+1}(n) &= \sum_{n\leqslant x} \sum_{d\mid n} \tau_r\left(\frac{n}{d}\right)\\ &= \sum_{d\leqslant x} \sum_{k\leqslant \frac{x}{d}} \tau_r(k)\\ &= \sum_{d\leqslant x} C_r\frac{x}{d}\left(\ln \frac{x}{d}\right)^{r-1} + O\left(\frac{x}{d}\left(\ln \frac{x}{d}\right)^{r-2}\right). \end{align}

Now we can estimate the lower-order part by $K\cdot \frac{x}{d}(\ln x)^{r-2}$, and since $\sum_{d\leqslant x} \frac{1}{d} = \ln x + O(1)$, the sum of these terms is, as it should be, $O(x(\ln x)^{r-1})$.

For the dominant terms, we find

\begin{align} \sum_{d\leqslant x} \frac{x}{d}\left(\ln \frac{x}{d}\right)^{r-1} &= \sum_{d\leqslant x} \frac{x}{d}\left(\ln x - \ln d\right)^{r-1}\\ &= \sum_{d\leqslant x} \frac{x}{d} \sum_{k=0}^{r-1} (-1)^k\binom{r-1}{k} (\ln x)^{r-1-k}(\ln d)^k\\ &= \sum_{k=0}^{r-1}(-1)^k x(\ln x)^{r-1-k}\binom{r-1}{k} \sum_{d\leqslant x} \frac{(\ln d)^k}{d}\\ &= \sum_{k=0}^{r-1}(-1)^k x(\ln x)^{r-1-k}\binom{r-1}{k} \left(\frac{(\ln x)^{k+1}}{k+1} + O(1)\right)\\ &= x(\ln x)^r\sum_{k=0}^{r-1}(-1)^k\binom{r-1}{k}\frac{1}{k+1} + O\left(x(\ln x)^{r-1}\right), \end{align}

and since

$$\sum_{k=0}^{r-1} (-1)^k\binom{r-1}{k}\frac{1}{k+1} = -\frac{1}{r} \sum_{k=0}^{r-1} (-1)^{k+1}\binom{r}{k+1} = \frac{1}{r},$$

we get

$$\sum_{n\leqslant x} \tau_{r+1}(n) = \frac{C_r}{r} x(\ln x)^r + O\left(x(\ln x)^{r-1}\right).$$

Since $\tau_1(n) = 1$ for all $n$, we immediately have

$$\sum_{n\leqslant x} \tau_1(n) = \lfloor x\rfloor = 1\cdot x(\ln x)^0 + O\left(x(\ln x)^{-1}\right),$$

hence $C_1 = 1 = \frac{1}{0!}$, and the recurrence $C_{r+1} = C_r/r$ yields $C_r = \frac{1}{(r-1)!}$, as desired.