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.)

Might be overkill, but there is a well known identity for sums of the form $\sum_{i=0}^n x^i$ where $x$ is not 1.
$$\sum_{i = 0}^n x^i = \frac{1- x^{n+1}}{1-x}$$
Now plug in 2 and you have what you seek.
This identity can easily be proven by induction.
