# Equivalent formula for the sum of first $n$ values of the number of divisors function

In the notes of the following OEIS sequence( https://oeis.org/A006218), it is stated that $$\sigma_0(1) + \sigma_0(2) +... + \sigma_0(n) = \left[ \dfrac{n}{1} \right] + \left[ \dfrac{n}{2} \right] +... + \left[ \dfrac{n}{n} \right] ,$$ where $\sigma_0(n)$ is the number of divisors of $n$, and $[x]$ denotes the integer part of $x$. How can one prove this identity? I tried approaching it inductively but i failed.

• $$\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$$ – Dietrich Burde Jan 1 '18 at 20:09

We have $$\sum_{k=1}^n\sigma(k)=\sum_{k=1}^n\sum_{d\mid j}1=\sum_{d=1}^n \sum_{j:1\le j\le n,d\mid j}=\sum_{j=1}^n\left\lfloor\frac nj\right\rfloor.$$ In words, $\sum_{k=1}^n\sigma(k)$ counts the number of pairs $(j,k)$ of positive integers with $j\mid k$ and $k\le n$. In each such pair $1\le j\le n$, and the number of admissible $(j,k)$ for a given $j$ is the number of multiples of $j$ up to $n$, which is $\left\lfloor n/j\right\rfloor$.
Hint: if you were to calculate the left-hand side by hand, how many times in total would $1$ be counted as a divisor of one of the numbers from $1$ to $n$? How many times would $2$ be counted as a divisor? What about $3$?