# Prove $\lfloor \log_2(n) \rfloor + 1 = \lceil \log_2(n+1) \rceil$

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?

-
What is $lb(n)$? Did you mean $\ln(n)$? – Joe Johnson 126 Nov 29 '12 at 11:10
lb(n) is log to the base 2 of n – Irwin Nov 29 '12 at 11:17
Didn't the lecturer mean $\lfloor lb(n) \rfloor + 1 = \lceil lb(n+1) \rceil$ ? – Noturab Nov 29 '12 at 11:28
@DávidKaya, yes, he did. How does that change things? – Irwin Nov 30 '12 at 0:59
@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. – Noturab Nov 30 '12 at 9:22

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.

-
Answers, and questions, written without LaTeX look pretty ugly and sometimes are even almost impossible to understand. You can try the FAQ section where you'll get directions how to properly write mathematics in this site. – DonAntonio Nov 29 '12 at 11:59
This is not true, take $n=5$ for example. $\lfloor\log_2 5\rfloor + 1 = 3$, and $\lceil\log_2 6\rceil=3$ also. – Ricbit Nov 30 '12 at 10:25
@Ricbit, The question was changed after I replied. I answered the question for lb(n)+1 = lb(n+1), no floor or ceil. – Dirk Dinther Nov 30 '12 at 10:50

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$).

-