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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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