Consider the following function:
$$S(n)=1+ c + c^2 + ยทยทยท + c^n,$$
where c is a positive real number.
(A) This function is the sum of a geometric series. Give a precise closed-form formula for $S(n)$, interms of $c$ and $n$, in the case where $c \neq 1$.
(B) Show that $S(n)$ is:
$\theta(1)$ if $c<1$
$ \theta(n)$ if $c=1$
$\theta(c^n)$ if $c>1$
can someone please explain how i can go about finding the solutions for these problems, i have never encountered these and am stuck, i know that big theta means that the function is bond on both sides but how do i got about finding the answer?
(edit)
im still having trouble understanding part B. can someone please explain? (can someone walk me through the second one) so far i have $n \leq c^{n+1} \leq ???$
(edit #2)
i tried doing the first one can someone verify if i did it right
$S(n)$ is $\Theta(1)$ if c<1
(1)$S(n)$ is $O(1)$ if c<1
(2)$S(n)$ is $\Omega(1)$ if c<1
(1) $$\frac{C^{n+1}-1}{C-1} \lt (C_1)(1)$$
$$\frac{C^{n+1}-1}{C-1} \lt (C_1)$$
$$C^{n+1} \lt C_1(C-1)$$
$$C^nC-1 \lt C_2C-1$$
$$C^n \lt C_2$$
$$C^n \lt 1$$
since c<1 this means that any number that will be $C^n$ will be less then 1 for all positive n
i did the omega part pretty much the same way and got
$$C^n \gt C_2$$
$$C^n \gt 0$$
since c<1, $C^n$ can potentially become very very small so the only thing bounding it is 0 for all positive n
Best Answer
For (A), consider $cS(n) = c+c^2 + c^3 + \cdots + c^{n+1}$. If you do the subtraction $cS(n) - S(n)$, you can see many terms would cancel out, and you will get a closed form, for $c\ne 1$.
After you get the closed form, you should be able to see the big $\Theta$ of the 3 cases.
Now you should get, for $c\ne1$, $$S(n) = \frac{c^{n+1}-1}{c-1} = \frac{1-c^{n+1}}{1-c}$$
For $c>1$ case,
$$S(n) = \frac{c^{n+1}-1}{c-1} = \frac{c\cdot c^n-1}{c-1} = \frac{c}{c-1}c^n-\frac{1}{c-1}$$
You can see that $S(n) < \frac{c}{c-1}c^n$ for all $n$, and $S(n)>c^n$ when
$$\begin{align} \frac{c}{c-1}c^n-\frac{1}{c-1}>& c^n\\ \left(\frac{c}{c-1}-1\right)c^{n}>&\frac{1}{c-1}\\ c^{n} >& 1\\ n>&0 \end{align}$$
Therefore $S(n)=\Theta(c^n)$. The other two cases are pretty much similar.