Approximate value for $\sum_{i=1}^n 2^{\lceil \log_2i\rceil}$.

Question

What will be the closest approximate value for:

$$\sum_{i=1}^n 2^{\lceil \log_2i\rceil}$$

One method is replacing $\lceil{\log_2i\rceil}$ with $\log_2i+1$. But is there any method to get the closest approximate value?

Answer 1

Let $m = \lfloor \log_2 n \rfloor$. \begin{align*} \sum_{i=1}^{n} 2^{\lceil \log_2 i\rceil} &= \overbrace{1 + 2 + 4 + 4 + \underbrace{8 + \cdots + 8}_{4} + \underbrace{16 + \cdots + 16}_8 + \cdots}^{n} \\ &= 1 + (n - 2^m)2^{m+1}+\sum_{k=1}^{m}2^{k-1}2^{k}\\ &= 1 + (n - 2^m)2^{m+1} + \frac{2}{3}(4^m-1) \end{align*}