# Simple way of proving this series converges?

Sep 28, 2015Posted in Short

Doing my university homework, I came across the following.

Prove that $\sum_{i=0}^n r^i = 1 + r + r^2 + … + r^n$ is $O(1)$ if $0 < r < 1$.

With that range of $r$, $r^a > r^b$ iff $a < b$. Since $0 < 1 < … < n$, $1 > r > r^2 > … > r^n$. Thus, $\sum_{i=0}^n r^i = O(1)$

Equivalently, as $n$ approaches infinite, the series converges to a finite value.

Is this proof even correct? Stay tuned to find out!

## Incorrect!

$\sum_{i=0}^n r^i = O(1)$ is not implied by $1 > r > … > r^n$. The correct proof is the following.

This is the geometric series, so its value (only for $r \neq 1$) is $\frac{1-r^{n+1}}{1 - r}$.

If $0 < r < 1$, $r^{n+1}$ approaches $0$ as $n$ tends to infinite, and for no value of $n$ such that $n \geq 0$ this is greater than $r$. Thus, the expression is something with a constant upper bound divided by a constant, which has a constant upper bound.

Since there exists a constant $c$ for which $c \geq \frac{1-r^{n+1}}{1 - r}$ for $n \geq 0$, $\sum_{i=0}^n r^i = O(1)$ . Thus it has been proven.