Sum of floor of harmonic progression: $\sum_{i=1}^n\lfloor\frac ni\rfloor=2\sum_{i=1}^k\lfloor\frac ni\rfloor-k^2$ for $k=\lfloor\sqrt n\rfloor$

Question

This question is actually from a programming question that a formula is required to compute maths faster. (Please note that computer frequently rounds down to the nearest integer, thus the floor function is involved even if it is not explicitly stated in the question in the link)

So here is the formula I needed for the question:

For any positive integer $n$, Let $k=\lfloor\sqrt{n}\rfloor$. Prove that: $$ \sum_{i=1}^n \bigg\lfloor\frac{n}{i}\bigg\rfloor = 2\sum_{i=1}^k \bigg\lfloor\frac{n}{i}\bigg\rfloor - k^2 $$ I've verified this for $n$ up to $10000$ (by a computer) and got a (very) informal proof (which relies heavily on not-so-obvious assumptions). However, I wasn't able to obtain even a semi-informal proof, thus I've asked for help here.

P.S. I would like to have someone format the formula. I don't know how to do it. Thank you.

Edit: Thank you avraham for formatting that. Formatting a summation is much easier than I've expected!

Answer 1

The sum of the floor function counts the integer points lying on or below a branch of the rectangular hyperbola $xy=n$ (for $x,y\gt 0$). Sketch this and add the square with corners $(0,0),(0,\sqrt n), (\sqrt n, 0), (\sqrt n, \sqrt n)$ (the last of these points lies on the hyperbola).

$k^2$ counts the points in the square, and the tails are symmetrical about $x=y$. The sum taken once counts the points in the tail, plus the points in the square (which are therefore counted twice when the sum is multiplied by $2$).

You should be able to turn these observations into a formal proof.

This is now the fourth time (at least) that a different form of question about this sum has been posed recently. The sum is equivalent to the sum of the divisor function $d(n)$, which counts the number of divisors of $n$.

---

Further note

If $(a,b)$ is below the hyperbola xy=n, so is $(b,a)$. Look at the sum on the right-hand side, taken once. It counts the number of points $(x,y)$ on the line $x=1$ with $0\lt xy \le n$ i.e. $\left\lfloor \frac n1 \right\rfloor$, the points with $x=2$ i.e. $\left\lfloor \frac n2 \right\rfloor$, up to the points with $x=k$ ie $\left\lfloor \frac nk \right\rfloor$.

Note that the points $(a,b)$ with $a,b \le k$ are all counted in this sum. No points with $a \gt k$ are counted.

The sum also counts the points in a similar way for $y=1, 2 \dots k$. This also has the points $(a,b)$ with $a,b\le k$ - we note there are $k^2$ of these, but has no points with $b\gt k$.

If we count the sum twice, we have counted all the points under the hyperbola, but there are $k^2$ points we have counted twice, so we subtract $k^2$ to avoid double-counting.

For other questions see this, and this.