# Sum of the number of factors of natural numbers equality

I have come upon the problem of proving an equality of the divisor function

How can you prove that the the expressions for the summatory divisor function are the same; $\sum_{m=1}^n d(m) = \sum_{m=1}^n \lfloor \frac{n}{m} \rfloor$. The explanation I find in the Wikipedia article (http://en.wikipedia.org/wiki/Divisor_summatory_function) is not clear enough for me, and I am trying to see if it is possible to prove it on simpler terms and without referring to the other expressions shown there.

• There is something missing --- the second sum is empty. – Gerry Myerson Apr 26 '14 at 6:00
• Thank you for noticing, fixed it. – suomynona Apr 26 '14 at 6:14

So, we count in two ways the number of pairs $(j,k)$ of positive integers such that $jk\le n$. First, the number of pairs with $jk=m$ is just $d(m)$, so the total number of pairs is $$\sum_ {m=1}^n d(m)\ .$$ On the other hand, the number of pairs with a given value of $j$ is $n/j$ rounded down, and so the total is $$\sum_{j=1}^n\Bigl \lfloor \frac{n}{j}\Bigr \rfloor \ .$$ Therefore the two sums are equal.
Changing the name of the variable and writing the expression as a double sum, $$RHS=\sum_{j=1}^n\Bigl\lfloor\frac{n}{j}\Bigr\rfloor =\sum_{j=1}^n\sum_{k=1}^{\lfloor n/j\rfloor}1\ .$$ Note that the condition on $k$, namely, $1\le k\le\lfloor n/j\rfloor$, is equivalent to $1\le jk\le n$. So we have $$RHS=\sum_{j=1}^n\sum_{k:1\le jk\le n}1\ ;$$ writing $jk=m$ and changing the order of summation, $$RHS=\sum_{j=1}^n\sum_{m=1}^n\sum_{k:jk=m}1 =\sum_{m=1}^n\sum_{j=1}^n\left.\cases{1&if j\mid m\cr 0&otherwise\cr}\right\} =\sum_{m=1}^n d(m)$$ as claimed.