2
$\begingroup$

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!

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.

$\endgroup$
  • $\begingroup$ How do you get that? $\endgroup$ – user636268 Jan 21 at 15:34
  • 1
    $\begingroup$ This is my hint... ;-) $\endgroup$ – Robert Z Jan 21 at 15:36
  • 1
    $\begingroup$ You knew this identity from the beginning?😲 $\endgroup$ – user636268 Jan 21 at 15:37
  • 1
    $\begingroup$ @Md.ShamimAkhtar See my edit. $\endgroup$ – Robert Z Jan 21 at 15:44
  • 1
    $\begingroup$ @Md.ShamimAkhtar I gave you a direct way. $\endgroup$ – Robert Z Jan 21 at 16:06
1
$\begingroup$

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$.

$\endgroup$