Sum of Powers of 2

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 1

From Sum of Geometric Sequence:

$\ds \sum_{j \mathop = 0}^{n - 1} x^j = \frac {x^n - 1} {x - 1}$

The result follows by setting $x = 2$.

$\blacksquare$

Proof 2

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$