Sum of Geometric Progression

From ProofWiki
Jump to: navigation, search

Theorem

Let $x$ be an element of one of the standard number fields: $\Q, \R, \C$ such that $x \ne 1$.

Let $n \in \N_{>0}$.


Then:

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


Corollary 1

Let $a, a r, a r^2, \ldots, a r^{n-1}$ be a geometric progression.

Then:

$\displaystyle \sum_{j \mathop = 0}^{n - 1} a r^j = \frac {a \left({r^n - 1}\right)} {r - 1}$


Corollary 2

$\displaystyle \sum_{j \mathop = 0}^{n - 1} j x^j = \frac {\left({n - 1}\right) x^{n + 1} - n x^n + x} {\left({x - 1} \right)^2}$


Proof 1

For all $n \in \N_{> 0}$, let $P \left({n}\right)$ be the proposition:

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


Basis for the Induction

$P \left({1}\right)$ is the case:

$x^0 = \dfrac {x^1 - 1} {x - 1} = 1$

so $P \left({1}\right)$ holds.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k + 1}\right)$ is true.


So this is our induction hypothesis:

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


Then we need to show:

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


Induction Step

This is our induction step:


\(\displaystyle \sum_{j \mathop = 0}^k x^j\) \(=\) \(\displaystyle \sum_{j \mathop = 0}^{k - 1} x^j + x^k\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^k - 1} {x - 1} + x^k\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^k - 1 + \left({x - 1}\right) x^k} {x - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^k - 1 + x^{k + 1} - x^k} {x - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^{k + 1} - 1} {x - 1}\) $\quad$ $\quad$

So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

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

$\blacksquare$


Proof 2

Let $\displaystyle S_n = \sum_{j \mathop = 0}^{n - 1} x^j$.


Then:

\(\displaystyle \left({x - 1}\right) S_n\) \(=\) \(\displaystyle x S_n - S_n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle x \sum_{j \mathop = 0}^{n - 1} x^j - \sum_{j \mathop = 0}^{n - 1} x^j\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 1}^n x^j - \sum_{j \mathop = 0}^{n - 1} x^j\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle x^n + \sum_{j \mathop = 1}^{n - 1} x^j - \left({x^0 + \sum_{j \mathop = 1}^{n - 1} x^j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle x^n - x^0\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle x^n - 1\) $\quad$ $\quad$


The result follows.

$\blacksquare$


Proof 3

From Difference of Two Powers:

$\displaystyle a^n - b^n = \left({a - b}\right) \left({a^{n - 1} + a^{n - 2} b + a^{n - 3} b^2 + \ldots + a b^{n - 2} + b^{n - 1} }\right) = \left({a - b}\right) \sum_{j \mathop = 0}^{n - 1} a^{n - j - 1} b^j$

Set $a = x$ and $b = 1$:

$\displaystyle x^n - 1 = \left({x - 1}\right) \left({x^{n - 1} + x^{n - 2} + \cdots + x + 1}\right) = \left({x - 1}\right) \sum_{j \mathop = 0}^{n - 1} x^j$

from which the result follows directly.

$\blacksquare$


Proof 4

Lemma

Let $n \in \N_{>0}$.

Then:

$\displaystyle \left({1 - x}\right) \sum_{i \mathop = 0}^{n - 1} x^i = 1 - x^n$

$\Box$


Then by the lemma:

\(\displaystyle \left({1 - x}\right) \sum_{i \mathop = 0}^{n - 1} x^i\) \(=\) \(\displaystyle 1 - x^n\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 0}^{n - 1} x^i = \frac {1 - x^n} {1 - x}\) \(=\) \(\displaystyle \frac {x^n - 1} {x - 1}\) $\quad$ $\quad$

$\blacksquare$


Also presented as

Note that when $x < 1$ the result is usually given as:

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

Some sources give it as:

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

and likewise its corollary:

$\displaystyle \sum_{j \mathop = 0}^n a x^j = a \left({\frac {1 - x^{n + 1} } {1 - x} }\right)$


Examples

$\dfrac 1 7$ from $1$ to $n$

$\displaystyle \sum_{j \mathop = 0}^n \dfrac 1 {7^j} = \frac 7 6 \left({1 - \frac 1 {7^{n + 1} } }\right)$


Common Ratio $1$

Consider the Sum of Geometric Progression defined on the standard number fields for all $x \ne 1$.

$\displaystyle \sum_{j \mathop = 0}^n a x^j = a \left({\frac {1 - x^{n + 1} } {1 - x} }\right)$

When $x = 1$, the formula reduces to:

$\displaystyle \sum_{j \mathop = 0}^n a 1^j = a \left({n + 1}\right)$


Index to $-1$

Let $x$ be an element of one of the standard number fields: $\Q, \R, \C$ such that $x \ne 1$.


Then the formula for Sum of Geometric Progression:

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

still holds when $n = -1$:

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


Index to $-2$

Let $x$ be an element of one of the standard number fields: $\Q, \R, \C$ such that $x \ne 1$.


Then the formula for Sum of Geometric Progression:

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

breaks down when $n = -2$:

$\displaystyle \sum_{j \mathop = 0}^{-2} x^j \ne \frac {x^{-1} - 1} {x - 1}$


Also see


Sources