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

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?

-
Induction is a good way to go and the inequality you used is all we have about the floor function, so what could be a better way? –  Hagen von Eitzen Feb 2 '14 at 18:27
A duplicate of this question was asked later. You might find my answer to that question useful. –  David Feb 18 at 4:58
@David +1. Truly remarkable answer by you in that post. –  Ishu Feb 18 at 7:36

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.