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.