<s>[INST] Showing that $\sum_{m=1}^{n}{\sigma(m)}=\sum_{k=1}^{n}{k\cdot \left\lfloor \frac n k\right\rfloor}$ Let $n \in \mathbb{N}$.
$\sigma$ is an arithmetic function and $\sigma(n)$ is the sum of the (positive) divisors of $n$.
How to show that $\sum_{m=1}^{n}{\sigma(m)}=\sum_{k=1}^{n}{k\cdot \left\lfloor \frac n k\right\rfloor}$?
My idea was to show it by induction:
$n=1:$
$\sum_{m=1}^{1}{\sigma(m)}=\sigma(1)=\sum_{d\vert1}{d}=1=\sum_{k=1}^{1}{1\cdot \left\lfloor \frac 1 1\right\rfloor}$
So it holds for $n=1$.
$n \mapsto n+1:$
$\sum_{m=1}^{n+1}{\sigma(m)}$
$=\sigma(n+1)+\sum_{m=1}^{n}{\sigma(m)}$
$=\sigma(n+1)+\sum_{k=1}^{n}{k\cdot \left\lfloor \frac n k\right\rfloor}$
$=\sum_{d\vert n+1}{d}+\sum_{k=1}^{n}{k\cdot \left\lfloor \frac n k\right\rfloor}$
$=\sum_{k=1}^{n+1}{k\cdot \left\lfloor \frac n k\right\rfloor}$
So it holds for all $n \in \mathbb{N}$.
I'm not sure if this is completely correct. Especially in the last step I don't know how to argue that the equality holds. Is there something to improve?
 [/INST] To prove the induction step, consider
$$\begin{equation}\begin{aligned}
& \sum_{k=1}^{n+1}k\cdot \left\lfloor \frac{n+1}{k}\right\rfloor - \sum_{k=1}^{n}k\cdot \left\lfloor \frac{n}{k}\right\rfloor \\
& = (n + 1)\cdot \left\lfloor \frac{n+1}{n+1}\right\rfloor + \sum_{k=1}^{n}k\cdot \left\lfloor \frac{n+1}{k}\right\rfloor - \sum_{k=1}^{n}k\cdot \left\lfloor \frac{n}{k}\right\rfloor \\
& = (n + 1) + \sum_{k=1}^{n}k\cdot \left(\left\lfloor \frac{n+1}{k}\right\rfloor - \left\lfloor \frac{n}{k}\right\rfloor\right)
\end{aligned}\end{equation}\tag{1}\label{eq1A}$$
The part in the summation brackets is
$$m = \left\lfloor \frac{n+1}{k}\right\rfloor - \left\lfloor \frac{n}{k}\right\rfloor  \tag{2}\label{eq2A}$$
For each $k$, the division algorithm states there's a unique positive integer $j$ and non-negative integer $r$ such that
$$n = jk + r, \; 0 \le r \lt k \tag{3}\label{eq3A}$$
With $0 \le r \lt k - 1$, \eqref{eq2A} gives $m = j - j = 0$. Only when $r = k - 1$, so $n + 1 = (j + 1)k$, does \eqref{eq2A} give a non-zero value, i.e., $m = (j + 1) - j = 1$. This means the only non-zero terms in the summation in the last line of \eqref{eq1A} are of $k$ and occur when $k$ is a factor of $n + 1$, so the summation itself is of all positive factors of $n + 1$ less than or equal to $n$. Adding $n + 1$ then gives the sum of all positive factors of $n + 1$. Thus, replacing the last line in \eqref{eq1A} with this and using the induction hypothesis gives
$$\begin{equation}\begin{aligned}
& \sum_{k=1}^{n+1}k\cdot \left\lfloor \frac{n+1}{k}\right\rfloor - \sum_{k=1}^{n}k\cdot \left\lfloor \frac{n}{k}\right\rfloor = \sum_{d\,\mid\, n+1}{d} \\
& \sum_{k=1}^{n+1}k\cdot \left\lfloor \frac{n+1}{k}\right\rfloor - \sum_{m=1}^{n}\sigma(m) = \sigma(n + 1) \\
& \sum_{k=1}^{n+1}k\cdot \left\lfloor \frac{n+1}{k}\right\rfloor = \sum_{m=1}^{n + 1}\sigma(m) 
\end{aligned}\end{equation}\tag{4}\label{eq4A}$$
</s>