This is a question a lecturer gave me. I'm more than willing to come up with the answer. But I feel I'm missing something in logs. I know the rules, $\log(ab) = \log(a) + \log(b)$ but that's all I have. What should I read, look up to come up with the answer?
Prove $\lfloor \log_2(n) \rfloor + 1 = \lceil \log_2(n+1) \rceil $
-
0@Irwin $\lfloor$ $\rfloor$ - these round a real number down to the next integer and $\lceil$ $\rceil$ - round a real number up to the next integer. With these symbols your equation can be proved. – 2012-11-30
2 Answers
EDIT: This answer is for the original question, before it was changed by the OP by adding ceil and floor.
I suppose $\operatorname{lb}()$ is the binary logarithm. Then this equation is not a general identity, so you cannot "prove" it. However you can solve for $n$ so that it is true.
$\operatorname{lb}(n)+1 = \operatorname{lb}(n+1) \Rightarrow 2^{(\operatorname{lb}(n)+1)} = 2^{\operatorname{lb}(n+1)} \Rightarrow 2^{\operatorname{lb}(n)} \cdot 2^1 = 2^{\operatorname{lb}(n+1)}$
$\Rightarrow n \cdot 2 = n + 1$
So $n = 1$ is a possible answer. Plugging it into the initial equation shows it really solves it. It's also the only solution.
-
1@Ricbit, The question was changed after I replied. I answered the question for lb(n)+1 = lb(n+1), no floor or ceil. – 2012-11-30
Well, even after your edit, this is not an identity in general. It is valid only for integral $n$. For a counter-example of why this is not valid for a positive $n$, take $n = 1.5$. Then,
$\lfloor \log_2(n) \rfloor + 1 = \lfloor \log_2(1.5) \rfloor + 1 = 1$
and
$\lceil \log_2(n + 1) \rceil = \lceil \log_2(2.5) \rceil = 2$
However, for $n \in \mathbb N$ and $n > 0$, this identity holds, and can be proven as follows:
Let $2^k \le n < 2^{k+1}$ for some $k \ge 0$ and $k$ is an integer.
Therefore, let $n = 2^k + m$, where $k \ge 0$ and $0 \le m < 2^{k}$, and $k, m$ are positive integers.
Then,
$\lfloor \log_2(n) \rfloor + 1 = \lfloor \log_2(2^k + m) \rfloor + 1 = k + 1$
Notice that $\log_2(2^k + m) = k$ when $m = 0$. Otherwise, $k < \log_2(2^k + m) < k+1$, and hence the above result.
Also,
$\lceil \log_2(n + 1) \rceil = \lceil \log_2(2^k + m + 1) \rceil = k + 1$
This last equation is clear for $m < 2^k -1$, where $2^k + m + 1 < 2^{k+1}$. When $m=2^k-1$, notice that $\log_2(2^k+2^k-1+1) = \log_2(2^{k+1})$ is an integer, and therefore $\lceil k+1\rceil=k+1$.
Hence, this identity is valid only for positive integers ($n \in \mathbb N$).