The same question was posted here but I feel necessary details were left out:
Geometric series and big theta
The question states: Show that, if $c$ is a positive real number, then $f(n)= \sum\limits_{k=0}^n c^k$ is:
- $\theta (1)$ if $c < 1$
- $\theta (n)$ if $c = 1$
- $\theta (c^n)$ if $c > 1$
I know that as $k$ approaches infinity this can be simplified to $\dfrac{1}{1-c}$ and since that doesn't rely on $n$, it's constant, thus the first bullet point is done (that's how my instructor explained it to me). However, that doesn't work for $c = 1$, and doesn't prove the third bullet. So how do I do this properly? Thank you.
For $c=1$ it is trivial, i.e.
$$f(n) = \sum_{k=1}^{n} c^k = \sum_{k=1}^{n} 1 = n \Longrightarrow f(n)\in O(n)$$
For $c>1$ you will get
$$f(n) = \sum_{k=1}^{n} c^k = \frac{1-c^{k+1}}{1-c} = \frac{ c^{k+1} - 1}{c -1} = c^{k+1}\underbrace{\frac{1}{c -1}}_{const}+\underbrace{\frac{- 1}{c -1}}_{const}\Longrightarrow f(n) \in O(c^n)$$