Log inequality - is $\lceil\log x\rceil - \lfloor\log y\rfloor\leq \lceil\log\frac{x}{y}\rceil+1$

Question

Is it true that $$\forall x>y\in\mathbb N:\lceil\log_2 x\rceil - \left\lfloor\log_2 y\right\rfloor\leq \left\lceil\log_2\frac{x}{y}\right\rceil+1$$?

I reached this inequality when further analyzing the expression I got in this question (I keep a set of counters that each has a potentially different size).

Thanks !!

Answer 1

Set $a=\lceil \log_2 x\rceil$ and $b=\lfloor \log_2 y\rfloor$. We have $2^{a-1}<x\le2^a$ and $2^b\le y<2^{b+1}$. Dividing, we get $$2^{(a-1)-(b+1)}<\frac{x}{y}\le 2^{a-b}$$ Hence $$\log_2\left(\frac{x}{y}\right)\in (a-b-2,a-b]$$ and $$\lceil \log_2\left(\frac{x}{y}\right)\rceil\in \{a-b-1,a-b\}$$

Now, your desired inequality is $$a-b\le \lceil \log_2\left(\frac{x}{y}\right)\rceil+1$$ which holds for either $a-b-1$ or $a-b$, as desired.

Answer 2

$$\lceil\log_2 x\rceil - \left\lfloor\log_2 y\right\rfloor\leq \left\lceil\log_2\frac{x}{y}\right\rceil+1\\ \lceil\log_2 x\rceil - \left\lfloor\log_2 y\right\rfloor\leq \left\lceil\log_2{x}-\log_2{y}\right\rceil+1$$

So, letting $\{a\}$ denote the fractional part of any $a$ and $A=\log_2 x,B=\log_2 y$

$$\lceil A\rceil - \left\lfloor B\right\rfloor\leq \left\lceil A-B\right\rceil+1\\ \lceil \lfloor A\rfloor+\{A\}\rceil - \lfloor B\rfloor\leq \lceil \lfloor A\rfloor+\{A\}-\lfloor B\rfloor-\{B\}\rceil+1\\ \lfloor A\rfloor+\lceil\{A\}\rceil - \lfloor B\rfloor\leq \lfloor A\rfloor-\lfloor B\rfloor+\lceil\{A\}-\{B\}\rceil+1\\ \lceil\{A\}\rceil\leq \lceil\{A\}-\{B\}\rceil+1\\$$

It becomes quite clear that the inequality is true. The left hand side is either $0$ or $1$, and the right hand side is either $1$ or $2$.