Θ designation of the sum of a geometric series

Question

I have a question about geometric rows. Why

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

for c> 1? I understand why this is Θ (n) if c = 1 and this is Θ (1) if c <1, but I just can’t understand why this is Θ (c) if c> 1.

Thanks!

Answer 1

The sum of the first n members of the geometric series

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

is set by

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

Note that if c> 1, then this quantity is bounded above c ⁿ - 1, and from below - c ^n-1 - 1 / c. Therefore, these are O (c ⁿ ) and & Omega; (c ⁿ ), therefore it is & Theta; (c ⁿ ).

Hope this helps!

Answer 2

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

The first thing to understand is that for some n S (n) = (c ^{n + 1} - 1) / (c - 1), where S (n) is the sum of the series.

So, we have (c ^{n + 1} - c ⁿ ) / (c-1) <= (c ^{n + 1} - 1) / (c - 1) = S (n), since c ⁿ > = 1.

So (c ^{n + 1} - c ⁿ ) / (c-1) = (c ⁿ (c-1)) / (c-1) = c ⁿ <= S (n)

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

Now that we have found our lower bound, consider the upper bound.

Note that S (n) = (c ^{n + 1} - 1) / (c - 1) <= (c ^{n + 1} ) / (c - 1) = ((c ⁿ ) c) / (c -1) .

To just our view of algebra a little, let y = c / (c-1) and substitute it in the above equation.

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

So now we have found our upper bound.

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

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