生成矩阵的递推关系

Question

回答了Math.SE，generating matrix for a recurrence relation

的复发f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)，一个人如何可以得到生成矩阵，以便它可以通过矩阵幂来解决？

为f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)相应的生成矩阵是：

| a 0 c | | f(n) | | f(n+1) | 
| 1 0 0 | x | f(n-1) | = | f(n) | 
| 0 1 0 | | f(n-2) | | f(n-1) | 

所以如何获得所需的复发一样吗？ 也应该是什么程序的任何复发可能的形式：

f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+..+someconstant*f(n-k)？

谢谢。

Answer 1

尝试阅读这篇文章 - http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html

我敢肯定，你可以看完后自己构建矩阵。