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.

Thank you in advance.

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

Edit. I'm beginning with my second solution because I think it's better than my first. But I'm leaving the first too as some people have already upvoted it.

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.

The other solution is really the same, but with more explicit algebra.

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.


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.