Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
It is best not to try to manipulate "canned" inequalities: go back to basics. –  André Nicolas Feb 5 '13 at 3:55
    
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. –  vonbrand Feb 5 '13 at 4:11

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
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!! –  Eleven-Eleven Feb 5 '13 at 5:37
    
@Christopher No problem! –  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?

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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