Show that

$$\sum_{d|n} \frac{n}{d} \sigma(d) = \sum_{d|n} d \tau(d)$$

by changing the order of summations from each side to the other. $\sigma$ and $\tau$ are divisor sum functions.

Yes, I do can prove this by putting $\sum_{d|n} \frac{n}{d} \sigma(d)=F(n)$ and $\sum_{d|n} d \tau(d)=G(n)$ and using the property of multiplicative function. However, since professor mentioned that we have to be familiar with changing the order of summations, I tried to solve this just directly. But unlike other problems, some kind of mysterious cycle just looped again and again regardless of which side I choose to transform into the other.

Here is what I've been doing with the left side (but the miserable failure was just about the same as starting from the right side).

$$\sum_{d|n} \frac{n}{d} \sigma(d)=\sum_{d|n}\frac{n}{d} \sum_{c|d}c $$

Let ck=d where k is a positive integer. Then by changing the order of the summation,

$$\sum_{d|n}\frac{n}{d} \sum_{c|d}c =\sum_{c|n}c\sum_{k|\frac{n}{c}}\frac{n}{ck} =\sum_{c|n}n\sum_{k|\frac{n}{c}}\frac{1}{k}$$

Then one might notice that since $k$ is still remaining there, there is no possibility (at least for me...) to make $\tau$ to come out. Only $\sigma$ will just come out again to no avail and return to the very first state. I actually tried

$$\sum_{d|n} \frac{n}{d} \sigma(d)=\sum_{d|n} d \sigma(\frac{n}{d}) $$

but this one failed, too. So logically, my conclusion was that there is some kind of manipulating terms that can make me out of this infinite looping, but I haven't recognized the method yet. I think if I can tackle this problem from any side, then I could deal with the other side using a similar way.

Could anyone help me solving the secret of changing the order of summation? Thanks.


Start with $$\sum_{d|n} \frac{n}{d}\sigma(d) = \sum_{d|n} d \; \sigma\left(\frac{n}{d}\right).$$ This is $$\sum_{d|n} \sum_{e|n/d} de.$$ Now put $q=de$ to get $$\sum_{d|n} \sum_{q/d|n/d} q = \sum_{q|n} \sum_{d|q} q = \sum_{q|n} q \sum_{d|q} 1 = \sum_{q|n} q \; \tau(q).$$ The first equality holds because $q/d|n/d$ means that for some $m$ we have $m q/d = n/d$ which means $mq =n,$ so $q$ is a divisor of $n$, and the number of times that it occurs is the number of $d$ such that $d|q$ or $\tau(q).$

  • $\begingroup$ So the idea was to make $de=q$ so that $\sigma$ will never arise again... Thanks. That was clever. $\endgroup$ – Taxxi Nov 10 '13 at 0:18

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.