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?

  • 1
    What is $lb(n)$? Did you mean $\ln(n)$?2012-11-29
  • 0
    lb(n) is log to the base 2 of n2012-11-29
  • 3
    Didn't the lecturer mean $\lfloor lb(n) \rfloor + 1 = \lceil lb(n+1) \rceil$ ?2012-11-29
  • 0
    @DávidKaya, yes, he did. How does that change things?2012-11-30
  • 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
    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.2012-11-29
  • 0
    This is not true, take $n=5$ for example. $\lfloor\log_2 5\rfloor + 1 = 3$, and $\lceil\log_2 6\rceil=3$ also.2012-11-30
  • 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$).