高中数学/不等式与数列/常系数线性递推数列

阅读指南

在差分方程与微分方程理论中，若干考察量之间呈现线性比例关系是最简单的情形，也是严格说来唯一存在普遍解法的情形。而对于更普遍的非线性关系式，往往也只能想办法先转换为人们更熟悉的线性关系后，才能变得易于求解。因此，分析清楚线性情形的求解变得格外重要。

本节主要讲解一种二阶的线性递推式求解思路，并简要介绍了更高阶情形的一般结论。由于计算可能比较麻烦，我们更推荐在领会求解思路的基础上，利用计算机程序或软件解决它们。在后面的多元递推数列章节中，我们还会将其拓展到多阶多变量的情形。虽然多元递推数列从数学角度来说一般是难以求出形式简便的通解，但是原则上可以通过计算机程序自动递推求解出任意特定项，在实际问题的数学建模（也就是应用题啦）中也更常见。

预备知识

本节大部分内容都要求读者至少了解递推数列的基本概念和一阶递推数列的常见解法，所以读者应该先阅读数列基础概念和一阶递推数列章节，然后再根据需要选读本节的内容。

考试要求

本节介绍的数列及其求解方法一般不被列入中学常规考试的考察范围。但是其方法并不难学，可以适当了解。

后续课程联系

本节对线性关系式的求解只是整个线性系统研究的冰山一角，这种基于特征方程的解法一般可以在有关“组合数学”或“差分方程”的大学课程中学习到。在其它后续的大学课程中，我们还将把研究线性系统的经验进一步加深，然后应用到经典力学、经典电路学、微分方程、积分变换、信号处理和量子力学等学科中。

本节提及的Fibonacci数列是特别常见的例子，与黄金分割比例也存在密切联系，进而在优选法中的分数法和外汇技术分析中的斐波那契回调都能见到它的应用。

基础知识

定义：k阶常系数线性递推关系（linear recurrence relation of degree k with constant coefficients）$\{a_{n}\}$的一般形式为： $a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k-1}a_{n-k}=b(n)$
其中各个$c_{i}$都是已知常数，而$b(n)$是关于n的已知表达式（可以记作数列$b_{n}$）。

特别地，当$b(n)=0$时，以上关系式又叫做（k阶的）常系数齐次线性递推关系（linear homogeneous recurrence relation of degree k with constant coefficients），否则叫做非齐次的常系数线性递推关系，$b(n)$叫做非齐次项。

“k阶”（degree k）是指关系式中出现的不同的$a_{i}$一共有k个；“常系数”（constant coefficients）是指式子中各个$c_{i}$都是与n的取值无关的常数；“线性”（linear）是指式子中各个$a_{i}$都是以一次幂单项式的形式出现的；“齐次”（homogeneou）是指式子中的每个单项式都是次数相同的，在这里可以说是不含常数项的。

用线性递推关系式描述的数列也叫做线性递推数列。对于n阶的常系数齐次线性递推数列，一般给定n个初始值（或者叫边界条件），即可确定所求的解。

线性递推关系看似形式单一，但不意味着它过于简单以至于缺乏实际应用。事实上，“在实际问题中常见”和“可以系统求解”这两点都是人们关注它的主要原因。本节主要关注它的求解方法，在后面的应用问题的递推关系建模章节中还会看到它的更多实例。

提示：齐次线性递推关系是有通用方法求解的；而非齐次的情形仅当非齐次项的母函数形式易知时才容易求解。

注意：在线性代数学的术语中，非齐次的关系式并不被认为是一种线性映射。就像是“线性方程组”一词中的“线性”与“线性映射”中的“线性”含义并不一样。但是齐次情形下的解与非齐次情形下的解存在密切联系，只要我们找到了齐次情形下的解，那么这个解也能为相关的非齐次情形下的解提供重要线索。当然在高中数学中，可以暂时不去纠结于这些概念细节。

2阶的齐次情形

列奥纳多·费波那契（Leonardo Fibonacci，1175年－1250年）在《计算之书》（Liber Abaci）中提到并求解了一个在理想假设条件下兔子成长率的经典问题。

数学家爱德华·卢卡斯（François Édouard Anatole Lucas，1842年－1891年）也是汉诺塔游戏（巧妙地在3个柱子之间移动一串圆盘）的发明人。

此为数列研究双煞，也就是参加数列章节考试前必须膜拜的2个人（除非您不怕在百分制的数学考试中获得Fibonacci数列中前几个数那样的得分）。

最常见的2阶齐次线性递推式是由列奥纳多·斐波那契给出的斐波那契数列（Fibonacci sequence）或者叫费氏数列$\{F_{n}\}$问题：
$F_{0}=F_{1}=1,F_{n+2}=F_{n+1}+F_{n}\quad (n\geq 2,n\in \mathbb {N} )$

提示：数列的编号具体是从0开始取还是从1开始取，并不影响这个问题的数学本质。

提示：有的人也将斐波那契数列叫做兔子序列。但是兔子序列更多的是用作斐波那契词（Fibonacci word）的别名。它斐波那契词只是模仿斐波那契数列构造的字符序列，但与之并不相同。为避免混淆，我们不推荐将斐波那契数列简称为兔子数列。

另一个常见的2阶齐次线性递推式是由爱德华·卢卡斯给出的卢卡斯数（Lucas number）$\{L_{n}\}$的递推问题：
$L_{0}=2,L_{2}=1,L_{n+2}=L_{n+1}+L_{n}\quad (n\geq 2,n\in \mathbb {N} )$

这类2阶递推关系的一般形式$a_{n+2}=c_{1}a_{n+1}+c_{2}a_{n}\quad (n\geq 3,n\in \mathbb {N} ,c_{1}\in \mathbb {R} ,c_{2}\in \mathbb {R} )$也叫做卢卡斯数列（Lucas sequence）。

提示：卢卡斯数构成的数列和卢卡斯数列的概念并不一样。卢卡斯数列包括了由卢卡斯数组成的数列和Fibonacci数列。

卢卡斯数列的递推式可以通过待定系数法构造为以下形式的等比关系（其中$c_{1}$和$c_{2}$为非零的已知常数，p和q为待定系数）：
$L_{n+2}=c_{1}L_{n+1}+c_{2}L_{n}\quad \Leftrightarrow \quad L_{n+2}+qL_{n+1}=p(L_{n+1}+qL_{n})$
通过对比变形前后的各个对应项的系数即可求出p和q的值。然后把$L_{n+2}+qL_{n+1}$看成一个整体，易知数列$\{L_{n+2}+qL_{n+1}\}$满足等比数列的定义，因而容易求出通项公式。知道$L_{n+2}+qL_{n+1}$的解析式后，再对其进行一次构造，即可得到$L_{n}$的解析式。

由上述分析可知，整个过程进行了2次递推关系式的构造，每构造一次就会降低一次递推式的阶数。有时候满足要求的待定系数会是比较复杂的分数，导致运算过程冗长且易错。因此这种使用待定系数的构造方法可行，但是不太适合手工求解，我们推荐使用本节后面介绍的计算机编程的办法求解。

为简明起见，我们先直接给出Fibonacci数列的通项公式如下：
$F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})\quad (n\in \mathbb {N} ^{+})$
由于直接进行构造式的证明比较繁琐，我们改为在数学归纳法章节中用新方法再对这个通项公式的正确性给予证明。

卢卡斯数列吸引数学家们注意的一个主要的特点就是它的通项公式中隐藏了数秘学中的黄金分割比例。事实上，我们在后面将会学到，Fibonacci数列的相邻项比值${\frac {F_{n}}{F_{n+1}}}$的数列极限也是黄金分割比例。这也是后面在优选法中要介绍的分数法的由来基础。

n阶的齐次情形

先给出结论：

对于形式为$a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}=0$的齐次递推式，可以定义特征方程：
$x^{k}+c_{1}x^{k-1}+c_{2}x^{k-2}+...+c_{k}=0$
由代数学基本定理可知，k次代数方程一定存在k个解。假设此特征方程有k个不同的解$x_{1},x_{2},x_{3},...,x_{k}$，则原递推式的通解（即一般解）为：
$a_{n}=d_{1}x_{1}^{n}+d_{2}x_{2}^{n}+d_{3}x_{3}^{n}+...+d_{k-1}x_{k-1}^{n}+d_{k}x_{k}^{n}$
其中的各个$d_{i}$是由给定的具体初始条件而确定的待定系数。

事实上由于高次代数方程一般难于通过笔算求解，所以笔算3阶及更高阶的线性递推式通解一般并不现实。

我们在此简要说明一下上面给出的通项公式是满足齐次递推关系式的。
设满足递推式的通解具有形式$a_{n}=d_{1}x_{1}^{n}+d_{2}x_{2}^{n}+...+d_{k}x_{k}^{n}$，其中各$x_{i}$是原递推式特征方程的各个不同根。
既然要说明$a_{n}$满足递推关系式，就可以尝试用倒退法，将$a_{n}$代入递推关系式，看看使等式成立的条件是否足够：
${\begin{array}{l}a_{n}+c_{1}a_{n-1}+...+c_{k}a_{n-k}=0\\\Leftrightarrow (d_{1}x_{1}^{n}+d_{2}x_{2}^{n}+...+d_{k}x_{k}^{n})+c_{1}(d_{1}x_{1}^{n-1}+d_{2}x_{2}^{n-1}+...+d_{k}x_{k}^{n-1})+...+c_{k}(d_{1}x_{1}^{n-k}+d_{2}x_{2}^{n-k}+...+d_{k}x_{k}^{n-k})=0\end{array}}$
交换求和顺序可得：
${\begin{array}{l}\Leftrightarrow (d_{1}x_{1}^{n}+c_{1}d_{1}x_{1}^{n-1}+...+c_{k}d_{1}x_{1}^{n-k})+(d_{2}x_{2}^{n}+c_{1}d_{2}x_{2}^{n-1}+...+c_{k}d_{2}x_{2}^{n-k})+...+(d_{k}x_{k}^{n}+c_{1}d_{k}x_{k}^{n-1}+...+c_{k}d_{k}x_{k}^{n-k})=0\\\Leftrightarrow d_{1}x_{1}^{n-k}(x_{1}^{k}+c_{1}x_{1}^{k-1}+...+c_{k})+d_{2}x_{2}^{n-k}(x_{2}^{k}+c_{1}x_{2}^{k-1}+...+c_{k})+...+d_{k}x_{k}^{n-k}(x_{k}^{k}+c_{1}x_{k}^{k-1}+...+c_{k})=0\\\end{array}}$
由于各个特征方程的根一定满足特征方程，进而得到：
${\begin{array}{l}d_{1}x_{1}^{n-k}\times 0+d_{2}x_{2}^{n-k}\times 0+...+d_{k}x_{k}^{n-k}\times 0=0\\\Leftrightarrow 0=0\end{array}}$
这说明$a_{n}$的确满足原来的齐次递推关系式。

提示：如果规定$c_{0}=1$，那么上述过程可以用连加号及其运算规律简化如下：
${\begin{array}{l}\sum _{i=0}^{k}\limits (c_{i}a_{n-i})=\sum _{i=0}^{k}\limits (c_{i}(\sum _{j=1}^{k}\limits d_{j}x_{j}^{n-i}))=\sum _{j=1}^{k}\limits (d_{j}\sum _{i=0}^{k}\limits (c_{i}x_{j}^{n-i}))=\sum _{j=1}^{k}\limits (d_{j}\times 0)=\sum _{j=1}^{k}\limits 0=0\end{array}}$

另一方面，要说明上述形式的通解涵盖了一切初始值下的齐次递推关系式的特解（即不会有漏掉的解），需要将k个初始条件分别代入假设成立的通项公式中，构成包含k个未知待定系数的k元线性方程组。判断此方程组在“特征根彼此不同”的条件下是否始终有解即可。由于其严格证明需要用到线性代数中的克莱姆法则和范德蒙矩阵公式，我们不再展开讲解。粗略地说，由k个独立的已知条件确定出k个未知系数基本上是足够的。

非齐次情形

对于一个常系数非齐次线性递推式，假设已求出其齐次形式的一个通解$b_{n}$（即先忽略掉常数项求解），如果能再求得原递推式的一个特解$c_{n}$，则由线性系统的叠加原理可知，原非齐次递推式的通解$a_{n}$一定满足如下形式：
$a_{n}=b_{n}+c_{n}$
读者可以仿照前面对于齐次情形的分析思路，检验此形式的通解满足非齐次线性递推式。

不过更大的难点在于非齐次项的形式可能很复杂，导致递推式的特解不一定总是很好地求出来。实际上，只有少数母函数易知的情形容易得到特解。

计算机求解

在旧版Mathematica软件中，可以通过RSolve命令求解常系数线性齐次递推式的通项公式。在Mathematica 10中，还可以通过RSolveValue命令求解常系数线性递推式的通项公式。

如果使用从边界条件正向递推的方法或从目标值倒推回溯的方法（在计算机算法理论中常简称为“递归法”），也可以用更一般的编程语言求解出数列中特定项的数值解。

提示：Fibonacci数列的计算也是计算机编程教程的常见案例。计算机从业者对它的兴趣可能并非来源于毕达哥拉斯学派信仰的数学神秘主义，而只是想说明某一种计算机编程语言可以如何实现递归算法（从而不会比同样可以实现递归算法的其它编程语言差劲）。

Mathematica

通过定义函数求特定项

最原始的方法是通过自定义递推关系式。例如：

fib[n_] := fib[n] = fib[n - 1] + fib[n - 2]; (* 以递推的形式设置新的自定义函数fib(n) *)
fib::usage = "这个函数是通过Fibonacci数列的递推关系式定义的"; (* 对自定义函数的用法说明 *)
fib[1] = fib[2] = 1; (* 给定2个初始项的值 *)
fib[200]; (* 计算第200项的值 *)

提示：在Mathematica的Wolfram语言中，“=”表示赋值，“==”表示相等，“:=”表示符号的定义。

只要问题可解，按这种逐个递推的笨方法总能够推算出任意的特定项，即使所给的递推式没有明显的通项公式求法。

通过内置命令求特定项

使用内置命令求解第100个Fibonacci数：

Fibonacci[100];

使用内置命令求解第100个卢卡斯数：

LucasL[100];

Mathematica在2008年推出的7.0版本中引入了可以按递推关系式求出一连串项的“RecurrenceTable”命令，其语法格式为：

RecurrenceTable[eqns, expr, {n, nmax}]; (* 以求解递归方程 eqns 为基础，产生一组关于连续 n 的 expr 的值的列表 *)
RecurrenceTable[eqns, expr, nspec]; (* 在 nspec 指定的 n 值范围上，产生一组 expr 的值 *)
RecurrenceTable[eqns, expr, {n1, …}, {n2, …}, …]; (* 为连续的 n1，n2，… 产生 expr 的数组值 *)

根据递推关系式求解前几个Fibonacci数的示例：

RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a, {n, 10}];

提示：注意区分Wolfram语言中的赋值号“=”和相等号“==”。

提示：如果RSolve命令没有输入错误，但是执行后出现“RSolve::deqn: Equation or list of equations expected instead of True in the first argument True.”一类的报错信息，一般是由于没有清除同名标识符中的已有信息。如果是这种情况：(1)可以先在其它地方输入独立命令“ClearAll[a]”清除标识符a中的内容，然后重新执行RSolve命令；(2)也可以改用除a以外的其它未使用过的标识符来命名要求解的数列。

通过内置命令求通项

Mathematica在2003年推出的5.0版本中引入了可以求递推关系式一般项表达式的“RSolve”命令，其语法格式为：

RSolve[eqn, a[n], n]; (* 求解递推方程 a[n] *)
RSolve[{eqn1, eqn2, …}, {a1[n], a2[n], …}, n]; (* 求解一个递推方程组 *)
RSolve[eqn, a[n1, n2, …], {n1, n2, …}]; (* 求解一个部分递推方程 *)

求解差分方程$a_{n+1}-2a_{n}=1$的示例：

RSolve[a[n+1] - 2 a[n] == 1, a[n], n];

包括边界条件的求解示例：

RSolve[{a[n+1] - 2 a[n] == 1, a[0] == 1}, a[n], n];

相关例题1： 已知数列$\{a_{n}\}$满足$a_{1}=1,a_{2}=3,a_{n+2}-2a_{n+1}-a_{n}=0$，使用Mathematica求它的通项公式。

解答：
在Mathematica软件中输入命令（因为只有一行命令，分号此时可以不写）：
RSolve[{a[n + 2] - 2 a[n + 1] - a[n] == 0, a[1] == 1, a[2] == 3}, a[n], n];
然后按组合键Shift + Enter即可得到结果为：$a_{n}={\frac {1}{2}}((1-{\sqrt {2}})^{n}+(1+{\sqrt {2}})^{n})$。

答案：$a_{n}={\frac {1}{2}}((1-{\sqrt {2}})^{n}+(1+{\sqrt {2}})^{n})$。

相关例题2： 已知数列$\{a_{n}\}$满足$a_{1}=1,a_{2}=1,a_{n+2}=a_{n+1}-2a_{n}+3$，使用Mathematica求它的通项公式。

解答：
在Mathematica软件中输入命令：
RSolve[{a[n + 2] == a[n + 1] + 2 a[n] + 3, a[1] == 1, a[2] == 1}, a[n], n]
然后按组合键Shift + Enter即可得到结果为：$a_{n}={\frac {5\times 2^{n}-5\times (-1)^{n}-9}{6}}$。

答案：$a_{n}={\frac {5\times 2^{n}-5\times (-1)^{n}-9}{6}}$。

补充习题