怎么用特征根法和不动点法求数列的通项公式？ 第1页

其实是处理一类叫做线性齐次递推方程的方法，这当中用到的思想其实是很深刻的，和线性代数有密切的关系，我其实觉得一个对线性代数没有了解的高中生是没有指望能够彻底理解这个方法的，而且在学了线性代数之后，这当中的原理简直是显而易见的，尤其是学习了线性齐次微分方程之后，会发现这两者几乎是一样的思路和方法。所以对于高中生来说，还是先粗略理解一下，如果有想不明白的地方，可以等以后学习了线性代数之后就会更明白了。

这两种方法其实是解决这样一类递推问题：

其中，是我们要求的数列，它的每一项由前k项递推得到，我们叫它k阶线性递推方程。是一系列常数，与n无关。当右侧的的时候，我们叫它k阶齐次线性递推方程；否则叫k阶非齐次线性递推方程。

在其中我们要求，否则它就是至多k-1阶的了。

举个例子，斐波那契序列

它可以改写成

，也就是一个2阶齐次线性递推方程。

如果我们要求的是

那么可以改写成

------------------------------------------------------分割-------------------------------------------------------------

我们从比较容易的齐次的问题开始，也就是。

我们不着急求方程的解的形式，首先先看看为什么叫做线性。对于这个方程，如果有两个数列都符合这个递推方程，那么考虑数列，有：

将每一项分别乘以固定的系数，然后相加，在数学上叫做线性组合。它可以进一步推广到三项或者以上。也就是说：

对于线性齐次递推方程，如果有一组解满足方程条件，则这组解的线性组合也满足方程条件。

我们可以用若干个“有特征的”解来作为代表，用它们的线性组合来表示其他的解。这组解在线性代数中叫做基底（base）。但不是所有的解都有用，比如说我们已经求出和，如果我们把合进来一起做线性组合，我们会发现得到的所有的解都是和本身线性组合的结果，因为本身也是前两项的线性组合，所以三项的线性组合仍然是前两项的线性组合。这在线性代数上叫做线性相关与线性无关。简单来说，如果有一个解已经可以表示成其他解的线性组合了，那么这个解就没有什么用了，我们直接用其他解的线性组合就好。线性无关也就是说任意一个解都不能表述成其他解的线性组合，或者等效来说：

对于基底（它们表示各不相同的数列），如果线性组合

（也就是说，线性组合的结果是全为0的数列）

只在

的时候成立，则我们说这些基底线性无关。显然它表明基底中每一项都不能表示为其他项的线性组合。

全0的数列是个特殊的解，它跟任意其他解都是线性相关的（系数取0就行了）。因为它太平凡了所以也叫做平凡解。基底当中不会包含这个解。

那么对于k阶线性齐次递推方程来说，我们知道，如果前k项都确定了，那么第k+1项就可以通过前k项算出来，第k+2项也可以跟着算出来，由此，后面所有的项都确定了。那么如果我们已知了k组线性无关的解，要求给定前k项初值的解，我们可以按前k项的值列出方程：

k个线性无关的方程，k个未知数，刚好能解出唯一的解。这说明有k个线性无关的解作为基底，则任意其他解都可以表示成这k个解的线性组合。在线性代数中，这说明解空间的维度是k，不过不需要深入理解这个概念。

复习：

线性齐次递推方程的解的线性组合仍然是线性齐次递推方程的解；

线性相关与线性无关；

k阶线性齐次递推方程有k个线性无关的解

------------------------------------------------------分割-------------------------------------------------------------

但是我们还没有说怎么求解的问题。不过从前面的结果中，我们得到了一种思路：我们不需要想办法对任意的初值求解；相反，我们无视初值，找到k个特殊的解，保证它们线性无关，然后利用初值的方程式解出每个基底对应的系数，从而求出相应的解。

我们求出一组特殊的等比数列的解来作为基底。为什么想到选择等比数列可以扯到母函数、z-变换等一系列问题上，我们不发散思路，总之当基底是等比数列（我们不需要设出前面的系数，因为只要底数相同，不同系数之间只差一个比例，这是线性相关的思想）的时候：

这是一个一元k次的方程，带上复数根在内，刚好有k个根，由于，显然不是这些根之一。如果这些根互不相同，那么这k个等比数列刚好就是k个解。用线性代数的方法可以证明它们是线性无关的，这跟范德蒙矩阵的性质有关，不展开讲，总之知道这件事就行了。

那么如果有重根呢？

根据微积分的原理，如果多项式在某个上有重根，则它在这一点上的一阶导数也为0，证明这一点可以考虑的代数基本定理展开的形式，它的导数可以用乘积导数公式展开，有重根的时候，重根展开的两项都为0。同样，如果有三个重根，则不仅一阶导数为0，二阶导数也为0。也就是说：

如果有多重根则二阶导数、三阶导数也为0。对比左边直接求导的系数：

我们就可以得到：也是原递推方程的解。如果有三个重根，则也是，有m重根的时候，

都是原递推方程的根

高阶导数本来是n(n-1)(n-2)...的形式，考虑到线性性，用任意一个线性无关的都可以，形式的比较简单。如果你喜欢把系数写成，也可以，只要是线性无关的就行。

以上内容对于高中生可能难了一点，总之记住：

假设原数列是等比数列，得到一个k阶方程，解出这个方程的所有根，每个根对应一个解；如果有重根，则依次用来替换它。得到的k组解是整个齐次递推方程的基底，它们是线性无关的。它们的组合可以表示任意一个特征方程的解。

假设原数列为等比数列后形成的一元k次方程

就叫做这个齐次线性递推方程的特征方程，这个方程的k个根就叫做这个方程的特征根。这些方程构成的解就叫做特征解。

求出特征解之后，按要求的初值列方程，就可以将最终要求的解表示为特征解的线性组合，从而求出最终要求的解。

------------------------------------------------------分割-------------------------------------------------------------

说完齐次的情况，再来说非齐次的情况。非齐次的情况其实没有想象的那么复杂，我们去掉最右边的得到一个齐次方程，用前面的方法，我们已经可以求出这个齐次方程的解。现在如果我们有任意一个非齐次方程的解，和任意一个相应齐次方程的解，则显然也是相应非齐次方程的解。跟齐次的情况相同，也是前k项完全决定了后面项的值，因此非齐次方程的解可以表示为：

任意一个非齐次方程的解 + 齐次方程的解的基底的线性组合

一般我们会用各种方法凑出一个非齐次方程的解，这个解就叫做特解；而相应齐次方程的解叫做通解。我们最后要求的解就可以写成通解 + 特解的形式，再通过解初值方程，得到通解中各个基底的系数，就可以解出非齐次的线性递推方程。

凑出非齐次方程的解的情况就需要不动点法出场了。对于一阶的情况，如果是个与n无关的常数，我们可以假设原数列是常数数列，也就是，然后代入递推关系解出C的值，这在将递推方程写成的时候，相当于求的不动点。可见不动点法其实是求特解的一种方法。

如果是别的值呢？我们一般根据的形式来凑这个特解，如果是n的m阶多项式，则的特解也是n的m阶多项式；如果是的形式，特解也是的形式；如果是几种可以凑出特解的形式的和，可以将其中每一种形式凑出特解再求和，来得到一个完整的特解。

凑出特解之后再求出齐次线性递推方程的通解，然后解初值方程就可以求出完整的通项。

------------------------------------------------------分割-------------------------------------------------------------

没看懂不要紧，我们来举几个例子。首先来个比较简单的，，其中

改写成

凑一个特解，特解的形式应该是，代回原方程：

因此

验证一下，的确是原递推方程的解。

再来求出通解，去掉非齐次项代入一个等比数列，特征方程是

特征根为

所以解的形式可以表示特征解的线性和再加上特解：

代入最早的递推关系中，得到

得到，因此

再来个稍微难一点的，，其中

改写成

求特解，设，或者利用不动点法，解出特解为

特征方程是

它有重根，因此特征解为

所以最后可以表示为

代入初值得到

所以

有的时候，递推方程一眼看上去根本不是线性的，但可以经过变换变成线性递推方程，比较经典的是分式的形式，比如

我们希望把它凑成

的形式，从而变成一个线性递推的方程。整理得到

比较系数得到

解出的过程不再细写