A recursive identity for the sum of divisors

Question

Let $(n,k)=\gcd(n,k)$ and $(n,l,k) = \gcd(\gcd(n,l),k)$, $\sigma(n)=$ sum of divisors of $n$. My question is, how the "ugly" identity, which I can prove it is true, can be "simplified" in presentation?:

$$\sigma(n) = \sum_{k=1}^{n-1}\frac{\sigma((n,k))}{n-1}+\frac{n}{n-1}\sum_{l=1}^{n-1}\sum_{k=1}^{(n,l)}\frac{\sigma((n,l,k))}{(n,l)}$$

Note, that the interesting part for this identity is, that we compute $\sigma(n)$ using only numbers $x<n$ and $\sigma(x)$.

Thanks for your help.

Answer 1

Swapping your use of $k$ and $l$ in the second term gives

$$\sigma(n) = \sum_{k=1}^{n-1}\frac{\sigma((n,k))}{n-1}+\frac{n}{n-1}\sum_{k=1}^{n-1}\sum_{l=1}^{(n,k)}\frac{\sigma((n,k,l))}{(n,k)}$$

Multiplying by $n-1$,

$$(n-1)\sigma(n)=\sum_{k=1}^{n-1}\left(\sigma((n,k))+n\sum_{l=1}^{(n,k)}\frac{\sigma((n,k,l))}{(n,k)}\right)$$

By taking the sum up to $k=n$ rather than $k=n-1$ we get

$$n\sigma(n)+\sum_{l=1}^{n}\sigma((n,l))=\sum_{k=1}^{n}\left(\sigma((n,k))+n\sum_{l=1}^{(n,k)}\frac{\sigma((n,k,l))}{(n,k)}\right)$$

Then after getting rid of the redundant terms and dividing both sides by $n$ we have

$$\sigma(n)=\sum_{k=1}^{n}\sum_{l=1}^{(n,k)}\dfrac{\sigma((n,k,l))}{(n,k)}$$

Answer 2

I think, one way to present such a recursive formula in a nice way, is the classical one, given by

$$\sigma(n) = \sigma(n-1) + \sigma(n-2) - \sigma(n-5) - \sigma(n-7) + \sigma(n-12) +\sigma(n-15) + \cdots +$$ Here $1,2,5,7,...$ is the sequence of generalized pentagonal numbers $\frac{3n^2-n}{2}$ for $n = 1,-1,2,-2,...$ and the signs are repetitions of $1,1,-1,-1$.