# Show that $\, 0 \leq \left \lfloor{\frac{2a}{b}}\right \rfloor - 2 \left \lfloor{\frac{a}{b}}\right \rfloor \leq 1$

How can I prove that, for $a,b \in \mathbb{Z}$ we have $$0 \leq \left \lfloor{\frac{2a}{b}}\right \rfloor - 2 \left \lfloor{\frac{a}{b}}\right \rfloor \leq 1 \, ?$$ Here, $\left \lfloor\,\right \rfloor$ is the floor function. I tried the following: say that $\frac{2a}{b} = x$, and $\left \lfloor{\frac{2a}{b}}\right \rfloor = m$, with $0 \leq x - m \leq 1$. I tried the same for $2 \left \lfloor{\frac{2a}{b}}\right \rfloor$, and then combining the two inequalities. It did not seem to help, though.

In general $$0\le \lfloor 2x\rfloor -2\lfloor x\rfloor\le 1.$$ Proof. Either $x\in [k,k+1/2)$ or $x\in [k+1/2,k+1)$, for some $k\in\mathbb Z$.

If $x\in [k,k+1/2)$, then $$\lfloor 2x\rfloor=2k\quad\text{and}\quad 2\lfloor x\rfloor=2k,$$ while $x\in [k+1/2,k+1)$, for some $k\in\mathbb Z$, then $$\lfloor 2x\rfloor=2k+1\quad\text{and}\quad 2\lfloor x\rfloor=2k.$$ So the inequalities hold in both cases.

Hint: let $a=pb+q$ where $p, q \in \mathbb Z$ and $0\le q<b$.

$0 \leq \left \lfloor{\frac{2a}{b}}\right \rfloor \leq \frac{2*a}{b} < 2*(\left \lfloor{\frac{a}{b}}\right \rfloor + 1)$ = $2*\left \lfloor{\frac{a}{b}}\right \rfloor$ + 2

$\left \lfloor{\frac{2a}{b}}\right \rfloor$ is an integer, so being < than an other integer means being $\leq$ than this integer -1

=> $\left \lfloor{\frac{2a}{b}}\right \rfloor$ $\leq$ $2*\left \lfloor{\frac{a}{b}}\right \rfloor$ + 1

Edit:

As for the other part of the inequality:

$$\frac{2a}{b}= 2\left \lfloor{\frac{a}{b}}\right \rfloor + 2(\frac{a}{b})$$ with $(x)$ being the fractional part of $x$.

All that's left to consider is whether $2(\frac{a}{b})$ is smaller or greater than $1$ to conclude.

• I don't think this answer proves that $\;0 \leq \left \lfloor{\frac{2a}{b}}\right \rfloor - 2 \left \lfloor{\frac{a}{b}}\right \rfloor\;$. – Marnix Klooster Aug 27 '16 at 21:43
• Yes you're right, I'll edit. Thank you :) . Although I don't remember if I intended to answer thoroughly to that – mvggz Aug 29 '16 at 9:41


We are asked to prove $$\tag{0} 0 \le \floor{2x} - 2 \floor{x} \le 1$$ for all rational $\;x\;$.

Our first observation is that the fact that $\;x\;$ is rational, so that it can be written as $\;\tfrac a b\;$ for integers $\;a,b\;$, seems not to help us in any way, so we instead will attempt to prove this for all real $\;x\;$.

A quick graph of $\;\floor{2x} - 2 \floor{x}\;$ shows that it has a period of $1$. Abbreviating $\Ref 0$ by $\;P(x)\;$, this suggests we investigate $\;P(x+1)\;$:

$$\calc P(x + 1) \op=\hint{expand abbreviation \;P\;; simplify} 0 \le \floor{2x+2} - 2 \floor{x+1} \le 1 \op=\hint{move integer 2 out of left floor, and 1 out of right floor} 0 \le \floor{2x} + 2 - 2 (\floor{x}+1) \le 1 \op=\hint{simplify; abbreviation \;P\;} P(x) \endcalc$$

So we've proven $$\tag 1 \langle \forall x :: P(x) \;\equiv\; P(x + 1) \rangle$$ which is a kind of 'induction step'. If we can additionally prove the 'base case' $$\tag 2 \langle \forall x : 0 \le x \lt 1 : P(x) \rangle$$ then by induction our goal $\;\langle \forall x :: P(x) \rangle\;$ follows. We can prove $\Ref 2$ as follows: assuming $\;0 \le x \lt 1\;$, we have

$$\calc P(x) \op=\hint{abbreviation \;P\;} 0 \le \floor{2x} - 2 \floor{x} \le 1 \op=\hints{by our assumption and the definition of \;\floor{\cdot}\;} \hints{we have \;0 \le \floor{x} \lt 1\;, and \;\floor{\cdot}\; is integer,} \hint{so \;\floor{x} = 0\;} 0 \le \floor{2x} \le 1 \op=\hints{by our assumption and the definition of \;\floor{\cdot}\;} \hint{we have \;0 \le \floor{2x} \lt 2\;; \;\floor{\cdot}\; is integer} \true \endcalc$$

This completes the proof.