<s>[INST] What is the result of sum $\sum\limits_{i=0}^n 2^i$ 
Possible Duplicate:
the sum of powers of $2$ between $2^0$ and $2^n$ 

What is the result of 
$$2^0 + 2^1 + 2^2 + \cdots + 2^{n-1} + 2^n\ ?$$
Is there a formula on this? and how to prove the formula?
(It is actually to compute the time complexity of a Fibonacci recursive method.)
 [/INST] I thought I might post a little more elaborate version of Henning's hint (see his comment).
$$\begin{align}
  1&=2^0\\
 10&=2^1\\
100&=2^2\\
1000&=2^3\\
\vdots&=\vdots\\
10\dots0&=2^n\\
\hline
11\dots1&=2^0+2^1+\dots+2^n\\
        1&=1\\
\hline
100\dots0&=2^0+2^1+\dots+2^n+1=2^{n+1}
\end{align}$$
Hence $2^0+2^1+\dots+2^n=2^{n+1}-1$
</s>