[Solved] Given 1 < a < 10, 1 ≤ n ≤ 100000, show how to compute the value of 1 × a + 2 × a^2 + 3 × a^3 + . . . + n × a^n efficiently, i.e. in O(log n)!

by


If this is homework I guess your professor explained you how to compute Fibonnacci numbers and expect you to use the same trick.

So basically remark that:

|1+a+ a²+...+ a^n|   |a 0 1| |1+a+ a²+...+     a^(n-1)|
|  a+2a²+...+na^n| = |a a 1| |  a+2a²+...+(n-1)a^(n-1)|
|1               |   |0 0 1| |1                       |

                     |a 0 1|^n  |1|
                   = |a a 1|    |0|
                     |0 0 1|    |1|

You need to do a matrix exponentiation, which is O(log(n)) if we don’t take into account the precision and only use standard machine’s operation.

solved Given 1 < a < 10, 1 ≤ n ≤ 100000, show how to compute the value of 1 × a + 2 × a^2 + 3 × a^3 + . . . + n × a^n efficiently, i.e. in O(log n)!