Finding sum of x^k from k= 0 to n in O(logn) time

Question

So my question is how to do this in C more specifically. I'm aware that O(logn) usually means that we'll be using recursion by somehow splitting one of the parameters.

What I'm trying to achieve is the sum of k = 0 to n of xⁿ. for example exponent_sum(x, n) would be the parameters in this case.

Then,

exponent_sum(4, 4) would be 4⁰ + 4¹ + 4² + 4³ + 4⁴ = 341.

I'm not sure where to start. Some hints would be really appreciated.

Answer 1

One way to look at the sum is as a number in base x consisting of all 1s.

For e.g, 4⁴ + 4³ + 4² + 4¹ + 4⁰ is 11111 in base 4.

In any base, a string of 1s is going to be equal to 1 followed by a string of the same number of 0s, minus 1, divided by the base minus 1.

For e.g:

• in base 10: (1000 - 1) / 9 = 999 / 9 = 111
• in base 16: (0x10000 - 1) / 0xF = 0xFFFF / 0xF = 0x1111
• in base 8: (0100 - 1) / 7 = 077 / 7 = 011

etc

So put these together and we can generalize that

exponent_sum(x, n) = (x ^{(n + 1)} - 1) / (x - 1)

For example, exponent_sum(4, 4) = (4⁵ - 1) / 3 = 1023 / 3 = 341

So the big O complexity for it will be the same as for computing xⁿ

Answer 2

Let me add another proof for the sake of completeness:

s = 1 + x¹ + x² + ... + xⁿ

Then

xs = x(1 + x¹ + x² + ... + xⁿ) = x¹ + x² + ... + xⁿ + xⁿ⁺¹ = s - 1 + xⁿ⁺¹

Solving for s

(x - 1)s = xⁿ⁺¹ - 1,

s = (xⁿ⁺¹ - 1)/(x - 1)

Answer 3

Another way to see the solution is like this: suppose the sum is S written as

S = 1 + x + x^2 + ... + x^k

Then if we multiply both sides of it by x we get

S*x = x * (1 + x + x^2 + ... + x^k)
    = x + x^2 + ... + x^k + x^(k+1)

then add 1 to both sides

S*x + 1 = 1 + x + x^2 + ... + x^k + x^(k+1)
        = (1 + x + x^2 + ... + x^k) + x^(k+1)
        = S + x^(k+1)

which means

S*x - S = x^(k+1) - 1
S*(x - 1) = x^(k+1) - 1

so

S = (x^(k+1) - 1) / (x - 1)