Prove that the binary representation of a number n will use floor(lg(n)) + 1 bits. 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.
 A: 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$$
A: Hint: For which numbers $n$ is $\lg n$ an integer?
A: Hint
Note that the binary representation of $2^n$ has $n+1$ bits.
Find then that the binary representation of a sum of $2^{k_i}$ with distinct $k_i$ has $\max_i k_i + 1$ bits.
Finally conclude that any integer in the interval $[2^n, 2^{n+1})$ has a binary representation of exactly $n+1$ bits.
