Sum of Geometric Sequence/Proof 4/Lemma
Jump to navigation
Jump to search
Lemma
Let $n \in \N_{>0}$.
Then:
- $\ds \paren {1 - x} \sum_{i \mathop = 0}^{n - 1} x^i = 1 - x^n$
Proof
Proof by induction on $n$:
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
- $\ds \paren {1 - x} \sum_{i \mathop = 0}^{n - 1} x^i = 1 - x^n$
Basis for the Induction
$\map P 1$ is the case:
\(\ds \paren {1 - x} \sum_{i \mathop = 1}^{1 - 1} x^i\) | \(=\) | \(\ds 1 \paren {1 - x}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 - x\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 - x^1\) |
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
- $\ds \paren {1 - x} \sum_{i \mathop = 0}^{k - 1} x^i = 1 - x^k$
Then we need to show:
- $\ds \paren {1 - x} \sum_{i \mathop = 0}^k x^i = 1 - x^{k + 1}$
Induction Step
This is our induction step:
\(\ds \paren {1 - x} \sum_{i \mathop = 0}^k x^i\) | \(=\) | \(\ds \paren {1 - x} \paren {x^k + \sum_{i \mathop = 0}^{k - 1} x^i}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x^k - x^{k + 1} + \paren {1 - x} \sum_{i \mathop = 0}^{k - 1} x^i\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x^k - x^{k + 1} + 1 - x^k\) | from the induction hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 - x^{k + 1}\) | gathering terms |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\ds \paren {1 - x} \sum_{i \mathop = 0}^{n - 1} x^i = 1 - x^n$
$\blacksquare$