1
$\begingroup$

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

|cite|improve this question
$\endgroup$
2
$\begingroup$

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$
|cite|improve this answer
$\endgroup$
  • $\begingroup$ hmm.. can you please explain the inequality? $\endgroup$ – Daniel Gagnon Dec 9 '13 at 19:31
  • $\begingroup$ Which one? $ $ $ $ $\endgroup$ – Did Dec 9 '13 at 19:31
  • $\begingroup$ in the first line. $\endgroup$ – Daniel Gagnon Dec 9 '13 at 19:33
  • $\begingroup$ And one more thing, is it summing from i=0 to $\infty$? $\endgroup$ – Daniel Gagnon Dec 9 '13 at 19:34
  • 1
    $\begingroup$ Every entry in the finite sum on the left of $\leqslant$ appears in the infinite sum on the right of $\leqslant$, with some more. $\endgroup$ – Did Dec 9 '13 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.