Take the 2-minute tour ×

I have a question about geometric series why is $g(n) = 1+c+c^2+....+c^n= \Theta(c^n)$ if $c>1$

I understand why it is $\Theta(n)$ if $c = 1$ and it is $\Theta(1)$ if $c <1$. But I just can't figure out why it is $\Theta(c^n)$ if $c>1$.


share|improve this question
Thanks for editing it for me and making it easier to read, I didnt know you can do that –  user308553 Jan 20 '12 at 5:20
add comment

1 Answer

Because $g(n)\geqslant c^n$ and $g(n)=\frac{c^{n+1}-1}{c-1}\leqslant a(c)\cdot c^n$ with $a(c)=\frac{c}{c-1}$, hence $c^n\leqslant g(n)\leqslant a(c)\cdot c^n$ for some finite $a(c)$ independent on $n$. This proves that $g(n)=\Theta(c^n)$.

Since $c^{n}\gg1$, the exact expression of $g(n)$ given above shows that, in fact, $g(n)\sim a(c)\cdot c^n$. This is a stronger statement than $g(n)=\Theta(c^n)$.

share|improve this answer
Thanks for the answer!! –  user308553 Jan 20 '12 at 7:50
add comment

Your Answer


