<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] How much is a direct summation worth?
$$\begin{align*}
1 + \sum_{i=0}^n 2^i &= 1 + (2^0 + 2^1 + 2^2 + \cdots + 2^n)\\
&= (2^0 + 2^0) + (2^1 + 2^2 + \cdots + 2^n)\\
&= 2^1 + (2^1 + 2^2 + \cdots + 2^n)\\
&= (2^1 + 2^1) + (2^2 + \cdots + 2^n)\\
&= 2^2 + (2^2 + \cdots + 2^n)\\
\vdots &= \ddots\\
&= 2^n + (2^n)\\
&= 2^{n+1}.
\end{align*}$$
Hence, $\displaystyle \sum_{i=0}^n 2^i = 2^{n+1} - 1.$
</s>