Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.