# Find $\sum_{i=0}^{\log n} \frac{1}{2^i}$

I'm not really sure how to solve summations, so any help would be great. In particular, I had thought that $n^2\sum_{i=0}^{\log n} \frac{1}{2^i}=O(n^2\log n)$ but it's actually $O(n^2)$, and I'm trying to make sure that I don't make that mistake again. Are there any resources that can help me solve other common summations using pen-and-paper?

Other summations (I don't have to solve these, but they're typical of what I would encounter):

$\sum_{i=1}^{ n} i$

$\sum_{i=1}^{\log n} 3^i$

$\sum_{i=0}^{n} 1.01^{-1}$

• Note that $\sum_{i\ge 0}\frac1{2^i}=2$, so $n^2\le n^2\sum_{i=0}^{\log n}\frac1{2^i}\le 2n^2$, giving you $O(n^2)$ without actually computing the finite sum. – Brian M. Scott Oct 23 '14 at 1:46

## 1 Answer

Well, if $f(n)=O(n^2)$ then $f(n)=O(n^2\log n)$ by definition, so you aren't wrong, there is just a better bound.

The trick is knowing that $\sum_{i=0}^\infty \frac{1}{2^i}=2$. So $\sum_{i=0}^{\log n} \frac{1}{2^j} = O(1)$.

• Sorry, that's what I meant. I was trying to find the tightest bound. – Ashley Oct 23 '14 at 1:49