解決非齊次線性遞推關係（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。