Why is $2^{n}-1=\sum\limits_{k=0}^{n-1}2^k$?

Question

Recently I discovered that $2^{n}-1=\sum\limits_{k=0}^{n-1} 2^k$. As I don't have a math background, please tell me what this is called and a proof of why this is the case.

Answer 1

This is called a geometric series. One way to prove the formula is mathematical induction.

First we check the formula (corrected the left side with $-1)$ for $n=1$: indeed, $2^1-1=2^0.$

Now we assume it's true for $n=m$ (i.e., $2^m-1=\sum\limits_{k=0}^{m-1}2^k$),

and we show it's then true for $n=m+1$:

$2^{m+1}-1=2^m+2^m-1=2^m+\sum\limits_{k=0}^{m-1}2^k=\sum\limits_{k=0}^{m}2^k.$

Therefore, it's true for $n=1, n=1+1=2, n=2+1=3, n=3+1=4, \dots$

Answer 2

As Hayden has pointed out, the correct expression is $2^n-1=\sum_{k=0}^{n-1} 2^k.$

So to see this, let’s first name the sum $S:=1+2^1+\dots+2^{n-2}+2^{n-1}.$

The ‘trick’ is to multiply the sum by $1$ in a clever way such that we can cancel some terms. Since $2=2-1$, we can say this:

$$ S=1+2^1+\dots+2^{n-2}+2^{n-1}\\ \implies\\ 1\times S = \left(2-1\right)\times \left(1+2^1+\dots+2^{n-2}+2^{n-1}\right)\\ S=2\times\left(1+2^1+\dots+2^{n-2}+2^{n-1}\right)\\ -1\times\left(1+2^1+\dots+2^{n-2}+2^{n-1}\right)\\ = \left(2^1+2^2+\dots+2^{n-1}+2^{n}\right)\\ -\left(1+2^1+\dots+2^{n-2}+2^{n-1}\right)\\ = 2^n-1. $$

Hope this helps! Stay safe

Answer 3

For all positive integer $n$ :$$\begin{align}2^n&=\sum_{k=0}^{n}2^k-\sum_{k=0}^{n-1}2^k&&=(1+2+\cdots+2^{n-1}+2^n)-(1+2+\cdots+2^{n-1})\\[1ex]&=1+\sum_{k=1}^{n}2^k-\sum_{k=0}^{n-1}2^k&&=1+(2+\cdots+2^{n-1}+2^n)-(1+2+\cdots+2^{n-1})\\[1ex]&=1+2\sum_{k=1}^n2^{k-1}-\sum_{k=0}^{n-1}2^k&&=1+2(1+2+\cdots+2^{n-1})-(1+2+\cdots+2^{n-1})\\[1ex]&=1+2\sum_{k=0}^{n-1}2^k-\sum_{k=0}^{n-1}2^k\\[1ex]&=1+\sum_{k=0}^{n-1}2^k&&=1+(1+2+\cdots+2^{n-1})\\[3ex]\therefore\quad\sum_{k=0}^{n-1}2^k&=2^n-1\end{align}$$

Answer 4

It isn't.

$2^n - 1 = \sum_{k=0}^{n-1} 2^k$ or equivalently $2^n = 1 + \sum_{k=0}^{n-1} 2^k$.

The offset of $1$ is important and unavoidable.

As for why, I STRONGLY suggest you play around with it on your own until you make up your own "aha" moment that works for you.

Trust me... you will have one.

.... but .... this one was mine:

$2^n = 2*2^{n-1} =$

$2^{n-1} + 2^{n-1} = $

$2^{n-1} + 2*2^{n-2} =$

$2^{n-1} + 2^{n-2} + 2^{n-2} =$

$2^{n-1} + 2^{n-2} + 2*2^{n-3} = $

$2^{n-1} + 2^{n-2} + 2^{n-3} + 2^{n-3} =$

........

$2^{n-1} + 2^{n-2} + 2^{n-3} +..... + 8 + 4 + 2 + 2=$

$2^{n-1} + 2^{n-2} + 2^{n-3} +..... + 8 + 4 + 2 +1+1=$

$(2^{n-1} + 2^{n-2} + 2^{n-3} +..... + 8 + 4 + 2 +1)+1=$

$(\sum_{k=0}^{n-1} 2^k) + 1$.

That was my "aha" moment...

Ohter people have this one:

$1 + (1 + 2 + 4 + 8 + 16 + ......... + 2^{n-1}) = $

$(1 + 1) + (2 + 4 + 8 + 16 + ........ + 2^{n-1}) =$

$2 + (2 + 4 + 8 + 16 + ....... + 2^{n-1})=$

$(2 + 2) + (4 + 8 + 16 + ....... + 2^{n-1}) =$

$4 + (4 + 8 + 16 + ...... +2^{n-1}) = $

$(4+4) + (8 + 16 + ...... + 2^{n-1}) =$

$8 + (8 + 16 + ..... + 2^{n-1}) = $

$(8+8) + (16 + ...... + 2^{n-1}) =$

$16 + (16 + ... + 2^{n-1})=$

$(16 + 16) + (..... + 2^{n-1}) = $

$32 + (.... + 2^{n-1})=$.

.... now clearly we can do this indefinately as each step is just ....

$2^k + (2^k + 2^{k+1} + .....) = $

$(2^k +2^k) + (2^{k+1} + ..... ) = $

$2*2^k + (2^{k+1} + ....) =$

$2^{k+1} + (2^{k+1} + ...) =$.

and it is "so clear it is obvious to anyone but a complete dope" that we just adding up two copies of a power of two... which is two times the power of two .... which is two the the next power of two.... which we then combine with the next....

So we just do that until we get to the end....

$2^{n-3} + (2^{n-3} + 2^{n-2} + 2^{n-1})=$

$(2^{n-3} + 2^{n-3}) + (2^{n-2} + 2^{n-1})=$

$2*2^{n-3} + (2^{n-2} + 2^{n-1})=$

$2^{n-2} + (2^{n-2} + 2^{n-1})=$

$(2^{n-2} + 2^{n-2}) + 2^{n-1}=$

$2*2^{n-2} + 2^{n-1} =$

$2^{n-1} + 2^{n-1} =$

$2*2^{n-1} =$

$2^n$.

So ........

$1 + \sum_{k=0}^{n-1} 2^k = 2^n$.

That's my aha way of looking at it.

....

And there are others.

find yours

.....

A common but subtle idea is $(2^{n-1} + 2^{n-2} + ...... + 2 + 1)=$

$1 \cdot (2^{n-1} + 2^{n-2} + ...... + 2 + 1)=$

$(2-1)(2^{n-1} + 2^{n-2} + ...... + 2 + 1)=$

$(2^n + 2^{n-1} + ..... + 4 + 2) -(2^{n-1} + 2^{n-2} + ...... + 2 + 1)=$

$2^n + (2^{n-1} + ..... + 4 + 2) - (2^{n-1} + ..... + 4 + 2) - 1=$

$2^n -1$

That works for some...

Answer 5

This is an observation I made myself as a kid and I proved a version of the formula. It's quite easy to do. This is called a geometric series. You start with a first term, then the rule is that the next term is obtained by multiplying the previous term by a fixed constant. The individual terms are called a geometric "sequence", but the sum of all the terms from first to last (in a finite list of terms) is called a geometric series.

The formula is easy to prove. The usual notation for the constant number you multiply each term by is $r$, denoting the "common ratio".

Let's say we have the series: $S(n) = 1 + r + r^2 + r^3 + ...+ r^{n-2} + r^{n-1}$. (series 1)

Note that the argument on the left is $n$ because you're summing $n$ terms on the right.

Now, let's multiply every individual term in the series by $r$. Note that this has the effect of multiplying the entire series by $r$.

$rS(n) = r + r^2 + r^3 + ... r^{n-1} + r^{n}$. (series $2$)

What happens if you take the old series and subtract it from the new one (series $2$ - series $1$)? Note that only the first term in the series $1$ and the last term in series $2$ are "unmatched" and will therefore "survive". All the middle terms vanish.

So you're left with: $rS(n) - S(n)= r^n - 1$

Rearrange that to: $S(n) = \frac{r^n-1}{r-1}$, and you've got your geometric series sum formula. If you put $r = 2$ into that formula, you will reproduce your original observation (with the small correction that others have mentioned), but of course, this is applicable to all $r$.

Note that in the usual statement of the formula, they assume the first term to be $a$ rather than $1$ as I stipulated above. This simply has the effect of mutiplying the entire series by $a$, so the formula is most often stated in texts as $S(n) = \frac{a(r^n-1)}{r-1}$. Not that relevant to your specific question here, but I thought you should know, in order to avoid confusion in the future.

Answer 6

Well, here is a simple proof using telescopic sums :

Let $ n $ be a positive integer, we have the following : $$ \sum_{k=0}^{n-1}{2^{k}}=\sum_{k=0}^{n-1}{2^{k}\left(2-1\right)}=\sum_{k=0}^{n-1}{\left(2^{k+1}-2^{k}\right)}=2^{n}-1 $$

Answer 7

Has anyone ever seen this proof anywhere? ( Different to geometric series proof)

in base 2: $$\underbrace{11\cdots 11}_{n\text{}} = \sum_{k=0}^{n-1} 2^k$$ the next number after $\underbrace{11\cdots 11}_{n\text{}} $ is ${1\underbrace{0\cdots 0}_{n\text{}}} = 2^n$

so $\underbrace{11\cdots 11}_{n\text{}} +1 = 2^n$

or

$\underbrace{11\cdots 11}_{n\text{}} = 2^n -1$

$$\sum_{k=0}^{n-1} 2^k = 2^n -1$$

so in base $x$ we get

$$\sum_{k=0}^{n-1} x^k = x^n -1$$

with the additional benefit of having defined the next number in any base (integer, complex, matrix etc. )