2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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\;$. $\endgroup$ – Marnix Klooster Aug 27 '16 at 21:43
  • $\begingroup$ Yes you're right, I'll edit. Thank you :) . Although I don't remember if I intended to answer thoroughly to that $\endgroup$ – mvggz Aug 29 '16 at 9:41
0
$\begingroup$

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.

$\endgroup$

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.