关于线性递推数列 · Shun Li's Notes

整理一些二阶线性递推数列相关的内容。

通项公式推导（线性代数方法）

Problem

推导二阶线性递推数列的通项公式。（基于线性代数视角）

Solution

考虑二阶线性递推数列

Copy LaTeX

其中系数 $c_0,c_1$ 给定，初值 $a_0,a_1$ 给定。将其改写为矩阵形式

Copy LaTeX

因此通项公式

Copy LaTeX

我们需要处理矩阵的 $n$ 次幂 $M^n$ ，将其整理为更具体的形式：

如果二阶矩阵 $M$ 可以相似对角化，那么
$Copy LaTeX$
此时通项公式为
$Copy LaTeX$
否则 $M$ 必然有重特征值 $\lambda_1 = \lambda_2 = \lambda$ ，并且
$Copy LaTeX$
此时通项公式为
$Copy LaTeX$

Remark

这里的一般模型用线性代数写起来非常漂亮，但是实际还需要繁琐的具体计算才能得到实际的结果。

Remark

对递推公式涉及的如下形式的二阶矩阵

Copy LaTeX

只可能存在两种情况：

有两个不同的特征值，可以相似对角化；
有两个相同的特征值，不可以相似对角化。

不存在第三种情况——有两个相同特征值且可以相似对角化，因为这种情况当且仅当矩阵为对角阵

Copy LaTeX

通项公式推导（初等方法）

Problem

推导二阶线性递推数列的通项公式。（基于高中数学）

Solution

考虑二阶线性递推数列

Copy LaTeX

其中系数 $c_0,c_1$ 给定，初值 $a_0,a_1$ 给定。

首先考虑凑一个等比数列：取常数 $p,q$ 希望满足

Copy LaTeX

与原式比较可得

Copy LaTeX

因此 $p$ 和 $q$ 为如下一元二次方程的两个根（如果存在的话）：

Copy LaTeX

这个方程被称为二阶线性递推数列的特征方程。（由此也可以看出， $p,q$ 其实地位是相等的，可以互换）

假设 $\Delta = c_0^2 + 4 c_1 \neq 0$ ，那么存在两个不等的根 $x_1,x_2$ （允许复根），可以分别取 $p = x_1$ 和 $q = x_2$ （我们不妨假设 $q \neq 0$ ，便于下文用 $q$ 作为分母）。定义

Copy LaTeX

那么 $\{b_n\}$ 是公比为 $q$ ，首项 $b_1 = a_1 - p a_0$ 的数列，进而得到

Copy LaTeX

因此 $\{a_n\}$ 满足

Copy LaTeX

变形得到

Copy LaTeX

继续凑一个等比数列：取常数 $\varepsilon$ 使得

Copy LaTeX

解得

Copy LaTeX

因此对于 $n \geqslant 0$ ，有

Copy LaTeX

上式对于 $n = -1$ 同样成立，因此通项公式为

Copy LaTeX

考虑退化情形 $\Delta = c_0^2 + 4 c_1 = 0$ ，此时两个根相等，只能取 $p = q = x_{1} = x_2$ ，得到

Copy LaTeX

因此

Copy LaTeX

$\{b_n\}$ 是公比为 $q$ ，首项 $b_1 = a_1 - q a_0$ 的数列，进而得到

Copy LaTeX

因此 $\{a_n\}$ 满足

Copy LaTeX

这里有一个平凡的退化情形 $p=q=0$ ，此时显然有 $c_0=c_1=0$ ，因此 $a_n = 0, \, n \geqslant 2$ 。下面不妨设 $q \neq 0$ ，变形得到

Copy LaTeX

此时我们无法重复非退化情形的做法：找到 $\varepsilon$ 进行进一步构造，但是存在更简单的做法：因为此时 $\{\frac{a_n}{q^n}\}$ 是等差数列，可以直接得到

Copy LaTeX

因此

Copy LaTeX

这里还存在一个特殊情况： $q=1$ ，此时 $a_n$ 恰好是一个等差数列。

我们默认初值和递推系数均为实值，这里还需要特别关注 $\Delta = c_0^2 + 4 c_1 < 0$ 的情形，因为此时涉及到复数，但是数列元素必然是实值的。设 $p,q$ 是一对共轭复根，记

Copy LaTeX

代入可知两个系数互为共轭，并且

Copy LaTeX

不妨记作

Copy LaTeX

那么

Copy LaTeX

因此

Copy LaTeX

如果 $p$ 的幅角 $\theta$ 满足 $\pi/\theta$ 为有理数，那么 $\frac{a_n}{r^n}$ 是一个周期数列。这里的 $r,\theta$ 可以直接从递推系数计算

Copy LaTeX

也可以反过来用 $r,\theta$ 表示递推关系

Copy LaTeX

此时

Copy LaTeX

这实际对应的是

Copy LaTeX

这是三角函数的一个积化和差公式。

总结：对于二阶线性递推数列，通项公式形如

Copy LaTeX 是特征方程的两个不相等的根 是特征方程的重根且不为 是特征方程的重根

其中 $C_1,C_2$ 可以通过两个初值确定。如果特征方程有一对共轭复根 $p,q$ ，那么有如下三角函数模型

Copy LaTeX

其中 $r,\theta$ 可以直接从递推系数计算

Copy LaTeX

剩下的两个参数 $A,\phi$ 由初值确定。如果虚根的幅角是 $\pi$ 的有理倍数， $\frac{a_n}{r^n}$ 还是一个周期数列。

Example

考虑著名的斐波那契数列

Copy LaTeX

Solution

特征方程

Copy LaTeX

解得

Copy LaTeX

因此通项公式形如

Copy LaTeX

系数 $C_1,C_2$ 由初值决定。通常有两种初值设置： $a_0=a_1=1$ ， $a_1=a_2=1$ ，代入解出对应的系数即可。

Example

考虑线性递推数列

Copy LaTeX

Solution

特征方程

Copy LaTeX

解得

Copy LaTeX

因此通项公式形如

Copy LaTeX

系数 $C_1,C_2$ 由初值决定。

Example

考虑线性递推数列

Copy LaTeX

Solution

特征方程

Copy LaTeX

解得

Copy LaTeX

因此通项公式形如

Copy LaTeX

系数 $A,\phi$ 由初值决定。

例如 $a_0 = a_1 = 1$ ，直接计算得到整个数列如下

Copy LaTeX

出现了明显的长度为 $6$ 的循环节。代入上述公式可以得到 $A=\frac{2}{\sqrt{3}}$ ， $\phi = -\frac{\pi}6$ ，因此通项公式

Copy LaTeX

补充：给二阶线性递推数列加点扰动

对于二阶线性递推数列

Copy LaTeX

显然有

Copy LaTeX

求和即可得到通项公式，显然数列 $\{x_n\}$ 存在指数级增长

Copy LaTeX

我们考虑把递推关系中的 $r$ 变成某个有界数列 $|r_n| \leqslant C$ ，此时上述通项公式的推导不再成立，但是 $q^n$ 指数级增长的量级估计仍然成立：记

Copy LaTeX

那么

Copy LaTeX

因此

Copy LaTeX

得到了增长的上界控制

Copy LaTeX

也可以换一个方向进行部分求和：取 $m \geqslant 1$

Copy LaTeX

得到

Copy LaTeX

整理得到

Copy LaTeX

因此

Copy LaTeX

得到了增长的下界控制。综上，数列 $\{x_n\}$ 仍然近似存在着 $q^n$ 量级的倍数增长。

Problem

已知数列 $\{x_n\}$ 满足

Copy LaTeX

并且

Copy LaTeX

其中 $1 < p < q$ 。求证：数列 $\{x_n\}$ 一致有界，即存在常数 $C$ 使得 $\lvert x_n \rvert \leqslant C$ 。

Proof

由前面的推导可知，我们仍然可以得到对 $\{x_n\}$ 的指数级增长估计

Copy LaTeX

但是题目给出了一个底数更小的指数级增长控制

Copy LaTeX

要求我们用这两个条件证明数列有界，即不可能存在指数级增长。

直接代入第二个估计可以得到

Copy LaTeX

除以 $q^m$ 并整理可得

Copy LaTeX

直接令 $m \to \infty$ ，即可得到

Copy LaTeX

因此数列 $\{x_n\}$ 一致有界。