2
$\begingroup$

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?

  • 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 2

3

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
2

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