How to prove $\lceil \log_2{(n+1)} - 1 \rceil \ge \lfloor \log_2(n) \rfloor$?

Question

Suppose $n$ is a positive integer. How can one show that $\lceil \log_2{(n+1)} - 1 \rceil \ge \lfloor \log_2(n) \rfloor$ ?

Answer 1

First, you have $$\log_2(n+1) > \log_2(n)$$ because $\log_2$ is increasing.

So obviously, $$\lceil \log_2(n+1) \rceil > \log_2(n)$$

You deduce that $\lceil \log_2(n+1) \rceil$ is an integer (strictly) greater to $\log_2(n)$, so it is greater (or equal) to $\lfloor \log_2(n) \rfloor +1$, i.e. $$\lceil \log_2(n+1) \rceil \geq \lfloor \log_2(n) \rfloor +1$$

You get $$\lceil \log_2(n+1) \rceil -1 \geq \lfloor \log_2(n) \rfloor $$

hence $$\lceil \log_2(n+1) -1\rceil \geq \lfloor \log_2(n) \rfloor $$