Θ notation for the sum of a geometric series

Question

I have a question about geometric series. Why is

1 + c + c² + ... + cⁿ = Θ(cⁿ)

when c > 1? I understand why it is Θ(n) if c = 1 and it is Θ(1) if c < 1, but I just can't figure out why it is Θ(cⁿ) if c>1.

Thanks!

Answer 1

The sum of the first n terms of the geometric series

c⁰ + c¹ + ... + c^n-1

is given by the quantitiy

(cⁿ - 1) / (c - 1)

Note that if c > 1, then this quantity is bounded from above by cⁿ - 1 and from below by c^n-1 - 1 / c. Therefore, it is O(cⁿ) and Ω(cⁿ), so it is Θ(cⁿ).

Hope this helps!

Answer 2

Let c > 1 and g(c) = 1 + c + c² + ... + cⁿ.

The first thing to realize is that for some n we have S(n) = (cⁿ⁺¹ - 1) / (c - 1) where S(n) is the sum of the series.

So we have that (cⁿ⁺¹ - cⁿ) / (c-1) <= (cⁿ⁺¹ - 1) / (c - 1) = S(n) since cⁿ >= 1.

So (cⁿ⁺¹ - cⁿ) / (c-1) = (cⁿ(c-1)) / (c-1) = cⁿ <= S(n)

Thus we have that S(n) >= cⁿ.

Now that we have found our lower bound, let's look for the upper bound.

Observe that S(n) = (cⁿ⁺¹ - 1) / (c - 1) <= (cⁿ⁺¹) / (c - 1) = ((cⁿ) c) / (c -1).

To simply our view of the algebra a bit, let y = c / (c-1) and substitute it into the equation above.

Hence, S(n) <= y * cⁿ where y is just some constant since c is! This is an important observation since now it is just a multiple of cⁿ.

So now we have found our upper bound as well.

Thus we have cⁿ <= S(n) <= y * cⁿ.

Therefore, S(n) = Θ(cⁿ) when c > 1.