Simple Divisor Sum Transformation by Changing the Order of Double Summation

Question

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.

Answer 1

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