Inequality for integers with floor function

Question

I want to show that for any nonnegative integers $l$ and $b$ we have $$ \frac{l}{2^{b+1}} - 1 \leq \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor. $$

I have a proof where I wrote $l = \alpha\cdot 2^{b+1} + \beta$ with $0\leq \beta\leq 2^{b+1}$, but it's not very elegant, I say.

Let $l = \alpha\cdot 2^{b+1} + \beta$ with $0\leq \beta\leq 2^{b+1}.$ Then we have (LHS): $$ \frac{l}{2^{b+1}}-1 = \alpha + \frac{\beta}{2^{b+1}}-1 $$ and (RHS): $$ \left\lfloor \frac{l-1}{2^{b+1}}\right\rfloor = \left\lfloor \alpha + \frac{\beta-1}{2^{b+1}}\right\rfloor. $$

In case $\beta = 0$ we get $\alpha - 1$ for (LHS) and due to $0<2^{-(b+1)}<1$ we get the same for (RHS), so we have equality for this case.

Otherwise, we have $1\leq \beta \leq 2^{b+1}$ and so $0 \leq \frac{\beta - 1}{2^{b+1}} < \frac{\beta}{2^{b+1}}<1$. So we have for (LHS) $$ \frac{l}{2^{b+1}}-1 = \alpha + \frac{\beta}{2^{b+1}}-1<\alpha $$ and for (RHS) $$ \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor = \left\lfloor \alpha + \frac{\beta-1}{2^{b+1}} \right\rfloor = \alpha.\square $$

Is there a more elegant way of showing this?

Answer 1

This is a one-liner if you use the fact that $\lfloor x+a \rfloor = \lfloor x\rfloor +a$ for $x \in \Bbb R$ and $a \in \Bbb Z$. Then the inequality is equivalent to $$\frac{l}{2^{b+1}} \le \left \lfloor \frac{l+2^{b+1} - 1}{2^{b+1}} \right \rfloor$$ which is trivially true. To see why, pull out and cancel the quotient of $l \div 2^{b+1}$. If $l \equiv 0 \pmod{2^{b+1}}$, then equality holds, otherwise the RHS (after cancelling) would be at least one, but the LHS would be less than one.

---

Actually, the above proof is equivalent to your approach, so here's another which uses the fact that $x-1<\lfloor x \rfloor$: $$\frac{l-1}{2^{b+1}} - 1 < \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor$$ Now, suppose you add $\frac{1}{2^{b+1}}$ to the LHS. Can the inequality be reversed? No, if $l \equiv 1 \pmod{2^{b+1}}$ then the LHS and RHS differ by 1, so adding won't change anything. Otherwise, the LHS is not an integer, and adding $\frac{1}{2^{b+1}}$ can make it equal to an integer (the RHS), but not greater. Hence, $$\frac{l}{2^{b+1}} - 1 \le \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor$$

Answer 2

Case 1

When $l=0$, in RHS we have

$$ \left\lfloor \frac{-1}{2^{b+1}} \right\rfloor = -1 $$

In LHS we will have $-1$, hence both sides will be equal

Case 2

When $l \geq 1$

Assume

$$ \frac{l}{2^{b+1}} - 1 \gt \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor $$

$$ \frac{l}{2^{b+1}} - \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor \gt 1 $$

$$ \frac{l-1}{2^{b+1}} - \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor + \frac{1}{2^{b+1}} \gt 1 $$

$$ \left\{ \frac{l-1}{2^{b+1}} \right\} + \frac{1}{2^{b+1}} \gt 1 $$

Where $\{a\}$ is fractional part of $a$, $0 \leq \{a\} \lt 1$

Using Euclid's division algorithm we can find $q$ and $r$ such that

$$(2^{b+1})q + r = l-1$$

Where $0 \leq r \leq 2^{b+1} - 1$ and $q \in \mathbb{Z}$

$$q + \frac{r}{2^{b+1}} = \frac{l-1}{2^{b+1}}$$ $$\left\{ q + \frac{r}{2^{b+1}} \right\} = \left\{ \frac{l-1}{2^{b+1}} \right\} $$

As per restrictions on $q$ and $r$, we have $$\left\{ q + \frac{r}{2^{b+1}} \right\} = \frac{r}{2^{b+1}}$$

Putting it in an earlier equation we get

$$ \frac{r}{2^{b+1}} + \frac{1}{2^{b+1}} \gt 1 $$ $$ \frac{r+1}{2^{b+1}} \gt 1 $$

But we have $0 \leq r \leq 2^{b+1} - 1$, so we know that $$\frac{r+1}{2^{b+1}} \leq 1$$

We reach a contradiction! Hence our initial assumption must be incorrect and we get that

$$ \frac{l}{2^{b+1}} - 1 \leq \left\lfloor \frac{l-1}{2^{b+1}} \right\rfloor $$

For all non-negative values of $l \geq 1$ and $b$

Answer

In case $1$ we proved the inequality to be true for $l=0$

In case $2$ we proved the inequality to be true for $l \geq 1$

Hence the inequality holds for all non-negative $l$ and $b$