本文转载自菜鱼的blog

原文题为《常系数线性递推的第n项及前n项和》

（一）Fibonacci数列`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`的第`n`项的快速求法（不考虑高精度）.

解法：

考虑`1 xx 2`的矩阵`[F_{n-2}, F_{n-1}]`。

根据Fibonacci数列的递推关系，我们希望通过乘以一个`2 xx 2`的矩阵，得到矩阵`[F_{n-1},F_n]=[F_{n-1},F_{n-1}+F_{n-2}]`

很容易构造出这个`2 xx 2`矩阵`A`，即：
`[(0, 1), (1, 1)]`
所以，有`[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^n = (A^(n/2))^2`；`n`为奇数时，`A^n=(A^(n/2))^2*A`。

问题（一）解决。

（二）数列`F_n=F_{n-1}+F_{n-2}+1,F_{1}=F_{2}=1`的第`n`项的快速求法（不考虑高精度）.

解法：

仿照前例，考虑`1 xx 3`的矩阵`[F_{n-2},F_{n-1},1]`，希望求得某`3 xx 3`的矩阵`A`，使得此`1 xx 3`的矩阵乘以`A`得到矩阵：`[F_{n-1},F_{n},1]＝[F_{n-1},F_{n-1}+F_{n-2}+1,1]`

容易构造出这个`3 xx 3`的矩阵`A`，即：

`[(0, 1, 0), (1, 1, 0), (0, 1, 1)]`

问题（二）解决。

（三）数列`F_n=F_{n-1}+F_{n-2}+n+1,F_1=F_2=1`的第`n`项的快速求法（不考虑高精度）.

解法：

仿照前例，考虑`1 xx 4`的矩阵`[F_{n-2},F_{n-1},n,1]`，希望求得某`4 xx 4`的矩阵`A`，使得此`1 xx 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 xx 4`的矩阵`A`，即：
`[(0, 1, 0, 0), (1, 1, 0, 0), (1, 1, 0, 0), (0, 1, 1, 1)]`
问题（三）解决

（四）数列`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}] xx A+A^2+A^3+…+A^(N-1)`。很多人使用一种很数学的方法构造一个`2r xx 2r`（`r`是`A`的阶数，这里为`2`）的矩阵来计算，这种方法比较麻烦且很慢，这里不再介绍。下面考虑一种新方法。

仿照之前的思路，考虑`1 xx 3`的矩阵`[F_{n-2},F_{n-1},s_{n-2}]`，我们希望通过乘以一个`3 xx 3`的矩阵`A`，得到`1 xx 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 xx 3`的矩阵是：
`[(0, 1, 0), (1, 1, 1), (0, 0, 1)]`
然后…容易发现，这种方法的矩阵规模是`(r+1) xx (r+1)`，比之前流行的方法好得多。

（五）数列`F_{n}=F_{n-1}+F_{n-2}+n+1,F_{1}=F_{2}=1`的前`n`项和`s_{n}`的快速求法（不考虑高精度）.

解法：

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

考虑`1 xx 5`的矩阵`[F_{n-2},F_{n-1},s_{n-2},n,1]`

我们需要找到一个`5 xx 5`的矩阵`A`，使得它乘以`A`得到如下`1 xx 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为：
`[(0, 1, 0, 0, 0), (1, 1, 1, 0, 0), (0, 0, 1, 0, 0), (0, 1, 0, 1, 0), (0, 1, 0, 1, 1)]`
然后…问题解决。

一般地，如果有`F_{n}=p*F_{n-1}+q*F_{n-2}+r*n+s`

可以构造矩阵`A`为：
`[(0, q, 0, 0, 0), (1, p, 1, 0, 0), (0, 0, 1, 0, 0), (0, r, 0, 1, 0), (0, s, 0, 1, 1)]`

更一般的，对于`F_{n}=sum(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))^3*logn`

此方法高效、一般、统一、和谐！