# Geometric series and big theta

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

-
Can you do part (A)? –  Oscar Cunningham Sep 30 '13 at 23:26
yea i got $\frac{1-c^{n+1}}{1-c}$ for $c\neq 1$ for A is that correct? –  notamathwiz Sep 30 '13 at 23:34
Yes, then do you still need help on (B)? –  peterwhy Sep 30 '13 at 23:36
yes, thats actually what i needed help on –  notamathwiz Sep 30 '13 at 23:41
@notamathwiz I modified my answer –  peterwhy Sep 30 '13 at 23:51

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.

-