Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
So the idea was to make $de=q$ so that $\sigma$ will never arise again... Thanks. That was clever. –  TaxxiDriver Nov 10 '13 at 0:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.