2
$\begingroup$

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 !!

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\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.