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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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