常系數(shù)線性遞推的第n項(xiàng)及前n項(xiàng)和

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

解法：

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

很容易構(gòu)造出這個(gè)2×2矩陣A，即：

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

又因?yàn)榫仃嚦朔M足結(jié)合律，故有：

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

這個(gè)矩陣的第一個(gè)元素即為所求。

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

問題（一）解決。

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

解法：

      仿照前例，考慮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】

容易構(gòu)造出這個(gè)3×3的矩陣A，即：

問題（二）解決。

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

解法：

      仿照前例，考慮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】

容易構(gòu)造出這個(gè)4×4的矩陣A，即：

問題（三）解決……

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

解法：

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

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

      仿照之前的思路，考慮1×3的矩陣【f[n-2],f[n-1],s[n-2]】，我們希望通過乘以一個(gè)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]】

容易得到這個(gè)3×3的矩陣是：

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

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

解法：

      結(jié)合（三）（四），容易想到……

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

我們需要找到一個(gè)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】

容易構(gòu)造出A為：

然后……問題解決。

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

可以構(gòu)造矩陣A為：

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

設(shè)Degree(Poly(n))=d, 并規(guī)定Poly(n)=0時(shí)，d=-1，此時(shí)對(duì)應(yīng)于常系數(shù)線性齊次遞推。則本方法求前n項(xiàng)和的復(fù)雜度為：

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

此方法高效、一般、統(tǒng)一、和諧！