Sum of Powers of 2/Proof 2

Theorem

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

Then:

 $(1):\quad$ $\displaystyle 2^n - 1$ $=$ $\displaystyle \sum_{j \mathop = 0}^{n - 1} 2^j$ $\displaystyle$ $=$ $\displaystyle 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:

 $\displaystyle 2^1 - 1$ $=$ $\displaystyle 2 - 1$ $\displaystyle$ $=$ $\displaystyle 1$ $\displaystyle$ $=$ $\displaystyle 2^0$ $\displaystyle$ $=$ $\displaystyle \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:

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

Then we need to show:

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

Induction Step

This is our induction step:

 $\displaystyle \sum_{j \mathop = 0}^k 2^j$ $=$ $\displaystyle \sum_{j \mathop = 0}^{k - 1} 2^j + 2^k$ $\displaystyle$ $=$ $\displaystyle 2^k - 1 + 2^k$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle 2 \times 2^k - 1$ $\displaystyle$ $=$ $\displaystyle 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:

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

$\blacksquare$