# big O notation - explain the equality

$$\sum\limits_{i = 1}^{\log n} {\sqrt {{2^i}} } = O(n)$$

OK, So I understand the equality, but I don't know how to prove it.
For my understanding, I need to show that the left side is $\le$ the right side multiplied by a constant. Is that right? Anyhow, I didn't figure it out to the end.

Use the upper bound $$\sum_{i=1}^k\sqrt{2^i}=\sum_{i=1}^kr^i\leqslant r^k\sum_{i\geqslant0}r^{-i}=\frac{r^k}{1-r^{-1}}$$ for $r=\sqrt2$ and $k=\log n$, then $r^k=\exp(k\cdot\log r)=\exp(\log n\cdot\log r)=n^{\log r}$ hence the proof is complete if $\log r\leqslant1$, that is, if $r\leqslant\mathrm e$. Now, $\sqrt2\lt2\lt\mathrm e$, QED.
• Sum of geometric series $\sum\limits_{i\geqslant0}x^i=\frac1{1-x}$ for $|x|\lt1$
• Identity $a^{\log n}=n^{\log a}$ for $a\gt0$
• Which one?   – Did Dec 9 '13 at 19:31
• And one more thing, is it summing from i=0 to $\infty$? – Daniel Gagnon Dec 9 '13 at 19:34
• Every entry in the finite sum on the left of $\leqslant$ appears in the infinite sum on the right of $\leqslant$, with some more. – Did Dec 9 '13 at 19:38