# How to prove that $2^{n-1}=1+1+2+4+\dotsb+2^{n-2}$ for $n>1$?

This is a claim in a textbook that I'm using, although it was not proven.

When trying this for small $$n$$'s it is clear.

\begin{align} 2^2&=1+1+2^1=4\\ 2^3&=1+1+2+2^2\\ 2^4&=1+1+2+4+2^3 \end{align}

What I was thinking for the proof was $$2^{n-1}=2(2^{n-2})=2^{n-2}+2^{n-2}$$, but obviously that's not incorporating addition, so I don't know where to go on. Is it just expressing $$2^{n-2}$$ as the first summation?

• Have you tried induction? – Don Thousand Jan 19 at 0:56
• Just wondering: Why use $n-1$ and $n-2$ instead of $n$ and $n-1$? – David G. Stork Jan 19 at 1:37

It's because it's a geometric progression. Since

$$1+p_i+{p_i}^2+··· +{p_i}^{a_i} = \dfrac{{p_i}^{a_i+1}-1}{p_i-1}.$$

you just add an extra one at the start of the progression.

In binary, this is

$$1+1+10+100+...+1\underbrace{00...00}_{n-2\text{ times}}=1+\underbrace{11...11}_{n-1\text{ times}}=1\underbrace{00...00}_{n-1\text{ times}}$$

which in decimal is $$2^{n-1}$$.

What you suggest basically seems to work - I'm going to change the leading value into $$n$$ rather than $$n-1$$ for ease of reading:

First, $$2^1 = 1+1$$ and $$2^2 = 1+1+2 = 1+2^0+2^1$$

Then using induction, assuming that the summation holds for lower $$n$$, we can use your observation $$2^n = 2^{n-1} + 2^{n-1}$$ and change the first $$2^{n-1}$$ into the summation form, giving $$2^{n} = 1+1 + 2 + \cdots + 2^{n-2} + 2^{n-1}$$ as required.

• Note that this answer is attempting to build on the OP's apparent attempt to use induction. – Joffan 2 days ago

Let me suggest 4 ways:

1. $$a^{n}-b^{n}=(a-b)(a^{n-1} + ba^{n-2}+ ... + b^{n-1}) \Rightarrow 2^{n} = 2^{n} - 1 + 1 = 1+2+ ... +2^{n-1} +1$$

2. Considering all subsets from set with $$n>1$$ elements and considering map between subsets and binary numbers

3. Mathematical Induction

4. Newton's binomial theorem

Let $$x = \sum_{m=2}^{n}2^{m-2},$$ and note that $$1 + x = 1 + 1 + 2 + 4 + \dotsb + 2^{n-3} + 2^{n-2}\tag{1}.$$ Then, multiplying $$(1)$$ by $$2$$, we have $$2+2x = 2 + 2 + 4 + \dotsb + 2^{n-2} + 2^{n-1}\tag{2}.$$ We can rewrite $$(1)$$ as $$1 + x = 2 + 2 + 4 + \dotsb + 2^{n-3} + 2^{n-2}\tag{3}.$$ Subtracting $$(3)$$ from $$(2)$$ gives us $$1 + x = 2^{n-1},$$ which is the same as $$2^{n-1} = 1 + 1 + 2 + 4 + \dotsb + 2^{n-2}.$$

Let $$S:=1+2+4+\dots+2^{n-2}$$.

Then, since it's a geometric series, we have $$S=\dfrac{1-2^{n-1}}{1-2}=2^{n-1}-1\implies S+1=2^{n-1}$$.