Verification of $\forall x \in \mathbb{R},(\bigg \lfloor \frac{\lfloor \frac{x}{2} \rfloor}{2} \bigg \rfloor = \lfloor \frac{x}{4} \rfloor )$

39 Views Asked by At

Question

This question was answered elsewhere, but I found the answer unsatisfying, mostly due to the amount of steps skipped. Maybe I've over complicated things, but just wondering if I'm going about things correctly.

To Prove $\forall x \in \mathbb{R}, \left(\bigg \lfloor \frac{\lfloor \frac{x}{2} \rfloor}{2} \bigg \rfloor = \lfloor \frac{x}{4} \rfloor \right)$

Note: For brevity I've used the following Theorem from the textbook (Epp p. 195) without proof (although it is proven in the text).

Theorem 4.5.2 The Floor of $\frac{n}{2}$:

$$ \bigg \lfloor \frac{n}{2} \bigg \rfloor = \begin{cases} \frac{n}{2} & \quad \text{if } n \text{ is even} \\ \frac{n - 1}{2} & \quad \text{if } n \text{ is odd} \end{cases} $$

Proof. Suppose $x \in \mathbb{R}$. Let $n = \lfloor \frac{x}{2} \rfloor $. Then by definition of floor

$$ n \leq \frac{x}{2} < n + 1. $$

Dividing by 2 we get

$$ \frac{n}{2} \leq \frac{x}{4} < \frac{n}{2} + \frac{1}{2} $$

This means $\lfloor \frac{x}{4} \rfloor = \frac{n}{2}$ by definition of floor. We now consider two cases.

Case 1. $n$ is even. This means $\lfloor \frac{n}{2} \rfloor = \frac{n}{2}$ by Theorem 4.5.2. But we've shown that $\lfloor \frac{x}{4} \rfloor = \frac{n}{2}$. Therefore,

$$\bigg \lfloor \frac{n}{2} \bigg \rfloor = \frac{n}{2} = \bigg \lfloor \frac{x}{4} \bigg \rfloor$$

Since $n = \lfloor \frac{x}{2} \rfloor$, by substitution

$$ \bigg \lfloor \frac{\lfloor \frac{x}{2} \rfloor}{2} \bigg \rfloor = \bigg \lfloor \frac{x}{4} \bigg \rfloor $$

Case 2. $n$ is odd. This means $\lfloor \frac{n}{2} \rfloor = \frac{n - 1}{2}$ by Theorem 4.5.2. Since $n = \lfloor \frac{x}{2} \rfloor$ then by definition of floor

$$ n \leq \frac{x}{2} < n + 1 $$

Dividing by 2,

$$ \frac{n}{2} \leq \frac{x}{4} < \frac{n}{2} + \frac{1}{2} $$

Note that $\frac{n}{2} - \frac{1}{2} \leq \frac{n}{2} < \frac{n}{2} + \frac{1}{2}$. Therefore,

$$ \frac{n}{2} - \frac{1}{2} \leq \frac{n}{2} \leq \frac{x}{4} < \frac{n}{2} + \frac{1}{2} $$

Or by transitivity,

$$ \frac{n}{2} - \frac{1}{2} \leq \frac{x}{4} < \frac{n}{2} + \frac{1}{2} $$

But this means $\lfloor \frac{x}{4} \rfloor = \frac{n}{2} - \frac{1}{2} = \frac{n - 1}{2}$ by definition of floor. Since $\lfloor \frac{n}{2} \rfloor = \frac{n - 1}{2}$ we have

\begin{align*} \bigg \lfloor \frac{x}{4} \bigg \rfloor &= \frac{n - 1}{2} &\\ &= \bigg \lfloor \frac{n}{2} \bigg \rfloor &\\ &= \bigg \lfloor \frac{\lfloor \frac{x}{2} \rfloor}{2} \bigg \rfloor & \text{By substitution of } n = \bigg \lfloor \frac{x}{2} \bigg \rfloor \end{align*}

Since we've exhausted all cases, we've shown $\bigg \lfloor \frac{\lfloor \frac{x}{2} \rfloor}{2} \bigg \rfloor = \lfloor \frac{x}{4} \rfloor$ for all real numbers as was to be shown.