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

Let us take a particular example that is large enough to illustrate the general situation. Concrete experience should precede the abstract.   
Let $n=8$. We want to show that $2^0+2^1+2^2+\cdots +2^8=2^9-1$.  We could add up on a calculator, and verify that the result holds for $n=8$. However, we would not learn much during the process.  
We will instead look at the sum written backwards, so at
$$2^8+2^7+2^6+2^5+2^4+2^3+2^2+2^1+2^0.$$
A kangaroo is $2^9$ feet from her beloved $B$. She takes a giant leap of $2^8$ feet. Now she is $2^8$ feet from $B$.  She takes a leap of $2^7$ feet. Now she is $2^7$ feet from $B$. She takes a leap of $2^6$ feet. And so on. After a while she is $2^1$ feet from $B$, and takes a leap of $2^0$ feet, leaving her $2^0$ feet from $B$.
The total distance she has covered is $2^8+2^7+2^6+\cdots+2^0$.  It leaves her $2^0$ feet from $B$, and therefore 
$$2^8+2^7+2^6+\cdots+2^0+2^0=2^9.$$
Since $2^0=1$, we obtain by subtraction that $2^8+2^7+\cdots +2^0=2^9-1$.
We can write out the same reasoning without the kangaroo.  Note that 
$2^0+2^0=2^1$, $2^1+2^1=2^2$, $2^2+2^2=2^3$, and so on until $2^8+2^8=2^9$.
Therefore
$$(2^0+2^0)+2^1+2^2+2^3+2^4+\cdots +2^8=2^9.$$
Subtract the front $2^0$ from the left side, and $2^0$, which is $1$, from the right side, and we get our result.
