# How to simplify $2^{\lceil log_2(n) \rceil} - 2^{\lfloor log_2(n) \rfloor}$?

I'm trying to proof: $\lfloor log_2(n) \rfloor + 2^{\lceil log_2(n) \rceil} - 2^{\lfloor log_2(n) \rfloor} ∈ O(log_2(n)) {} {} | n ∈ \mathbb N$

Therefore I need to solve this equaty:

$\lim_{n\to \infty} \frac{\lfloor log_2(n) \rfloor + 2^{\lceil log_2(n) \rceil} - 2^{\lfloor log_2(n) \rfloor}} {log_2(n)} < \infty$

But I didn't come further than

$\lim_{n\to \infty} \frac{\lfloor log_2(n) \rfloor + 2^{\lceil log_2(n) \rceil} - 2^{\lfloor log_2(n) \rfloor}} {log_2(n)} \le \lim_{n\to \infty} \frac{log_2(n) + 2^{\lceil log_2(n) \rceil} - 2^{\lfloor log_2(n) \rfloor}} {log_2(n)}$

Do you know a solution?

• This does not seem right: take $n=1+2^k$. – lhf Nov 8 '16 at 17:03
• @lhf I just realised there is a -1 missing at the end. But that shouldn't make a difference, does it? – oRookie Nov 8 '16 at 17:17

If $\log_2(n)$ is integer, i.e. $n=2^k,\,k\in\mathbb Z_+$ then $$\lceil \log_2(n) \rceil=\lfloor \log_2(n) \rfloor=k$$ Otherwise $$\lceil \log_2(n) \rceil=\lfloor \log_2(n) \rfloor+1\implies 2^{\lceil \log_2(n) \rceil}=2\times2^{\lfloor \log_2(n) \rfloor}$$ In this case, there is $m$ such that $$n=2^k+m,\;2^{k-1}\le m<2^k$$ So it comes to this: $$2^{\lceil \log_2(n) \rceil}-2^{\lfloor \log_2(n) \rfloor}= \begin{cases} 0&n=2^k\\2^{\lfloor \log_2(n) \rfloor}&n=2^k+m \end{cases}$$ and we can see that in the second case, $2^{\lfloor \log_2(n) \rfloor}=2^k$ where $2^k<n<2^{k+1}$

• That's briliant! Thank you! – oRookie Nov 9 '16 at 1:46
• @oRookie you're welcome ;) – polfosol Nov 9 '16 at 4:59