# Why is the following about logarithms true?

I was reading some algorithm's analysis and I came across the following in the proof:

$\log_2(n+1) \le h \le 1 + \log_2(n) \implies h = \lceil \log_2(n+1)\rceil$

Here both $h$ and $n$ are integral. Why is the above true ?

-
Should the logarithm on the right be logarithm base 2? – Arturo Magidin Oct 28 '11 at 17:15
yes ! thanks for noticing – AnkurVijay Oct 28 '11 at 17:19
Hint: $log_2(n)<log_2(n+1)$ So $log_2(n)<h\leq 1+log_2(n)$. How many different integers $h$ can be in the range $(x,x+1]$ for any real number $x$? And is $\lceil \log_2(n+1)\rceil$ in that range when $x=log_2(n)$? – Thomas Andrews Oct 28 '11 at 17:32
@Thomas thanks, got it. If you put the hint as an answer, Ill accept it. – AnkurVijay Oct 28 '11 at 17:35

The ceiling function $\lceil x\rceil$ can be defined as the unique integer in the interval $[x,x+1)$.
But $1+\log_2(n)< 1+\log_2(n+1)$, so $h$ is an integer in the interval $[\log_2(n+1),1+\log_2(n+1))$. That means that $h=\lceil \log_2(n+1)\rceil$.