# Prove that $\sum\limits_{k=1}^n\lfloor n/k\rfloor+\lfloor \sqrt{n} \rfloor$ is even. [duplicate]

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!

## marked as duplicate by rtybase, Community♦Jan 21 at 15:50

• Please format your question through latex. – lightxbulb Jan 21 at 15:17
• I do not know how to use latexx – user636268 Jan 21 at 15:20
• math.meta.stackexchange.com/questions/5020/… – lightxbulb Jan 21 at 15:20
• Do you mean $\lfloor x \rfloor$? You did mention largest integer not exceeding $x$. – Mohammad Zuhair Khan Jan 21 at 15:21
• Yes the floor function – user636268 Jan 21 at 15:22

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.
Hint: try to prove this by induction on $$n$$. When you replace $$n$$ by $$n+1$$, some terms in the expression will increase by $$1$$, count how many do for each $$n$$.