Sum of Powers of 2/Proof 2

From ProofWiki
Jump to navigation Jump to search

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$


Sources