A proof of $\sum\limits_{d|n} \sigma(d) = n \sum\limits_{d|n} {\tau(d) \over d}$

I'm trying to proof the following statement:

Let $$n \in \mathbb{Z}$$ and the $$\sum$$ are on the divisors $$d$$ of $$n$$. Show that $$\sum\limits_{d|n} \sigma(d) = n \sum\limits_{d|n} {\tau(d) \over d}.$$

I arrive to a point where I have a product of polynomials and I can't simply find a way to reorder the factors in order to resemble some kind of useful structure for this problem. Any suggestions?

EDIT: due to unsuscribe of user593746, I can't ask delucidation, so I reopen the question because I wish to have detailed delucidation on the passages on the first row of his good proof (summatory index manipulations and t outside the first sum):

We have $$\sum_{d\mid n}\sigma(d)=\sum_{d\mid n}\sum_{t\mid d}t=\sum_{t\mid n}\sum_{k\mid \frac{n}{t}}t=\sum_{t\mid n}t\sum_{k\mid \frac{n}t}1,$$ where $$k=\frac{d}{t}$$. So $$\sum_{d\mid n}\sigma(d)=\sum_{t\mid n}t\tau\left(\frac{n}t\right)=\sum_{\delta \mid n}\frac{n}{\delta}\tau(\delta)=n\sum_{\delta\mid n}\frac{\tau(\delta)}{\delta},$$ where $$\delta =\frac{n}{t}$$.

• Nov 27 '18 at 14:51
• The sums express two different ways to count the sum of how many divisors $c\mid n$ each divisor $d\mid n$ divides. Nov 27 '18 at 14:55
• Hey, do you remember user593746's nickname before he/she unsubscribe? Is it "Zvi"? Sep 6 '20 at 7:00

We have $$\sum_{d\mid n}\sigma(d)=\sum_{d\mid n}\sum_{t\mid d}t=\sum_{t\mid n}\sum_{k\mid \frac{n}{t}}t=\sum_{t\mid n}t\sum_{k\mid \frac{n}t}1,$$ where $$k=\frac{d}{t}$$. So $$\sum_{d\mid n}\sigma(d)=\sum_{t\mid n}t\tau\left(\frac{n}t\right)=\sum_{\delta \mid n}\frac{n}{\delta}\tau(\delta)=n\sum_{\delta\mid n}\frac{\tau(\delta)}{\delta},$$ where $$\delta =\frac{n}{t}$$.

• In the final result $\delta$ has the same exact meaning of $d$, identify the same divisors, right? Nov 27 '18 at 15:01
• Yep. I used a different variable because I wanted to define $\delta=\frac{n}{t}$, which could be confusing if I say $d=\frac{n}{t}$, since $d$ is used in $k=\frac{d}{t}$ already. But then, which ever variables you are using as the indices of summation don't really matter.
– user593746
Nov 27 '18 at 15:03
• You're welcome, thanks for the very good answer! Jan 16 '19 at 15:00

Here is a derivation with some intermediate steps which might be helpful.

We obtain \begin{align*} \color{blue}{\sum_{d\mid n}\sigma(d)}&=\sum_{d\mid n}\sum_{t\mid d}t\tag{1}\\ &=\sum_{{t\mid d\mid n}\atop{t,d\geq 1}}t\tag{2}\\ &=\sum_{{t \mid tk \mid n}\atop{t,k\geq 1}}t\tag{3}\\ &=\sum_{{t \mid n,k \mid \frac{n}{t}}\atop{t,k\geq 1}}t\tag{4}\\ &\,\,\color{blue}{=\sum_{t \mid n}t\sum_{k \mid \frac{n}{t}}1}\tag{5} \end{align*}

Comment:

• In (1) we use the definition of the divisor function $$\sigma(d)=\sum_{t| d}t$$.

• In (2) we write the index region somewhat more compactly. This does not change the sum, as it is only a rearrangement of the summands.

• In (3) we use $$t|d \Longleftrightarrow \exists k\geq 1 : tk=d$$, assuming $$t,d,k$$ are positive integers.

• In (4) we use the transitivity of the $$|$$ operator: $$t| d| n\Longrightarrow t|n$$ and we also use $$t \cdot k| n\Longleftrightarrow t | \frac{n}{k}$$.

• In (5) we rearrange the summands again by summing at first over $$t| n$$. We also factor out $$t$$ from the inner sum, since $$t$$ does not depend on the index variable $$k$$.

[Add-on 2019-01-17]: A derivation using Dirichlet convolution due to OPs comment.

Taking the unit-function $$u(n)=1$$ for all $$n$$ and the function $$N(n)=n$$ for all $$n$$ we have \begin{align*} \tau(n)&=\sum_{d|n}1=(u\star u)(n)\\ \sigma(n)&=\sum_{d|n}d=(u\star N)(n) \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{d|n}\sigma(d)}&=(\sigma \star u)(n)\\ &=((u\star N)\star u)(n)\\ &=(u\star(N \star u))(n)\\ &=(u\star (u\star N))(n)\\ &=((u\star u) \star N)(n)\\ &=(\tau \star N)(n)\\ &\,\,\color{blue}{=\sum_{d|n}\tau(d)\frac{n}{d}} \end{align*} and the claim follows.

• Thank you for this precise explanation; one thing, the term $t$ can be carried out of the fist sum according to some kind of properties or constraint? Jan 16 '19 at 11:44
• @Alessar: You're welcome and you're right, we can factor out $t$ since it does not depend on the index of the inner sum. I've updated the answer accordingly. Jan 16 '19 at 12:14
• Sheuer, one curious question; this kind of derivation in this proof can be done only using Dirichlet convolutions? Jan 17 '19 at 7:39
• @Alessar: Many thanks for accepting my answer and granting the bounty. I've added a derivation based upon Dirichlet convolution. Jan 17 '19 at 9:55
• Wow! Thanks! Wish I could give 100 times that bounty! Jan 17 '19 at 9:58