Asymptotic bounds on geometric sums

Question

So I'm doing exercises from Dasgupta's Algorithms. The exercise i'm having trouble with is:

Show that, if $c$ is a positive real number, then $g(n) = 1 + c + c^2 +...+c^n$ is:

1. $\Theta(1)$ if $c<1$

2. $\Theta(n)$ if $c=1$

3. $\Theta(c^n)$ if $c>1$

(I dont know if this is a hint but it is included in the text: "The moral: in big-$\Theta$ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly indreasing or the number of terms if the series in unchanging")

The only one that makes sense for me is 2) where $1+1^2+..+1^n$ is the same as $n+1$, and removing the 1 gives $O(n)$. I dont know if my reasoning makes sense, but thats all i've got. I have no idea where to start or how to think on the other two. Any suggestions?

Answer 1

Hints:

• In the first case, use the inequalities $$ 1 \leq \sum_{i=0}^n c^i = \frac{1-c^{n+1}}{1-c} \leq \frac{1}{1-c}. $$

• In the second case, use the inequalities $$ c^n \leq \sum_{i=0}^n c^i = \frac{c^{n+1}-1}{c-1} \leq \frac{c}{c-1} c^n. $$

Answer 2

For an intuition of the first case, start with a decreasing geometric sum with an infinite number of terms. Calculate $c \cdot g(\infty) = c + c^2 + \ldots$, and $g(\infty) - c \cdot g(\infty) = 1$, so $g(\infty) = 1/(1-c)$. Clearly $g(n) \leq g(\infty)$ for any positive $c$, and so the entire series (infinite or finite) asymptotically matches the first term.

For an intuition of the 3rd case, take the sum to be $1 + d + d^2 + \ldots + d^n$, where $d>1$, and then let $c = 1/d$, so $c<1$. Now, $1 + d + d^2 + \ldots + d^n = d^n(c^n + c^{n-1} + c^{n-2} + \ldots + 1)$. That parenthesized sum on the right is your finite decreasing geometric series from the first case (in reverse order), which grows asymptotically like $\Theta(1)$, so your entire term grows like $d^n$, the last term of the finite sum.