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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

Just for fun, here is an alternative proof, using the same induction approach as another math.se answer of mine.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\floor}[1]{\lfloor#1\rfloor} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

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.