How to show that $\lfloor n/1\rfloor+\lfloor n/2 \rfloor+....+\lfloor n/n\rfloor+\lfloor{\sqrt{n}}\rfloor$ is even?

Question

Let $n$ is a natural number. Prove that $$\left\lfloor\frac{n}{1}\right\rfloor+\left\lfloor\frac{n}{2}\right\rfloor+....+\left\lfloor\frac{n}{n}\right\rfloor+\left\lfloor{\sqrt{n}}\right\rfloor$$
is even.

I used induction and the inequality $$x-1<\lfloor{x}\rfloor\le{x}$$ to prove it.

Is there any other, nicer way to do it?

Answer 1

Let $$S = \{\,(a,b)\in\mathbb N^2\mid ab\le n\,\} $$ and $$ T=\{\,(a,a)\in\mathbb N^2\mid a^2\le n\,\}.$$ Then $$ |S|=\sum_{b\ge 1}|\{\,a\in\mathbb N\mid a\le\tfrac nb\,\}|=\sum_{b\ge 1}\lfloor \tfrac nb\rfloor =\left\lfloor \frac n1\right\rfloor+\left\lfloor \frac n2\right\rfloor+\ldots +\left\lfloor \frac nn\right \rfloor$$ and $$ |T|=\lfloor \sqrt n\rfloor.$$ The map $(a,b)\mapsto (b,a)$ is a fixedpoint-free involution of $S\setminus T$, hence $|S\setminus T|$ is even. Since $$ \left\lfloor \frac n1\right\rfloor+\left\lfloor \frac n2\right\rfloor+\ldots +\left\lfloor \frac nn\right \rfloor+\lfloor\sqrt n\rfloor = |S\setminus T|+2|T|$$ we are done.