recurrence relation dependent inversly on n

Question

I recently learnt to find out nth number fibonacci series by matrix exponentiation. but i am stuck on two relations :

1) F(n) = F(n−1) + n            
2) F(n) = F(n−1) + 1/n    

Is there any efficient way to solve these in O(logn) time like we have matrix expo. for fibonacci series ?

Answer 1

The first one is obviously equal to:

F(n) = F(0) + n*(n+1)/2

and can be computed in O(1) time. For the second, look here.

---

Supposing that you want to compute the first one with matrix exponentiation, in the same way that you did with the Fibonacci series, here's the matrix you should use:

    | 1 1 0 |
A = | 0 1 1 |
    | 0 0 1 |

The choice of matrix is obvious if you think of the following equation:

| F(n+1) |   | 1 1 0 |   | F(n) |
|  n+1   | = | 0 1 1 | * |  n   |
|   1    |   | 0 0 1 |   |  1   |

Of course, the starting vector has to be: (F(0), 0, 1).

For the second series this is not so easy, as you would want to gradually compute the value 1/n, which cannot be computed linearly in this way. I guess it cannot be done but I won't try to prove it.

Answer 2

The first one can be calculated in O(1) just because this is an arithmetic progression and the sum is n*(n-1)/2.

The second one is a harmonic series and can not be calculated efficiently, but you can approximate it in O(1) with:

where the first one is a 0.57721566490153286060 and the second is approximately 1/(2k)