2
$\begingroup$

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$.

Thanks.

  • 0
    Thanks for editing it for me and making it easier to read, I didnt know you can do that2012-01-20

1 Answers 1

2

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)$.