link

Also you can do it preety easily in .

This is the sum of a geometric series so it can be calculated fast by divide and conqueror approach.

Let n = 2k then y = x¹ + x² + ... + x^k, and then the sum is y + x^k * y.