CODEWITHSUNDEEP
algorithmrecurrence
Mark Samuel
Mark Samuel

Reputation: 37

Non-Linear Recurrence Relation

How can I find Nth term for this recurrence relation

F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

I have to find Nth term for this recurrence relation modulo 10^9+7.

I know how to find Nth term for linear recurrence relations but unable to proceed for this.

1<=N<=10^9

F(0) and F(1) are provided as an input.

Upvotes: 2

Views: 2898

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

There's a trick. Let G(n) = F(n) + 1. The equation

F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

becomes

G(n) - 1 = G(n-1) - 1 + G(n-2) - 1 + (G(n-1) - 1) * (G(n-2) - 1)
         = G(n-1) - 1 + G(n-2) - 1 + G(n-1)*G(n-2) - G(n-1) - G(n-2) + 1
         = G(n-1)*G(n-2) - 1,

so adding 1 to both sides,

G(n) = G(n-1)*G(n-2).

This is the multiplicative equivalent of the familiar Fibonacci recurrence. The solution is

G(n) = G(0)^Fib(n-1) * G(1)^Fib(n),

by analogy with the theory of linear recurrences (where Fib(-1) = 1 and Fib(0) = 0 and Fib(1) = 1), since

G(n-1)*G(n-2) = G(0)^Fib(n-2) * G(1)^Fib(n-1)
              * G(0)^Fib(n-3) * G(1)^Fib(n-2)
              = G(0)^Fib(n-1) * G(1)^Fib(n)
              = G(n).

Hence,

F(n) = (F(0)+1)^Fib(n-1) * (F(1)+1)^Fib(n) - 1,

doing the Fib computations via the matrix power method mod p-1 per Fermat's little theorem and the exponentiation mod p.

Upvotes: 12

Related Questions