我试图解决Fibonacci序列的递归关系，但问题是它不是齐次的。
递归关系如下：
对于n>1，并且θ(n(＝c1n+c2，其中c1，c2>0
初始条件：F(0(=0，F(1(=1
我试图通过将其视为具有常系数的齐次线性二阶递归来解决它，但我不确定当我有时如何解决它
F(n(-F(n-1(-F
代替：
F(n(-F(n-1(-F
解决这种递归关系的最佳方法是什么？
您可以使用以下不等式找到下界和上界：
2F(n-2) + Theta(n) < T(n) < 2F(n-1) + Theta(n)
您可以很容易地证明下限和上限在Theta(n 2^n)中。因此，T(n) = Theta(n 2^n)。
使用AnsatzF1(n) = a*n + b可以获得
F1(n) - F1(n-1) - F1(n-2) = -a*n + 3a - b = Θ(n) = c1*n + c2.
所以我们有a = -c1和b = -3c1 - c2，即
F1(n) = -c1*n - 3c1 - c2
在不查看初始条件的情况下求解给定的递归。将其与齐次递归的解决方案F0相结合(参见Binet公式(
F0(n) = d1*q1^n + d2*q2^n
用q1/2 = (1 +/- sqrt(5))/2得到
F(n) = F0(n) + F1(n) = d1*q1^n + d2*q2^n - c1*n - 3c1 - c2 .
现在可以通过求解线性方程组来调整因子d1、d2以匹配给定的初始条件
F(0) = d1 + d2 - 3c1 - c2 = 0
F(1) = d1*q1 + d2*q2 - 4c1 - c2 = 1
对于d1、d2。