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?
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}$