For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$

Question

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$

---

My try :

Left hand side :
$\begin{align} \sum_{d|p^k}\sigma (d) &= \sigma(p^0) + \sigma(p^1) + \sigma(p^2) + \cdots + \sigma(p^k) \\ &= \dfrac{p^{0+1}-1}{p-1} + \dfrac{p^{1+1}-1}{p-1} + \cdots + \dfrac{p^{k+1}-1}{p-1} \\&= \dfrac{1}{p-1}\left( (p + p^2 + \cdots + p^{k+1}) - (k+1)\right) \\&= \dfrac{1}{p-1}\left(\dfrac{p(p^{k+1}-1)}{p-1}- (k+1)\right) \\ \end{align}$

I'm not sure if I am in right path; this doesn't look simple. Any help ?

Answer 1

You can reduce to prime powers to get the job done, but that doesn't get at the heart of the equality.

$$\sum_{d\mid n}\sigma(d)=\sum_{d\mid n}\sum_{r\mid d}r=\sum_{r\mid d\mid n}r=\cdots$$

Can you continue? For each $r\mid n$, how many times is $r$ a summand of the above sum?

Answer 2

Define the functions $N$ and $1$ by $N(n)=n$ and $1(n)=1$ for all $n \in \mathbb{N}.$

An equivalent, but easier to write, solution is to note that the function $\sum_{d|n}\sigma(d)$ is the Dirichlet convolution $\sigma\ast 1$ and thus the definition $\sigma=N*1$ implies that $$\sigma*1=(N*1)*1=N*(1*1).$$ Now notice that $1*1$ is the classical divisor function $\tau$ and we therefore get $$ \sigma*1=N*\tau,$$ which provides the required answer.

Answer 3

looking at this intuitively, firstly we note that: $$ \sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d) \\ = \sum_{d|n} d\tau(n/d) $$ so now we are summing the divisors $d$ of $n$, each divisor being counted with multiplicity $\tau(n/d)$. so you just have to persuade yourself that this multiplicity is appropriate.

but this is evident if we look at a particular $d$, since for any integer $m$ we have $$ dm | n \Leftarrow \Rightarrow m | n/d $$ in words there is a 1-1 correspondence between (a) multiples of $d$ which divide $n$, and (b) divisors of $n/d$