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


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

  • $\begingroup$ It is best not to try to manipulate "canned" inequalities: go back to basics. $\endgroup$ – André Nicolas Feb 5 '13 at 3:55
  • $\begingroup$ If you can't prove it, try looking for a counterexample. You might find it, or the search will help to understand why it must be true, and thus to manufacture a proof. $\endgroup$ – vonbrand Feb 5 '13 at 4:11

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.

  • $\begingroup$ This is kind of what I had in mind, but I had y = (n+1)/m instead of y = 1/m. That makes it much easier to understand. I'd been playing around in my head the idea that m=2 had something to do with this, just based upon the right hand side of the inequality, but now I see just by calling y=1/m, it seems much simpler now. Thanks!! $\endgroup$ – Eleven-Eleven Feb 5 '13 at 5:37
  • $\begingroup$ @Christopher No problem! $\endgroup$ – L. F. Feb 5 '13 at 6:00

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?


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.