7
$\begingroup$

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 ?

$\endgroup$
1
  • 2
    $\begingroup$ Reduce to the case of prime powers (as it looks like you've already done), then compute both sides of $n = p^k$. You don't need to compute a closed form for the left side directly; just count how many times each $p^r$ appears in the sum. $\endgroup$
    – anomaly
    Aug 25, 2014 at 21:16

3 Answers 3

Reset to default
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Exactly! I have felt the same when working as all I was doing was just algebra. If I am understanding correctly, it seems in your method $n$ need not be a single prime power($p^k$) ? $\endgroup$
    – AgentS
    Aug 25, 2014 at 21:21
  • 1
    $\begingroup$ and $r$ appears $\tau(d)*\tau(n)$ times i guess, not so sure sorry $\endgroup$
    – AgentS
    Aug 25, 2014 at 21:22
  • 2
    $\begingroup$ Indeed, $n$ is an arbitrary natural number here. We sum an $r$ for each instance of $r\mid d\mid n$, in other words the number of $r$s is equal to the number of $d$s for which $r\mid d\mid n$, which is equals the number of divisors of $n/r$... can you proceed further from here? What does the sum look like at this point? $\endgroup$
    – whacka
    Aug 25, 2014 at 21:28
  • 1
    $\begingroup$ i see it now xD so the multiplier for each $r$ is $\tau(n/r)$ in the sum; for example, $r=n$ appears only once because $\tau(n/n) = 1$ $\endgroup$
    – AgentS
    Aug 25, 2014 at 21:43
  • 2
    $\begingroup$ change of variables ($r\leftrightarrow\frac{n}{r}$): $~\sum\limits_{r\mid n}r\,\tau(\frac{n}{r})=\sum\limits_{r\mid n}\frac{n}{r}\tau(r)$ $\endgroup$
    – whacka
    Aug 25, 2014 at 21:51
3
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .