I'm taking Computer Algorithms class and one of my problems is from Skiena's Algorithm Design Manual, 2-41:
Prove that the binary representation of $n \ge 1$ has $\lfloor \lg n \rfloor +1$ bits ($\lg$ is base 2)
Some base cases:
$n = 1, \lfloor \lg 1 \rfloor + 1 = 1$
$n = 2, \lfloor \lg 2 \rfloor + 1 = 2$
$n = 5, \lfloor \lg 5 \rfloor + 1 = 3$
$n = 15, \lfloor \lg 15 \rfloor + 1 = 4$
I don't know where to go from there though. Any help appreciated.
Best Answer
Let $n \in \mathbb{N}$, suppose $n$ requires $d$ digits in it's base 2 representation, we'd like to show that $d = \lfloor \log_2(n) \rfloor+1$.
At most we have $n = 1 \ldots 1$, that is $d$ 1's in a row. But we know that is $$\sum_{i=0}^{d-1} 2^i = 2^d - 1$$
At a minimum the first digit is a 1 and the rest are zeros (since the powers start at 0 right to left, this is $2^{d - 1}$).
We now have the following bound on $n$. $$2^{d-1 } \le n \le 2^d - 1$$
Taking log base 2 on on the above inequality yields: (Call this inequality $\beta$) $$d - 1 \le \log_2 (n) \le \log_2(2^d -1 )$$
Note: Taking the log respects the inequalities because $\log_2(\cdot)$ is a strictly increasing function (check it's derivative)
We will attempt to take the floor of $\beta$. Since $d-1$ is an integer $\lfloor d-1 \rfloor = d-1$, as for $\log_2(2^d-1)$, we must look a little closer. Since $2^{d-1} \le 2^d - 1 < 2^d$ and , we know that $$d-1 = \log_2(2^{d-1}) \le \log_2(2^d - 1) < log_2(2^d) = d $$
Therefore $\lfloor \log_2(2^d - 1) \rfloor = d-1$ and so the result of taking the floor of $\beta$ yields
$$d - 1 \le \lfloor \log_2 (n) \rfloor \le \lfloor \log_2(2^d -1 ) \rfloor = d-1$$
In other words
$$d - 1 \le \lfloor \log_2 (n) \rfloor \le d-1$$
So $$d - 1 = \lfloor \log_2 (n) \rfloor \Leftrightarrow d = \lfloor \log_2 (n) \rfloor + 1$$