# What is the result of sum $\sum\limits_{i=0}^n 2^i$ [duplicate]

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

-

8
Yes, there is a formula. Consider what the result looks like in binary notation. What happens if you add 1 to the result (still in binary)? – Henning Makholm Jun 15 '12 at 17:06
You know how a geometric series works? – J. M. Jun 15 '12 at 17:09
$2^{n+1}-1$ is correct. If you need to produce a rigorous proof, I suggest induction. – Henning Makholm Jun 15 '12 at 17:17
@null Isn't the time complexity of a Fibonacci recursive method given in terms of the Fibonacci numbers? – talmid Jun 15 '12 at 17:29

1
I am extremely amused as to why you didn't vote to close yourself @PatrickDaSilva! – Gigili Jun 16 '12 at 0:02
show 6 more comments

## marked as duplicate by user17762, Martin Sleziak, Henning Makholm, Peter Tamaroff, Asaf KaragilaJun 15 '12 at 21:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 7 Answers

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?

-

2
It's at least +1! – Patrick Da Silva Jun 15 '12 at 17:27

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.

-

3
I wouldn't call this "overkill", but rather "standard approach". The proof of this identity is essentially the standard approach when one tries to prove this identity for $x = 2$. – Patrick Da Silva Jun 15 '12 at 17:32
Where is that from? I 'invented' it in high school, and could never find a source... – Alex Feinman Jun 15 '12 at 18:26
This is usually an standard exercise in your first `proof' course at the university. – Dimitri Surinx Jun 15 '12 at 19:30

I thought I might post a little more elaborate version of Hennig's hint (see his cooment). $$\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$

-

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

-

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

-

1
It's at least worth +1! – Patrick Da Silva Jun 15 '12 at 20:55

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.

-
I mean, seriously? A kangaroo? Gosh. $2^8$ feet leaps? Man... +1 for the laugh – Patrick Da Silva Jun 15 '12 at 17:34

1
@PatrickDaSilva: Yes, seriously. Someone reading it with attention may be able to reconstruct the idea a year from now. – André Nicolas Jun 15 '12 at 17:39

1
@AndréNicolas "A Hulk is $2^9$ feet from her beloved..." would be more interesting. +1 – Peter Tamaroff Jun 15 '12 at 18:40
@AndreNicolas : You seem to like this pedagogic approach a lot. I respect you for that =) sometimes people forget that you need to do mathematics to have fun! When there's no fun, there's no theorem. – Patrick Da Silva Jun 15 '12 at 20:54

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

-
Its 2^(n+1)....my bad. – george Jun 15 '12 at 21:03

1
Note that the sum has exactly one odd number and therefore the sum cannot be an odd number. So your answers $2^{n-1},2^{n+1}$ are wrong. – Asaf Karagila Jun 15 '12 at 21:07
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 61, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.938536524772644, "perplexity_flag": "middle"}