1

I saw this question about solving recurrences in O(log n) time with matrix power: Solving a Fibonacci like recurrence in log n time

The recurrence relations in this question are homogeneous.

Is there a matrix for non-homogeneous linear recurrence relations?

My recurrence is:

a(n) = a(n-1) + a(n-2) + 1, where a(0) = 1 and (1) = 1

The "plus one" makes the linear recurrence relation a non-homogeneous one.

If there is no matrix for this kind of linear recurrence relation, how can I compute a(n) in O(log n) time?

Community
  • 1
  • 1
matheuscscp
  • 827
  • 7
  • 23

2 Answers2

3

You need to follow the usual procedure for solving non-homogeneous linear recurrences. First solve the non-homogeneous part for convenient boundary conditions and then solve the homogeneous part.

Experience suggests that the most convenient boundary conditions here are

a'(0) = -1 and a'(1) = -1,

which leads to the solution a'(n) = -1 for all n of the recurrence

a'(n) = a'(n - 1) + a'(n - 2) + 1.

Now we write the linear homogeneous recurrence for b(n) = a(n) - a'(n).

b(0) = a(0) - a'(0) = 2 and b(1) = a(1) - a'(1) = 2
b(n) = a(n) - a'(n)
     = a(n - 1) + a(n - 2) + 1 - a'(n - 1) - a'(n - 2) - 1
     = a(n - 1) - a'(n - 1) + a(n - 2) - a'(n - 2)
     = b(n - 1) + b(n - 2)

By inspection, the solution to b(n) is b(n) = 2 Fibonacci(n + 1), so since a(n) = b(n) + a'(n), we have a(n) = 2 Fibonacci(n + 1) - 1.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Okay, so b(0) = 2, b(1) = 2 and b(n) = b(n - 1) + b(n - 2). But, why b(n) = 2 Fibonacci(n + 1)? Assuming this is true, I can understand why a(n) = 2 Fibonacci(n + 1) - 1, but this inspection that leads b(n) to 2 Fibonacci(n + 1), I didn't understand... – matheuscscp Oct 03 '14 at 04:55
  • @matheuscscp It satisfies the Fibonacci recurrence `b(n) = b(n - 1) + b(n - 2)`, with slightly different boundary conditions. Fibonacci starting at 1 is 1, 1, and this is 2, 2, so it's twice the shifted Fibonacci sequence. – David Eisenstat Oct 03 '14 at 14:12
1

You can write the recursion equation in matrix form for the 3D vectors [ a[n-1], a[n], 1 ]'. The corresponding vector recursion is

/  a[n]  \     /  0  1  0  \   /  a[n-1] \
| a[n+1] |  =  |  1  1  1  | * |   a[n]  | 
\    1   /     \  0  0  1  /   \     1   /

So that indeed also a brute force matrix exponentiation solution becomes possible.

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51