線性遞歸使用矩陣求冪

Question

矩陣求冪可用於求解線性遞歸。 我知道如何解決線性復發，如：

f(n) = f(n-k1) + f(n-k2) + ... + constant

，但我無法找到如何解決復發像

f(n) = f(n-k1) + f(n-k2) + ... + n^m

或

f(n) = f(n-k1) + f(n-k2) + ... + n*m

任何信息

或

f(n) = f(n-k1) + f(n-k2) + ... + k^n 即涉及'n'項的 。

任何人都可以提供任何鏈接或解釋如何解決這種復發 或如何形成其功率將用於解決復發的初始矩陣。

Answer 1

下面是一個例子。假設f(n) = f(n-1) + f(n-2) + (n-1)^2。我們也有n^2 = (n-1)^2 + 2(n-1) + 1和n = (n-1) + 1，它給出了代數項的線性遞歸。以矩陣形式，

|1 1 1 0 0| |f(n-1) | | f(n) | 
|1 0 0 0 0| |f(n-2) | |f(n-1)| 
|0 0 1 2 1| |(n-1)^2| = | n^2 | 
|0 0 0 1 1| | n-1 | | n | 
|0 0 0 0 1| | 1 | | 1 | 

重複左側向下n=2操作。