特征根法是解决常系数齐次线性递推通项问题的通用做法。它十分普及，因为它简单好记。本文先简单介绍特征根法，然后给出几个证明。

齐次线性递推

我们先来看一下齐次线性递推的概念。我们定义 $k$ 阶的齐次线性递推应该长这个样子：

对任意 $n \in \mathbb{N}$，有 $a_{n+k} = c_1 a_{n+k-1} + c_2 a_{n+k-2} + \cdots + c_k a_n$ ，其中 $c_1 , c_2 , \cdots , c_k \in \mathbb{R}$

为了顺利推出每一项，这个递推还应该给出 $k$ 个初值 $a_0,a_1,a_2,\cdots,a_{k-1}$ 。

对了，在本文中，若未特别提及线性递推均为 $k$ 阶齐次线性递推。

特征根法

对于上面那个递推式，我们定义它的特征方程为：

$\lambda^k=c_1 \lambda^{k-1} +c_2 \lambda^{k-2} + \cdots + c_{k-1} \lambda +c_k$

这个方程有 $k$ 个根 $\lambda_1,\lambda_2,…,\lambda_k$ ，它们也许有些不是实数但没有关系。那么我们宣称数列 $\{a_n\}$ 的通项为

$a_n=p_1\lambda_1^n+p_2\lambda_2^n+\cdots+p_k\lambda_k^n$

其中 $p_1,p_2,…,p_k$ 是待定的系数，通过把初值 $n=0,1,2,…,k-1$ 带入后，可以解出 $p_1,p_2,…,p_k$ 。

重根的情况

重根的情况相对复杂。打个比方，假设 $\lambda_1=\lambda_2=\lambda_3$ 的话。我们只需要把原来设的通项中的 $p_1\lambda_1^n+p_2\lambda_2^n+p_3\lambda_3^n$ 改为 $(p_1n^2+p_2n+p_3)\lambda_1^n$ 就好了。具体来说就是，如果某个根有 $m$ 个重根，就设一个 $m-1$ 次的多项式乘上这个根的 $n$ 次方，不明白的可以再看看上面的例子。

举个例子————斐波那契数列

斐波那契数列 $\{f_n\}$ 满足递推关系 $f_{n+2}=f_{n+1}+f_n$ ，且有初值 $f_0=0$,$f_1=1$ 。求它的通项当然可以通过构造等比数列或者求生成函数的方法来求，但在这里，特征根法是最简单的一种。

化零多项式，例如特征多项式可以优化单变量的线性递推（详见博客《特征多项式优化线性递推》），我们来考虑多变量线性递推。我们先来看几个问题，从中体会一下怎么利用化零多项式优化线性递推。

好集个数

如果一个集合的全体元素之和为 $3$ 的倍数，我们则称之为好集（空集元素之和为 $0$ ）。
那么，在集合 $\{1,2,3,…,3n\}$ 的所有子集中，有多少个好集？

这道题(个人认为的)最漂亮的做法并不是利用线性递推，我将这个做法补充在文章结尾。

我们暴力一点，假设 $a_n$ 表示和为 $3$ 的倍数的集合个数，$b_n$ 表示和除 $3$ 余 $1$ 的集合个数，$c_n$ 表示和除 $3$ 余 $2$ 的集合个数,于是我们有：

$\begin{bmatrix}4 & 2 & 2\\2 & 4 & 2\\2 & 2 & 4\end{bmatrix}$ $\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}$ $=\begin{bmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \end{bmatrix}$

我们记：

$A=\begin{bmatrix}4 & 2 & 2\\2 & 4 & 2\\2 & 2 & 4\end{bmatrix}$

考虑 $A$ 的特征多项式 $f(\lambda)=-\lambda^3+12\lambda^2-36\lambda+32$。
根据 Caylay-Camilton 定理我们有 $f(A)=-A^3+12A^2-36A+32I=0$,于是我们得到：

$(-A^3+12A^2-36A+32I)\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}=0$ $A^3\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}-12A^2\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}+36A\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}-32\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}=0$ $\begin{bmatrix} a_{n+3} \\ b_{n+3} \\ c_{n+3} \end{bmatrix}-12\begin{bmatrix} a_{n+2} \\ b_{n+2} \\ c_{n+2} \end{bmatrix}+36\begin{bmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \end{bmatrix}-32\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}=0$ $\begin{bmatrix} a_{n+3}-12a_{n+2}+36a_{n+1}-32a_n \\ b_{n+3}-12b_{n+2}+36b_{n+1}-32b_n \\ c_{n+3}-12c_{n+2}+36c_{n+1}-32c_n \end{bmatrix}=0$

故：$a_{n+3}-12a_{n+2}+36a_{n+1}-32a_n =0 \Leftrightarrow a_{n+3}=12a_{n+2}-36a_{n+1}+32a_n$。

我们就根据转移矩阵得到递推式了，之后我们就可以使用特征方程法或者生成函数法求通项了，这都是后话。
值得注意的是，如果使用特征方程法，其特征方程就是 $f(\lambda)=0$（想想为什么） 。

我们先来分析调和级数和质数的倒数和的增长速度，最后聊一聊关于调和级数的有趣的事情。

调和级数

我们常用级数来表示一个数列的前缀和。调和级数就是自然数倒数序列 $\{\frac{1}{n}\}$ 的和，其表达式为:

$\sum_{i=1}^{\infty}\frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...$

这个和发散，但发散地极慢。举例来说，调和序列前 $10^{43}$ 项的和还不足 $100$。人们甚至一度认为这个数列收敛。欧拉精准地估计了这个和，并标明这个和的增长速度与自然对数的增长速度相同。具体来说：

$\sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + O(1/n)$

其中，误差项 $O(\frac{1}{n})$ 在 $n$ 增大时趋近于零，可以忽略不计。

欧拉的证明附于文尾。

质数的倒数和

事实上，质数的倒数和的增长速度是 $O(\ln \ln n)$ 下面给出简单证明：

欢迎大家去看杜瑜皓@《多项式及求和》

多项式线性插值算法讲的是：

已知一个 $k$ 次多项式 $F(x)$ 在整点 $0,1,2,3,4,5,…,k$ 处的值为 $F(0),F(1),F(2),…,F(k)$
我们能够在 $O(k)$ 的时间内求出 $F(n)$ 或者在 $O(k \log k）$ 的时间内求出原多项式$F(x)$

二项式反演

欢迎大家去看我的博客《二项式反演》啊orz

简单来说就是我们发现如果数列 $\{f_n\}$ 和 $\{g_n\}$ 满足:

$g_n=\sum_{i=0}^n C_n^i f_i$

则：

$f_n=\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$

牛顿级数

我们发现 $C_x^0,C_x^1,C_x^2,…,C_x^k$ 次数两两不同，他们线性无关，于是我们设：

$F(x)=\sum_{i=0}^k C_x^i p_i$

由二项式反演就可以得到：

$p_n=\sum_{i=0}^n (-1)^{n-i}C_n^iF(i)$ $\frac{p_n}{n!}=\sum_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\frac{F(i)}{i!}$

显然我们可以通过FFT在 $O(k \log k)$ 时间内算出各项系数 $p_i$ 。

演绎推理是我们在数学中经常遇到的一些方法。对于数列来说，通过原数列计算出新的数列叫作演绎，而通过计算出的数列反推出原数列则被称为反演。

形式化地，如果原数列为 $\{f_n\}$，新数列是 $\{g_n\}$ ，且满足

$g_n=\sum_{i=0}^n a_{ni} f_i$

反演就是我们希望通过 $\{g_n\}$ 得到 $\{f_n\}$ :

$f_n=\sum_{i=0}^n b_{ni} g_i$

结合一下就是

$g_n=\sum_{i=0}^n a_{ni} f_i \Leftrightarrow f_n=\sum_{i=0}^n b_{ni} g_i$

数列反演有许许多多种不同的类型，就例如莫比乌斯反演，二项式反演等等。其实，我们发现反演其实就是在解方程，一些方程组有算法上固定的、特殊的解，我们对于这些特殊的算法冠以具体的名字，就例如二项式反演。

二项式反演

二项式反演讲的是:

$g_n=\sum_{i=0}^n (-1)^i C_n^i f_i \Rightarrow f_n=\sum_{i=0}^n (-1)^i C_n^i g_i$

这个式子高度对称，它还有一个等价形式是我们所常用的：

$g_n=\sum_{i=0}^n C_n^i f_i \Rightarrow f_n=\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$

其实这里应该是双箭头，但是在这里右式是反演，左式则是演绎，故我们向右推出。先来证明这个反演公式，然后介绍它的应用。

欢迎大家去看叉姐的论文啊~

欢迎大家去看这篇文章的姊妹篇：特征多项式优化线性递推

叉姐利用了特征多项式将线性递推从矩阵快速幂的 $O(k^3 \log n)$ 优化到了 $O(k^2 \log n)$ 。

但这方法对没有学过线性代数的同学极不友好（大雾）。我们尝试利用简单线性表示干同样的事情：将线性递推的复杂度从 $O(k^3 \log n)$ 优化到了 $O(k^2 \log n)$ 。

齐次线性递推

我们先来看一下齐次线性递推的概念。我们定义 $k$ 阶的齐次线性递推应该长这个样子：

对任意 $n \in \mathbb{N}$，有 $a_{n+k} = c_1 a_{n+k-1} + c_2 a_{n+k-2} + \cdots + c_k a_n$ ，其中 $c_1 , c_2 , \cdots , c_k \in \mathbb{N}$ 。

其实我们还希望 $c_k \neq 0$ ,不然这就会退化成一个 $k-1$ 阶的齐次线性递推。但在大多数情况下可以不考虑这种情况，它并不影响最终的时间复杂度。

对了，在本文中，若未特别提及线性递推均为 $k$ 阶齐次线性递推。

线性表示

如果你学过线性相关的话，就知道线性相关和线性表示其实是等价的。

当然，假装我们什么线性代数都没学过的话，线性表示讲述的是一个数和一些数的关系:如果这个数能被这些数加加减减得到，那么就称这个数能被这些数线性表示。

形式化地，对于一个数 $a_n$ 和一些数 $a_0,a_1,\cdots,a_{k-1}$ ，如果存在 $p_0,p_1,\cdots,p_{k-1}$ ，使得 $a_n = p_0a_0 + p_1a_1 + \cdots +p_{k-1}a_{k-1}$ ，则称 $a_n$ 能被 $a_0,a_1,…,a_{k-1}$ 线性表示。

Q: 为什么我们要花这么大力气来求线性表示
A: 因为这样我们就可以根据 $p_0,p_1,\cdots,p_{k-1}$ 线性时间内求出 $a_n$。

每一个 $a_n$ 都可以被线性表示

我们发现，对于每一个 $a_n$ ，他都可以被 $a_0,a_1,\cdots,a_{k-1}$ 线性表示出来。

先举个例子， 对于一个 $3$ 阶的齐次线性递推 $a_{n+3} = a_{n+2} + 2a_{n+1} - a_n $ 。我们有：

$a_0= 1a_0 + 0a_1 + 0a_2$ $a_1= 0a_0 + 1a_1 + 0a_2$ $a_2= 0a_0 + 0a_1 + 1a_2$ 我们尝试继续向下推： $a_3= -1a_0 + 2a_1 + 1a_2$ $a_4= -1a_1 + 2a_2 + 1a_3$ $= -1a_1 + 2a_2 + (-1a_0 + 2a_1 + 1a_2)$ $= -1a_0 + 1a_1 + 3a_2$ $a_5= -1a_2 + 2a_3 + 1a_4$ $= -1a_2 + 2(-1a_0 + 2a_1 + 1a_2) + (-1a_0 + 1a_1 + 3a_2)$ $= -3a_0 + 5a_1 + 4a_2$

显然我们可以一直推下去。换句话说，每一个 $a_n$ 都可以用 $a_0,a_1,a_2$ 的线性组合表示。

欢迎大家去看叉姐的论文啊~

欢迎大家去看这篇文章的姊妹篇：利用简单线性表示优化线性递推

假设大家都学过矩阵快速幂了，下面主要讲将特征多项式黑科技。

温习：矩阵快速幂

对于一个 $k$ 次的线性递推:

$ h_n = a_1 h_{n-1} + a_2 h_{n-2} + ... + a_k h_{n-k} , \forall\ n \in \mathbb{N}\ ,\ n > k $

我们构造转移矩阵

$ A = \begin{bmatrix} a_1 & a_2 & \cdots & a_{k-2} & a_{k-1} & a_k\\ 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & \cdots & 1 & 0 & 0\\ 0 & 0 & \cdots & 0 & 1 & 0 \end{bmatrix}_{k \times k}$

和初始向量

$x = \begin{bmatrix} h_{k-1} \\ h_{k-2} \\ \vdots \\ h_2 \\ h_1 \\ h_0 \end{bmatrix}_{k \times 1}$

易见

$Ax = \begin{bmatrix} a_1 & a_2 & \cdots & a_{k-2} & a_{k-1} & a_k\\ 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & \cdots & 1 & 0 & 0\\ 0 & 0 & \cdots & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} h_{k-1} \\ h_{k-2} \\ \vdots \\ h_2 \\ h_1 \\ h_0 \end{bmatrix} = \begin{bmatrix} h_k \\ h_{k-1} \\ \vdots \\ h_3 \\ h_2 \\ h_1 \end{bmatrix} $

显然这样可以顺次推下去，于是我们只要得到 $A^{n-k+1}x$ 就可以得到 $ h_n $ ，由于一次矩阵乘法复杂度为 $ O(k^3) $ (听说可以更小一点，但我不会。。。) 矩阵乘法又满足快速幂性质，可以类比普通乘法快速幂得到一个 $O(k^3 \log n)$ 的优秀做法。

但是这个复杂度依然不够优秀，我们把眼光放到线性代数上。

​ 我们知道无穷级数 $\sum_{n\geq1} \frac{1}{n}=O(n\ln n)$ 发散。事实上，质数的倒数和 $\sum_{p\in \mathbb{P}} \frac{1}{p}=O(n\ln \ln n)$ 同样发散。简单证明可以看我的博客 《调和级数相关——质数的倒数和增长速度为O(ln ln n)》。

​ 尽管如此，平方的倒数和收敛（尽管收敛地很慢，我们将看到），而且收敛于一个有趣的数。

欧拉级数

$\sum_{n \geq 1} \frac{1}{n^2}=\frac{\pi^2}{6}$

​ 这是 1734 年 Leonhard Euler 做出的一个经典、著名且重要的结果。这个事实的一个重要解释是它导出了 Riemann zeta 函数的第一个非平凡值 $\zeta(2)=\frac{\pi^2}{6}$ 。不仅这一结果在数学史上有显赫的地位，它的几个极其优美聪明的证明也拥有自己的历史。本文就分享几个极为精妙的证明。

Euler 的证明

​ Euler 当然是十分聪明的，这个证明也十分优美。首先注意到 $\sin x$ 的泰勒展开
​

$$\sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+...$$
​ 从而
​ $\frac{\sin x}{x}=1-\frac{x^2}{3!}+\frac{x^4}{5!}-\frac{x^6}{7!}+...$
​ 令 $\frac{\sin x}{x}=0$ 解得 $x=k \pi (k \in \mathbb{Z}$ 且 $k \neq 0)$
​ 故我们将 $\frac{\sin x}{x}$ 因式分解
​ $\frac{\sin x}{x}=(1-\frac{x}{\pi})(1+\frac{x}{\pi})(1-\frac{x}{2\pi})(1+\frac{x}{2\pi})(1-\frac{x}{3\pi})(1+\frac{x}{3\pi})...$
​ $=(1-\frac{x^2}{\pi^2})(1-\frac{x^2}{4\pi^2})(1-\frac{x^2}{9\pi^2})...$
​ （Euler 似乎并没有证明这个因式分解的正确性。幸运的是，一个世纪以后，Weierstrass 提出了著名的 Weierstrass 分解定理，利用复分析证明了这个结论。）
​ 考虑这个因式分解的 $x^2$ 项前系数，对比泰勒展开式，可以知道
​ $-(\frac{1}{\pi^2}+\frac{1}{4\pi^2}+\frac{1}{9\pi^2}+...)=-\frac{1}{3!}=-\frac{1}{6}$
​ 两边同乘 $-\pi^2$ 即
​ $\sum_{n \geq 1} \frac{1}{n^2}=\frac{\pi^2}{6}$
​ 证毕