# Sum of number-of-divisors function equals $\sum_{j=1}^{n} \lfloor n/j \rfloor$.

I am trying to prove the identity

$$t(1) + t(2) + \cdots + t(n) = \Big\lfloor \dfrac{n}{1} \Big\rfloor + \Big\lfloor \dfrac{n}{2} \Big\rfloor + \cdots + \Big\lfloor \dfrac{n}{n} \Big\rfloor,$$

where $t(j)$ is the number of divisors of $j$.

Attempt: The highest power of $k \in \{2, 3, \ldots, n\}$ that divides $n!$ is given by

$$H_{k} := \Big\lfloor \dfrac{n}{k}\Big\rfloor + \Big\lfloor \dfrac{n}{k^{2}}\Big\rfloor + \cdots + \Big\lfloor\dfrac{n}{k^{N_{c}}}\Big\rfloor,$$

where $N_{c}$ is the maximal integer satisfying $k^{N_{c}} \leq n$. With a little thought, one can see that

\begin{equation*} \begin{split} \Big\lfloor\dfrac{n}{1}\Big\rfloor + \Big\lfloor\dfrac{n}{2}\Big\rfloor + \cdots + \Big\lfloor\dfrac{n}{n}\Big\rfloor &= H_{2} + H_{3} + \cdots + H_{n} + \Big\lfloor\dfrac{n}{1}\Big\rfloor \\ &= H_{2} + H_{3} + \cdots + H_{n} + n. \end{split} \end{equation*}

Each $H_{k}$ is a counted in the sum $t(1) + t(2) + \cdots + t(n)$, since each $t(k^{j})$ is a summand for $j \in \{1, 2, \ldots, N_{k}\}$, and also each $t(m)$ is a summand, where $m$ is a multiple of $k$ less than or equal to $n$.

This is where I'm a little stuck: I think that the only other summand in $t(1) + t(2) + \cdots + t(n)$ would be $1 + 1 + \cdots + 1 = n$, since each $t(j)$ counts $1$ as a divisor. My problem is showing that these are the only extra terms in $t(1) + t(2) + \cdots + t(n)$, which would show equality.

Any hints would be appreciated, or even suggestions of going about it a different way.

For the sake of completeness I would like to point out that this is usually done by induction. We seek to show that

$$\sum_{k=1}^n \tau(k) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

It holds for $n=1:$ $$\tau(1) = \lfloor 1\rfloor.$$

In the induction step we start from

$$\sum_{k=1}^n \tau(k) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

to get

$$\tau(n+1) + \sum_{k=1}^n \tau(k) = \tau(n+1) + \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

Now $$\tau(n+1) = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right)$$

since

$$\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor = \begin{cases} 1 \quad\text{if}\quad k|n+1 \\ 0 \quad\text{otherwise}.\end{cases}$$

Therefore we have

$$\sum_{k=1}^{n+1} \tau(k) = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right) + \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor \\ = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right) + \sum_{k=1}^{n+1} \bigg\lfloor \frac{n}{k} \bigg\rfloor \\ = \sum_{k=1}^{n+1} \bigg\lfloor \frac{n+1}{k} \bigg\rfloor$$

and the induction is complete.

• This is a much easier approach. Thank you. – Fred Apr 20 '16 at 0:57
• Is this really usually done by induction? – Unit Apr 20 '16 at 23:07

It really helps to write $t(1)+t(2)+\dotsb+t(n)$ in a triangular array:

1 +
1 + 1 +
1 + 0 + 1 +
1 + 1 + 0 + 1 +
1 + 0 + 0 + 0 + 1 +
1 + 1 + 1 + 0 + 0 + 1 +
1 + 0 + 0 + 0 + 0 + 0 + 1 +
1 + 1 + 0 + 1 + 0 + 0 + 0 + 1 +
1 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 1 + ...


Row $k$ is $t(k)$ written in a way that indicates which numbers from 1 to $k$ divide $k$. What do you see vertically?

As a final hint, note that $\lfloor n/d \rfloor$ counts the number of multiples of $d$ not exceeding $n$.

Since you have resolved your issue, let me explain the above. We have $$\sum_{k=1}^n t(k) = \sum_{k=1}^n \sum_{\substack{1 \le d \le n \\ d|k}} 1$$ and we want to swap the order of summation. Well, as $k$ and $d$ range over $1$ to $n$, you add $1$ every time $d$ divides $k$. This is the same as adding $1$ every time $k$ is a multiple of $d$. For a fixed $d$, how many multiples of $d$ are there between $1$ and $n$? Precisely $\lfloor n/d \rfloor$ (they are $d$, $2d$, $3d$, ..., $md \le n < (m+1)d$). So $$\sum_{k=1}^n \sum_{\substack{1 \le d \le n \\ d|k}} 1 = \sum_{d=1}^n \sum_{\substack{1 \le k \le n\\ k = md}} 1 = \sum_{d=1}^n \Big\lfloor \frac{n}{d} \Big\rfloor$$ and the proof is complete.

• I'm guessing that the first column counts what I wanted it to count... namely $n$. And this is the only extra term in my sum, since the other $1$'s are counting the $H_{k}$. Is this correct thinking? – Fred Apr 19 '16 at 6:12
• I don't see the need to introduce $H_k$ and factorials at all. – Unit Apr 19 '16 at 6:17
• I am using $n!$ because it's the only way I know how to relate the right-hand and left-hand sides of the sum. That is, it looked familiar to me from the fact that the highest power of $k$ that divides $n!$ is $\Sigma_{j=1}^{N_{k}} \lfloor n/(k^{j}) \rfloor$. This fact I've gotten from a different problem. – Fred Apr 19 '16 at 6:34
• Don't look at the different problem, just look at what Unit has done! – Gerry Myerson Apr 19 '16 at 7:08
• Right. According to this more general identity, we get that $$\sum_{n=1}^x \sum_{d|n} 1 = \sum_{d=1}^x \sum_{n=1}^{\lfloor x/d \rfloor} 1 = \sum_{d=1}^x \lfloor x/d \rfloor.$$ – mds May 24 '18 at 20:29

it is the basic theory of Dirichlet convolution : $$\zeta(s) = \sum_{n=1}^\infty n^{-s}$$ $$\zeta(s)^2 = (\sum_{n=1}^\infty n^{-s})(\sum_{m=1}^\infty m^{-s} )= \sum_{n=1}^\infty \sum_{m=1}^\infty n^{-s} m^{-s}= \sum_{n=1}^\infty n^{-s} \sum_{d|n} 1 = \sum_{n=1}^\infty \tau(n) n^{-s}$$ there is talso the Perron formula : $$\sum_{n=1}^\infty a_n n^{-s} = \int_{1-\epsilon}^\infty (\sum_{n=1}^\infty a_n \delta(x-n)) x^{-s} dx = s \int_1^\infty (\sum_{n \le x} a_n) x^{-s-1}dx$$ (integration by part)

hence

$$\zeta(s) = s \int_1^\infty (\sum_{n \le x}1) x^{-s-1} dx = s \int_1^\infty \lfloor x \rfloor x^{-s-1} dx$$

$$\zeta(s)^2 = s \int_1^\infty (\sum_{n \le x}\tau(n)) x^{-s-1} dx$$

but you can also write

$$\zeta(s)^2 = (\sum_{n=1}^\infty n^{-s} )s \int_1^\infty \lfloor x \rfloor x^{-s-1} dx = s \int_1^\infty (\sum_{n=1}^\infty \lfloor x/n \rfloor) x^{-s-1}dx$$ (since $\int_0^\infty f(x/n) x^{-s-1}dx = n^{-s} \int_0^\infty f(y) y^{-s-1}dy$ with $x= ny$)

i.e.

$$\sum_{n \le x}\tau(n) = \sum_{n=1}^\infty \lfloor x/n \rfloor = \sum_{n \le x} \lfloor x/n \rfloor$$