Let $n$ be a natural number. Prove that $\displaystyle \sum_{k=1}^n\lfloor n/k\rfloor+\lfloor \sqrt{n} \rfloor$ is even.
I tried to introduce the fractional part, but it didnt help me. Next, I considered an inequality to create a bound, but that too was in vain. Next I found out that $\lfloor x \rfloor = \lfloor x/2 \rfloor +\lfloor x+1/2 \rfloor$. I applied this, but as all were as a sum, it became hard for me to cancel out and it made my work difficult. Now the next problem is about the square root in the box. I once saw in an example that
$$\lfloor \sqrt{n}+ \sqrt{n+1} \rfloor = \sqrt{4n+1}$$
Now even if this may seem useful, I cannot understand how to remove the $\lfloor \sqrt{n+1} \rfloor $ from the identity. Any help would be helpful!
Since $\lfloor \sqrt{n}\rfloor^2$ and $\lfloor \sqrt{n}\rfloor$ have the same parity it suffices to show the following identity $$\sum_{k=1}^n\lfloor n/k\rfloor=2\sum_{k=1}^{\lfloor \sqrt{n}\rfloor} \lfloor n/k\rfloor-\lfloor \sqrt{n}\rfloor^2. $$ See Hurkyl's answer to Simplifying $\sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor}$?
In other words, in a direct way, $$\begin{align} \sum_{k=1}^n \lfloor n/k \rfloor &= \sum_{j,k} [1 \leq j] [1 \leq k] [jk \leq n]\\ &=\underbrace{\sum_{j\not=k} [1 \leq j] [1 \leq k] [jk \leq n]}_{\text{even}}+\sum_{j=k} [1 \leq j] [1 \leq k] [jk \leq n]\\ &\equiv \sum_{j=k} [1 \leq j] [1 \leq k] [jk \leq n] =\lfloor \sqrt{n}\rfloor\pmod{2}\end{align}$$ where $[P]$ is $1$ if $P$ is true, and $0$ if false.