Prove that $\left\lfloor \lfloor x/2\rfloor/2 \right\rfloor=\lfloor x/4\rfloor$ for all $x$.

Question

This I approached the problem. I let $x = n + e$ where $n$ is an integer and $e$ is a decimal less than $1$ but not less than $0$. I substituted that into the equation to get $\left\lfloor \lfloor (n+e)/2\rfloor/2 \right\rfloor = \lfloor (n+e) / 4 \rfloor $

Then I will try for 4 cases. case 1: $0 \le x < 1/4$

case 2: $1/4 \le x < 1/2$

case 3: $1/2 \le x < 3/4$

case 4: $3/4 \le x < 1$

Am I allowed to pull the n out of $\left\lfloor \lfloor (n+e)/2\rfloor \right\rfloor$?

If I can then i can simply plug in the cases into $e$, which will give me $0=0$ for all $4$ cases. Is that correct?

Answer 1

First, we'll notice that, for $a$, $b$ two real numbers, $\left[\frac{a}{b}\right]$ is the quotient of the Euclidian division of $a$ by $b$.

Let $x\in\mathbb{R}$. Then $$x = 2 \left[\frac{x}{2}\right] + r'$$ with $r' \in \{0,1\}$

And likewise $$x = 4\left[\frac{x}{4}\right] + r''$$ with $r'' \in \{0,1,2,3\}$

Finally

$$\left[\frac{x}{2}\right] = 2 \left[\frac{\left[\frac{x}{2}\right]}{2}\right] + r$$ with $r \in \{0,1\}$.

So we have with the two first equations :

$$ 2 \left[\frac{x}{2}\right] + r' = 4\left[\frac{x}{4}\right] + r''$$

And, with the third :

$$2 \times \left( 2 \left[\frac{\left[\frac{x}{2}\right]}{2}\right] + r\right) + r' = 4\left[\frac{x}{4}\right] + r''$$

So $$4 \left[\frac{\left[\frac{x}{2}\right]}{2}\right] + (2r + r') = 4\left[\frac{x}{4}\right] + r''$$

Since $0 \leqslant 2r+ r' < 4$, the unicity of the Euclidian division allow us to say that $$ \left[\frac{\left[\frac{x}{2}\right]}{2}\right] = \left[\frac{x}{4}\right] $$

Answer 2

1. Clearly $\lfloor x/4 \rfloor=k$ if and only if $4k+4>x\ge 4k$.

2. Now $\lfloor\lfloor x/2\rfloor/2\rfloor =k$ if and only if $2k+2>\lfloor x/2\rfloor\ge 2k$.

But $2k+2>\lfloor x/2\rfloor\ge 2k$ if and only if $\lfloor x/2\rfloor=2k$ or $2k+1$. In the first case $\lfloor x/2\rfloor=2k$ if and only if $4k+2>x\ge 4k$, while in the second case $\lfloor x/2\rfloor=2k+1$ if and only if $4k+4>x\ge 4k+2$. Altogether $2k+2>\lfloor x/2\rfloor\ge 2k$ if and only if $4k+4>x\ge 4k$.

Therefore, $\lfloor x/4 \rfloor=\lfloor\lfloor x/2\rfloor/2\rfloor$.

Answer 3

Noting that $\left[\frac x2\right]\le\frac x2,$ then $\cfrac{\left[\frac x2\right]}2\le\frac x4,$ and so $$\left[\cfrac{\left[\frac x2\right]}2\right]\le\left[\frac x4\right].$$ That's the easy part.

Now, the other direction is not too tricky to prove. Take any $x\in\Bbb R.$ There exists a greatest integer $n$ such that $4n\le x,$ and there exists a greatest $k\in\{0,1,2,3\}$ such that $4n+k\le x.$ Putting $e=x-(4n+k),$ we have $x=4n+k+e$ and $0\le e<1.$ Now, $0\le k+e<4,$ so $\left[\frac x4\right]=\left[n+\frac{k+e}4\right]=n,$ regardless of which $k$ we're dealing with. We must show that $n\le\left[\cfrac{\left[\frac x2\right]}2\right]$ regardless of $k.$ Well, $$\left[\frac x2\right]=\left[2n+\frac{k+e}2\right]=\begin{cases}2n & k=0,1\\2n+1 & k=2,3.\end{cases}$$ Hence, since $$n=\left[\frac{2n}2\right]=\left[\frac{2n+1}2\right]$$ for any integer $n,$ then we're done.

Answer 4

Every real number $x$ can be written in the form $E+r$ where $E$ is an even integer and $0\le r\lt2$, and every even integer $E$ can be written in the form $4n+2m$ where $n$ is an integer and $m\in\{0,1\}$. Hence we can write $x$ as

$$x=4n+2m+r$$

with $n$ an integer, $m\in\{0,1\}$, and $0\le r\lt2$. Note that

$$\left\lfloor{2m+r\over4}\right\rfloor=\left\lfloor{m\over2}\right\rfloor=\left\lfloor{r\over2}\right\rfloor=0$$

for any such $m$ and $r$. Thus, making use only of the identity $\left\lfloor N+u\right\rfloor=N+\left\lfloor u\right\rfloor$ if $N$ is an integer (and $u$ is any real number), and spelling things out in tiny steps, we have

$$\begin{align} \left\lfloor{x\over4}\right\rfloor&=\left\lfloor n+{2m+r\over4} \right\rfloor\\ &=n+\left\lfloor {2m+r\over4} \right\rfloor\\ &=n\\ &=n+\left\lfloor{m\over2} \right\rfloor\\ &=\left\lfloor n+{m\over2} \right\rfloor\\ &=\left\lfloor{2n+m+\left\lfloor{r\over2}\right\rfloor\over2} \right\rfloor\\ &=\left\lfloor{\left\lfloor2n+m+{r\over2}\right\rfloor\over2} \right\rfloor\\ &=\left\lfloor{\left\lfloor{4n+2m+r\over2}\right\rfloor\over2} \right\rfloor\\ &=\left\lfloor{\left\lfloor{x\over2}\right\rfloor\over2} \right\rfloor\\ \end{align}$$

Added later: Here's a second proof. If $x\ge0$, write $x$ in binary:

$$x=d_n\ldots d_1d_0.d_{-1}d_{-2}\ldots$$

Then clearly

$$\begin{align} \left\lfloor{\left\lfloor{x\over2 }\right\rfloor\over2} \right\rfloor &=\left\lfloor{\left\lfloor d_n\ldots d_1.d_0d_{-1}d_{-2}\ldots\right\rfloor\over2} \right\rfloor\\ &=\left\lfloor{ d_n\ldots d_1\over2} \right\rfloor\\ &=\left\lfloor d_n\ldots d_2.d_1 \right\rfloor\\ &=\left\lfloor d_n\ldots d_2.d_1d_0d_{-1}\ldots \right\rfloor\\ &=\left\lfloor{x\over4}\right\rfloor\\ \end{align}$$

Finally, if $x\lt0$, choose an integer $N$ such that $4N+x\ge0$. Then, using the same trick of moving additive integers in and out of the floor function, we have

$$\begin{align} \left\lfloor{x\over4} \right\rfloor &=\left\lfloor N+{x\over4} \right\rfloor-N\\ &=\left\lfloor{4N+x\over4} \right\rfloor-N\\ &=\left\lfloor {\left\lfloor{4N+x\over2} \right\rfloor\over2} \right\rfloor-N\\ &=\left\lfloor{2N+\left\lfloor{x\over2} \right\rfloor\over2} \right\rfloor-N\\ &=\left\lfloor{\left\lfloor{x\over2} \right\rfloor\over2} \right\rfloor \end{align}$$

Answer 5

Any $x\in {\mathbb R}$ can be written as $$x=4k+2b_1+b_0+t$$ with $k\in{\mathbb Z}$, $\ b_1$, $b_0\in\{0,1\}$, and $0\leq t<1$. It follows that $0\leq b_0+t<2$, so that we have $$x/2=2k+b_1+t'$$ with $0\leq t'<1$. This in turn implies $\lfloor x/2\rfloor=2k+b_1$, and as $b_1\leq1$ it then follows that $$\left\lfloor\lfloor x/2\rfloor/2\right\rfloor=k=\lfloor x/4\rfloor\ ,$$ where on the right hand side we have used that $2b_1+b_0+t<4$.