1
$\begingroup$

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

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

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .