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.)
 A: 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$
A: Hint: Consider the sequence of partial sums $(a_n) = 2^0 + \cdots + 2^n$. Add one to each term. Do you notice a pattern?
For example:
$a_0 + 1 = 2^0 + 1 = \dots$
$a_1 + 1 = 2^0 + 2^1 + 1 = \dots$
$a_2 + 1 = 2^0 + 2^1 + 2^2 + 1 = \dots$
Can you guess what a general formula for $a_n + 1$ might be? Then what is $a_n$?
An easy way to prove this would be by induction.
Since you already know $a_n = 2^{n+1} - 1$, the proof by induction goes like this:


*

*Base case: with $n=0$: $a_0 = 2^0 = 1$, which is $2^{0+1}-1$, so the formula holds for the base case.

*Inductive step: if $a_n = 2^{n+1}-1$, then $a_{n+1} = a_n + 2^{n+1}$ (because to get to the next term in the sequence you just add the next power of $2$); by the inductive hypothesis, this is equal to $(2^{n+1}-1) + 2^{n+1} = 2 \times 2^{n+1} - 1 = 2^{(n+1)+1} - 1$, which is the formula we conjectured for $a_{n+1}$.


With this, we've shown $a_n = 2^{n+1}-1$ for all $n \in \mathbb{N}_0$.
A: 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.$
A: 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.
A: Let $S = 2^0 + 2^1 + 2^2 + \cdots + 2^{n}$.
Then $2S = 2^1 + 2^2 + 2^3 + \cdots + 2^{n} + 2^{n+1}$.
Then
$$\begin{align*}
S = 2S - S &=     & & 2^1 &+& 2^2 & + & 2^3 & + & 2^4 &+&\cdots &+& 2^{n} &+& 2^{n+1}\\
&& -2^0 -& 2^1 & - & 2^2 & - & 2^3 & - & 2^4 & - & \cdots & - & 2^n
\end{align*}$$
How much is that?
A: 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.
A: This is called as a Geometric progression. YES there is a formula.
Refer this: http://en.wikipedia.org/wiki/Geometric_progression
The answer for your problem is 2^(n-1).
You want the proof refer the above link. Simple and excellent
