Geometric series and big theta

Solution 1:

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.