解决非齐次线性递推关系（log n）的时间

Question

我看到了有关为O解决复发（log n）的与矩阵功率时间这个问题：Solving a Fibonacci like recurrence in log n time

在这个问题的递推关系是同质的。

是否有非齐次线性递推关系的矩阵？

我的复发是：

一个（N）= A（N-1）+ A（N-2）+ 1，其中a（0）= 1，（1）= 1

“加一”使线性递推关系成为非均匀关系。

如果对于这种线性递推关系的没有矩阵，我怎么能计算在O（N）（log n）的时间？

Answer 1

可以编写为3D矢量矩阵形式的递归等式[A [N-1]，A [n]的，1]”。相应的向量递归是

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

因此，确实也是一个强力矩阵求幂解决方案成为可能。

Answer 2

您需要按照解决非齐次线性复发通常的程序。首先求解方便边界条件的非均匀部分，然后求解均匀部分。

经验表明，这里最便捷的边界条件是

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

这导致了解决方案a'(n) = -1的复发

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

现在我们写b(n) = a(n) - a'(n)线性齐次递推的所有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) 

通过检查，解决b(n)是b(n) = 2 Fibonacci(n + 1)，这样以来a(n) = b(n) + a'(n)，我们有a(n) = 2 Fibonacci(n + 1) - 1。