3
$\begingroup$

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

$\endgroup$
3
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ In the final result $\delta$ has the same exact meaning of $d$, identify the same divisors, right? $\endgroup$
    – Alessar
    Nov 27 '18 at 15:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – user593746
    Nov 27 '18 at 15:03
  • $\begingroup$ You're welcome, thanks for the very good answer! $\endgroup$
    – Alessar
    Jan 16 '19 at 15:00
2
+50
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Alessar
    Jan 16 '19 at 11:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – epi163sqrt
    Jan 16 '19 at 12:14
  • $\begingroup$ Sheuer, one curious question; this kind of derivation in this proof can be done only using Dirichlet convolutions? $\endgroup$
    – Alessar
    Jan 17 '19 at 7:39
  • 1
    $\begingroup$ @Alessar: Many thanks for accepting my answer and granting the bounty. I've added a derivation based upon Dirichlet convolution. $\endgroup$
    – epi163sqrt
    Jan 17 '19 at 9:55
  • 1
    $\begingroup$ Wow! Thanks! Wish I could give 100 times that bounty! $\endgroup$
    – Alessar
    Jan 17 '19 at 9:58

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.