# Proof for Sum of Sigma Function

How to prove:

$$\sum_{k=1}^n\sigma(k) = n^2 - \sum_{k=1}^nn\mod k$$

where $\sigma(k)$ is sum of divisors of k.

-

## 2 Answers

Using the identity \begin{align} n \ \text{mod} \ k = n - k \lfloor \tfrac{n}{k} \rfloor, \end{align} one has \begin{align} \sum_{k = 1}^{n} (n \ \text{mod} \ k) =\sum_{k = 1}^{n} n - k \lfloor \tfrac{n}{k} \rfloor = n^{2} - \sum_{k = 1}^{n} k \lfloor \tfrac{n}{k} \rfloor. \end{align} Finally, since \begin{align} \sum_{k = 1}^{n} k \lfloor \tfrac{n}{k} \rfloor = \sum_{k = 1}^{n} \sigma(k), \end{align} the claim follows.

-

$$\sum_{k=1}^n \sigma(k) = \sum_{k=1}^n\sum_{d|k} d = \sum_{d=1}^n\sum_{k=1}_{d|k}^{n}d = \sum_{d=1}^n d\left\lfloor \frac n d\right\rfloor$$

Now just prove that $$d\left\lfloor \frac n d\right\rfloor = n-(n\mod d)$$

-
You beat me to the punch by 1 min! –  user02138 Jun 13 '13 at 15:57