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$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction