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),$$

which leads to your

$$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.