Floor function inequality

Question

I am racking my brain trying to get this problem solved and I can't seem to break it...

Let $m, n$ be positive integers, with $m > 1$. Prove

$$\left\lfloor\frac{n}m\right\rfloor+\left\lfloor\frac{n+1}m\right\rfloor\le\left\lfloor\frac{2n}m\right\rfloor$$

I started trying to use the inequalities that say

$$\lfloor x\rfloor + \lfloor y\rfloor + \lfloor x+y\rfloor \le \lfloor 2x\rfloor + \lfloor 2y\rfloor\;.$$

From there I rewrote both sides with the notion that for a real number $y$,

$y = \lfloor y\rfloor + \{y\}$, where $\{y\}$ is the fractional part, but I keep going in circles and can not get to the desired result...

Answer 1

If you want to use you that inequality of yours let $x=\dfrac{n}{m}$ and $y=\dfrac{1}{m}:$ $$\bigg\lfloor \frac{n}{m}\bigg\rfloor+\bigg\lfloor \frac{1}{m}\bigg\rfloor+\bigg\lfloor \frac{n+1}{m}\bigg\rfloor\leq\bigg\lfloor \frac{2n}{m}\bigg\rfloor+\bigg\lfloor \frac{2}{m}\bigg\rfloor$$

Since $m>1\Rightarrow \bigg\lfloor\dfrac{1}{m}\bigg\rfloor=0$. If additionally $m>2$ then also $\bigg\lfloor\dfrac{2}{m}\bigg\rfloor=0$ so all we need to do is check for $m=2:$

$$\bigg\lfloor \frac{n}{2}\bigg\rfloor+\bigg\lfloor \frac{n+1}{2}\bigg\rfloor\leq n+1$$

Since $\displaystyle\bigg\lfloor \frac{n}{2}\bigg\rfloor+\bigg\lfloor \frac{n+1}{2}\bigg\rfloor\leq \dfrac{n}{2}+\dfrac{n+1}{2}=n+\dfrac{1}{2}<n+1$ this case is verified.

Answer 2

HINT: Let $a=\left\lfloor\dfrac{n}m\right\rfloor$, so that $$a\le\frac{n}m<a+1\;,$$ and therefore $am\le n<am+m$. Either $n+1<am+m$, in which case $$a<\frac{n+1}m<a+1$$ and $\left\lfloor\dfrac{n+1}m\right\rfloor=a$, or $n+1=am+m$, in which case $\left\lfloor\dfrac{n+1}m\right\rfloor=a+1$. Can you now work out what $\left\lfloor\dfrac{2n}m\right\rfloor$ is in each of these cases?

Answer 3

Let $f(n)=\left\lfloor\frac{2n}m\right\rfloor -\left\lfloor\frac{n}m\right\rfloor-\left\lfloor\frac{n+1}m\right\rfloor$

Then it is easy to prove that $f(n+m)=f(m)$ and $f(n) \geq 0 \forall 0 \leq n \leq m-1$.

Answer 4

Let $a={\sf floor}(\frac{n}{m})$ and $b={\sf floor}(\frac{n+1}{m})$.

We have $a \leq \frac{n}{m}$ and $b \leq \frac{n+1}{m}$, so $a+b \leq \frac{2n+1}{m}$. If this were an equality, it would imply that both $a =\frac{n}{m}$ and $b = \frac{n+1}{m}$, so that $m$ would divide both $n$ and $n+1$, and hence divide $n+1-n=1$ also, which is absurd.

So we have the strict inequality $a+b \lt \frac{2n+1}{m}$, yielding $m(a+b) \lt 2n+1$. Since $m,a+b$ and $2n+1$ are all integers, we deduce $m(a+b) \leq 2n$. So $a+b$ is an integer lower than $\frac{2n}{m}$ ; it is therefore smaller than the floor of $\frac{2n}{m}$ as wished.