常系數線性遞推的第n項及前n項和

（一）Fibonacci數列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的第n項的快速求法（不考慮高精度）.

解法：

考慮1×2的矩陣【f[n-2],f[n-1]】。根據fibonacci數列的遞推關系，我們希望通過乘以一個2×2的矩陣，得到矩陣【f[n-1],f[n]】=【f[n-1],f[n-1]+f[n-2]】

很容易構造出這個2×2矩陣A，即：

所以，有【f[1],f[2]】×A＝【f[2],f[3]】

又因為矩陣乘法滿足結合律，故有：

【f[1],f[2]】×A ^n-1=【f[n],f[n+1]】

這個矩陣的第一個元素即為所求。

至于如何快速求出A ^n-1，相信大家都會，即遞歸地：n為偶數時，Aⁿ=(A ^n/2)²；n為奇數時，Aⁿ=(A ^n/2)²*A。

問題（一）解決。

（二）數列f[n]=f[n-1]+f[n-2]+1,f[1]=f[2]=1的第n項的快速求法（不考慮高精度）.

解法：

      仿照前例，考慮1×3的矩陣【f[n-2],f[n-1],1】，希望求得某3×3的矩陣A，使得此1×3的矩陣乘以A得到矩陣：【f[n-1],f[n],1】＝【f[n-1],f[n-1]+f[n-2]+1,1】

容易構造出這個3×3的矩陣A，即：

問題（二）解決。

（三）數列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的第n項的快速求法（不考慮高精度）.

解法：

      仿照前例，考慮1×4的矩陣【f[n-2],f[n-1],n,1】，希望求得某4×4的矩陣A，使得此1×4的矩陣乘以A得到矩陣：

【f[n-1],f[n],n+1,1】＝【f[n-1],f[n-1]+f[n-2]+n+1,n+1,1】

容易構造出這個4×4的矩陣A，即：

問題（三）解決……

（四）數列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的前n項和s[n]的快速求法（不考慮高精度）.

解法：

      雖然我們有S[n]=F[n+2]-1，但本文不考慮此方法，我們想要得到更一般的方法。

      考慮（一）的矩陣A，容易發現我們要求【f[1],f[2]】×（A+A²+A³+…+A^N-1）。很多人使用一種很數學的方法構造一個2r*2r（r是A的階數，這里為2）的矩陣來計算，這種方法比較麻煩且很慢，這里不再介紹。下面考慮一種新方法。

      仿照之前的思路，考慮1×3的矩陣【f[n-2],f[n-1],s[n-2]】，我們希望通過乘以一個3×3的矩陣A，得到1×3的矩陣：

【f[n-1],f[n],s[n-1]】=【f[n-1],f[n-1]+f[n-2],s[n-2]+f[n-1]】

容易得到這個3×3的矩陣是：

然后…………容易發現，這種方法的矩陣規模是(r+1)*(r+1)，比之前流行的方法好得多。

（五）數列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的前n項和s[n]的快速求法（不考慮高精度）.

解法：

      結合（三）（四），容易想到……

考慮1×5的矩陣【f[n-2],f[n-1],s[n-2],n,1】,

我們需要找到一個5×5的矩陣A，使得它乘以A得到如下1×5的矩陣：

【f[n-1],f[n],s[n-1],n+1,1】

=【f[n-1], f[n-1]+f[n-2]+n+1,s[n-2]+f[n-1],n+1,1】

容易構造出A為：

然后……問題解決。

一般地，如果有f[n]=p*f[n-1]+q*f[n-2]+r*n+s

可以構造矩陣A為：

更一般的，對于f[n]=Sigma(a[n-i]*f[n-i])+Poly(n)，其中0<i<=某常數c, Poly (n)表示n的多項式，我們依然可以構造類似的矩陣A來解決問題。

設Degree(Poly(n))=d, 并規定Poly(n)=0時，d=-1，此時對應于常系數線性齊次遞推。則本方法求前n項和的復雜度為：

((c+1)+(d+1))³*logn

此方法高效、一般、統一、和諧！