# Sum of Powers of 2/Proof 2

Jump to navigation Jump to search

## Theorem

Let $n \in \N_{>0}$ be a (strictly positive) natural number.

Then:

 $\text {(1)}: \quad$ $\ds 2^n - 1$ $=$ $\ds \sum_{j \mathop = 0}^{n - 1} 2^j$ $\ds$ $=$ $\ds 1 + 2 + 2^2 + 2^3 + \dotsb + 2^{n - 1}$

## Proof

Let $S \subseteq \N_{>0}$ denote the set of (strictly positive) natural numbers for which $(1)$ holds.

### Basis for the Induction

We have:

 $\ds 2^1 - 1$ $=$ $\ds 2 - 1$ $\ds$ $=$ $\ds 1$ $\ds$ $=$ $\ds 2^0$ $\ds$ $=$ $\ds \sum_{j \mathop = 0}^{1 - 1} 2^j$

So $1 \in S$.

This is our basis for the induction.

### Induction Hypothesis

We now show that, if $k \in S$ is true, where $k \ge 1$, then it logically follows that $k + 1 \in S$.

So this is our induction hypothesis:

$\ds \sum_{j \mathop = 0}^{k - 1} 2^j = 2^k - 1$

Then we need to show:

$\ds \sum_{j \mathop = 0}^k 2^j = 2^{k + 1} - 1$

### Induction Step

This is our induction step:

 $\ds \sum_{j \mathop = 0}^k 2^j$ $=$ $\ds \sum_{j \mathop = 0}^{k - 1} 2^j + 2^k$ $\ds$ $=$ $\ds 2^k - 1 + 2^k$ Induction Hypothesis $\ds$ $=$ $\ds 2 \times 2^k - 1$ $\ds$ $=$ $\ds 2^{k + 1} - 1$

So $k \in S \implies k + 1 \in S$.

It follows by the Principle of Finite Induction that $S = \N_{>0}$.

That is:

$\ds \forall n \in \N_{> 0}: \sum_{j \mathop = 0}^{n - 1} 2^j = 2^n - 1$

$\blacksquare$