Skiena the Algorithm Design Manual - Geometric Series Clarification

Question

Picture taken from book.

That is an explanation of a geometric series from the book, which I do not understand. Constant ratio is a right? So let's take first term (just the sum function), for n = 5, and constant ratio = 2.

So we will have this: 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 = 1 + 2 + 4 + 8 + 16 + 32 = 63

No if I use the RHS, a(a^n+1 - 1)/(a - 1). So it will give this: 2(2^5+1 - 1)/(2 - 1) for n = 5 this gives 126.

How can they be equal ?

Also it says later on: 'when a > 1 the sum grows rapidly with each new term..' Is he talking about space complexity ?

Because I do not get the big-theta notation. So for n = 5 and a = 2 it will take Big-Theta(64), 64 (2^6) steps?

Here is some ruby code:

n = 5
a = 2
sum = 0

for i in 0..n do
  sum = sum + a**i
end

puts sum # prints 63

I can see n+1 steps.

Any help understanding this please?

Answer 1

The formula in the book is wrong, there is an extra a factor (n=0 should yield 1, not a).

"The sum grows rapidly" is just about the values of the sum, it does not describe the complexity of computing it.