big O notation - explain the equality

Question

$$\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.

Be glad for help.

Answer 1

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.

To keep in mind:

• 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$