非线性递归关系 [英] Non-Linear Recurrence Relation

问题描述

如何找到该递归关系的第N个项

How can I find Nth term for this recurrence relation

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

我有为该递归关系找到第N个项，取模 10 ^ 9 + 7 。

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

我知道如何找到第N个项

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

1<=N<=10^9

提供F（0）和F（1）作为输入。

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

推荐答案

有一个窍门。设 G（n）= F（n）+ 1 。方程

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

成为

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,

因此在双方上都添加 1

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),

类似于线性递归理论（其中 Fib （-1）= 1 和 Fib（0）= 0 和 Fib（1）= 1 ），因为

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).

因此，

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

通过矩阵幂方法mod 进行 Fib 计算每个 Fermat小定理和幂模 p-1 p 。

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

这篇关于非线性递归关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！