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.

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.
