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

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?

• I think it should be $\log_2(i)$ instead of $\log_2(n)$ in the summation. – Math Lover Jan 15 '19 at 18:50
• This doesn't look too hard to compute exactly, since you have a bunch of consecutive terms that are the same. – Michael Lugo Jan 15 '19 at 19:06
• Can we deduce any expression that gives the closest approximate value for any given n – Sail Akhil Jan 15 '19 at 19:11

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*}