特征根法、斐波那契数列和几个证明

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

齐次线性递推

我们先来看一下齐次线性递推的概念。我们定义 $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$ 。求它的通项当然可以通过构造等比数列或者求生成函数的方法来求，但在这里，特征根法是最简单的一种。

我们通过定义可以得出斐波那契数列的特征方程是：

$\lambda^2=\lambda+1$

解出来：

$\lambda_1=\phi=\frac{\sqrt5+1}{2}$ , $\lambda_2=1-\phi=\frac{1-\sqrt5}{2}$

于是我们设通项为：

$f_n=p_1\phi^n + p_2(1-\phi)^n$

带入 $n=0,1$ 得到：

$\begin{cases}p_1 + p_2 = 0\\ \frac{\sqrt5+1}{2}p_1 + \frac{1-\sqrt5}{2}p_2 = 1 \end{cases}$ $\Rightarrow \begin{cases}p_1 = \frac{1}{\sqrt5}\\p_2 = -\frac{1}{\sqrt5} \end{cases}$

故 $f_n= \frac{1}{\sqrt5}(\phi^n-(1-\phi)^n) $
即 $f_n= \frac{1}{\sqrt5}((\frac{\sqrt5+1}{2})^n-(\frac{1-\sqrt5}{2})^n)$

代几个值试试，神奇吧。

一个简单的证明

就拿斐波那契数列来举例子。斐波那契数列需要满足两个条件，一个是递推式 $f_{n+2}=f_{n+1}+f_n$ ，另一个是初值 $f_0=0,f_1=1$ 。满足这两个条件的数列是惟一的，那就是斐波那契数列。

我们先着眼于第一个条件——递推式。满足这个递推式的数列多种多样。理论上来说，只要随便确定初值 $f_0,f_1$ 都能生成一个满足这样递推式的数列。我们来尝试给两个初值，就 $f_0=1$ 和 $f_1=\phi$ 吧，看看会发生什么。

$f_2=f_1+f_0=\phi+1=\phi^2$ $f_3=f_2+f_1=\phi^2+\phi=\phi^3$ $f_4=f_3+f_2=\phi^3+\phi^2=\phi^4$ ... $f_n=f_{n-1}+f_{n-2}=\phi^{n-1}+\phi^{n-2}=\phi^n$

等比数列！

容易验证，数列 $\{1,1-\phi,(1-\phi)^2,…\}$ 也是一个满足递推式 $f_{n+2}=f_{n+1}+f_n$ 的等比数列。因为他们都是特征方程 $\lambda^2=\lambda+1$ 的根。

我们还知道一些性质，他们是显而易见的。比方说一个数列满足某个递推式，那么将数列中每个数都乘上一个常数，数列依旧满足这个递推式。再比方说如果都两个数列满足同一个递推式，那么他们的和，差（就是对应的数相加，减），也满足这个递推式。

形式化地，如果数列 $\{a_n\}$ 满足某个递推式，那么数列 $\{ka_n\}$ 也满足这个递推式，其中 $k \in \mathbb{C}$。

如果数列 $\{a_n\},\{b_n\}$ 满足某个递推式，那么数列 $\{a_n+b_n\}$ 也满足这个递推式。

下面，我们要进行一番操作了。

对于递推式 $f_{n+2}=f_{n+1}+f_n$,我们发现了两个等比数列满足这个递推式，他们的公比是方程 $\lambda^2=\lambda+1$ 的两个根 $\phi$ 和 $1-\phi$ 。但我们还需要满足初值条件 $f_0=0,f_1=1$。

我们已经知道了，我们对这两个等比数列加加减减，或者让他们各自乘上一个常数，得到的新数列依然满足递推式。于是我们尝试利用两个数列，组合出真正的斐波那契数列 $\{f_n\}$ 。

显然我们可以将两个数列分别乘上一个常数，然后加起来。如果加起来之后的新数列前两项满足初值条件 $f_0=0,f_1=1$ ，就大功告成了。我们假设两个数列分别乘常数 $p_1,p_2$ ，为了满足初值条件，我们可以得到

$\begin{cases}p_1 + p_2 = 0\\ \frac{\sqrt5+1}{2}p_1 + \frac{1-\sqrt5}{2}p_2 = 1 \end{cases}$ $\Rightarrow \begin{cases}p_1 = \frac{1}{\sqrt5}\\p_2 = -\frac{1}{\sqrt5} \end{cases}$

我们将两个等比数列分别乘上 $p_1,p_2$ 得到数列 $\{\frac{1}{\sqrt5},\frac{1}{\sqrt5}\phi,\frac{1}{\sqrt5}\phi^2,…\}$ 和数列 $\{\frac{1}{\sqrt5},\frac{1}{\sqrt5}(1-\phi),\frac{1}{\sqrt5}(1-\phi)^2,…\}$ ，把两个数列加起来，便是斐波那契数列。

哦~我这就是特征根法的工作原理。对于一个 $k$ 阶递推式的 $k$ 个不同的特征根，我们可以得到 $k$ 个满足递推式的等比数列，将它们加（待）加（定）减（系）减（数）就能组合出原数列。

那么是不是 $k$ 个公比不同的等比数列就一定可以组合的出来原数列呢？这是一个关于线性无关的问题，我们下一章再说。结论是，一定能。

这个证明唯一美中不足的是，它显然是知道结果反过来证明过程的。如果没有上文的介绍，也许根本不能理解这个证明。就算已经熟悉特征根法了，也会觉得这个证明在攀附结果。

重根的情况

麻烦的是，不是什么时候都能找到 $k$ 个不同的根，一旦有了重根，我们就找不到 $k$ 个公比不同的等比数列了。这使得我们待定的系数不到 $k$ 个，而我们又有 $k$ 个方程，大概率我们是解不出来的。

这就要求我们对于 $m$ 重根 $x$ ，我们除了找等比数列 $a_n=x^n$ ，还要找另外 $m-1$ 个数列，他们求通项都十分方便，而且他们之间不能加加减减就得到 。

直接证明并不方便，因为其后面蕴含着一些更为深刻的道理，我们将在下一章中知道。这里给出一个并不是十分漂亮的证明，但是不涉及到线性代数，高中知识足以应付，故放在这里仅供参考。

这需要一些高中的导数知识，有一些显而易见的性质。对于多项式 $f(\lambda)$ ,如果它在 $x$ 处有 $m$ 重根。那么它的导数 $f’(\lambda)$ 在 $x$ 处有 $m-1$ 重根，它的二阶导数 $f’’(\lambda)$ 在 $x$ 处有 $m-2$ 重根。简言之就是函数 $f(\lambda)$ 本身、一阶导数、二阶导数、…、$m-1$ 阶导数都在 $x$ 处有零点。即

$f(x)=f'(x)=f''(x)=\cdots=f^{(m-1)}(x)=0$

我们先来看一阶导数 $f’(\lambda)$ 。

$f(\lambda)=\lambda^k-c_1 \lambda^{k-1} -c_2 \lambda^{k-2} - \cdots - c_{k-1} \lambda -c_k$ $f'(\lambda)=k\lambda^{k-1}-c_1 (k-1)\lambda^{k-2} -c_2 (k-2)\lambda^{k-3} - \cdots - c_{k-1} \times 1 -c_k \times 0$

由 $f’(x)=0$ 可以得到：

$kx^{k-1}-c_1 (k-1)x^{k-2} -c_2 (k-2)x^{k-3} - \cdots - c_{k-1} \times 1 -c_k \times 0 = 0$ $kx^k-c_1 (k-1)x^{k-1} -c_2 (k-2)x^{k-2} - \cdots - c_{k-1} x -c_k \times 0x^0 =0$ $kx^k=c_1 (k-1)x^{k-1} +c_2 (k-2)x^{k-2} + \cdots + c_{k-1} x + c_k \times 0x^0$

这个等式告诉我们，如果我们给数列 $\{a_n\}$ 赋初值 $a_i=ix^i,0 \leq i < n$ ,根据递推式我们可以推出 $a_k=kx^k$ 。这是归纳的基石。接下来我们只需要归纳证明这个数列的通项确实是 $a_n=nx^n$ 就行了。这相当容易（就留作思考题吧）。

值得一提的是，如果我们考虑二阶导数 $f’’(x)=0$ ，我们直接得到的数列是 $a_n=n(n-1)x^n$ ，不过我们可以把这个数列加上 $b_n=nx^n$ ，这样就变成我们想要的 $a_n=n^2x^n$ 。更高阶的导数也要这么操作。如何使用 $n,n(n-1),n(n-1)(n-2),…,n(n-1)..(n-m+1)$ 的线性组合表示出 $n^m$， 这是个经典的组合问题，他们前面的系数被称为第二类斯特林数，具体可以看我另外一篇文章 《反演魔术——二项式反演》 。

真正的证明——矩阵

在这一章中，我们将再提升一个层次看问题——矩阵的角度看我们刚才都做了什么，并且为什么刚才做的相当理所当然，而不是为了凑出结果而证明的。

转移矩阵

对于一个 $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^nx$ 就可以得到 $ h_n $

无重根的情况——矩阵对角化

巨坑待填。。。

相关文章

都写得很好啊我能怎么办。

捡石子游戏、 Wythoff 数表和一切的 Fibonacci 数列@matrix67
怎么用特征根法和不动点法求数列的通项公式? - 灵剑的回答 - 知乎