【线性代数】k阶常系数线性递推方程

前言#

之前我们在矩阵专栏里面讲了线性 DP 优化，可以把$O(n)$的递推转移优化到天才的$O(k^3\log n)$，但是这种只能优化类似于$h_n = 5h_{n-1} + 6h_{n-2}$这种范围不太大的线性递推方程（其构成的整体叫做数列)，而且由于$k$是立方，如果矩阵太大，说不定还不如$O(n)$（$k$在 300 的立方就已经超时了)。所以我们能不能归纳出一个公式呢？直接变成$O(1)$！当然是可以的，这就是我们今天要将的k阶常系数线性递推。

补充说明一下，上面说的$O(1)$只是一种情况，因为我们把情况推广到了k阶常系数线性递推，所以具体优化程度要看方程是什么样子的，比如可以把$O(n^2)$优化到$O(n)$也是其中一种。

k 阶常系数线性递推方程#

概念#

什么是数列#

数列是一组按照一定规律排列的数字序列，其中每个数字称为序列的项。数列在数学中广泛用于建立模型、描述变化以及解决各种实际问题。数列可以是有限的（包含有限个项）或无限的（包含无限个项）。

数列的一般形式可以表示为：

$a_1, a_2, a_3, \ldots, a_n, \ldots$

其中，$a_n$ 表示数列的第 n 项。数列中的项可以是实数、复数或其他数值类型。

数列的种类和性质多种多样，根据项之间的规律，可以将数列分为不同的类型，如等差数列、等比数列、斐波那契数列等。以下是一些常见的数列类型：

1. 等差数列（Arithmetic Sequence）： 在等差数列中，每一项与前一项的差值都是相同的常数，称为公差。例如，$2, 5, 8, 11, \ldots$ 就是一个公差为 3 的等差数列。

2. 等比数列（Geometric Sequence）： 在等比数列中，每一项与前一项的比值都是相同的常数，称为公比。例如，$3, 6, 12, 24, \ldots$ 就是一个公比为 2 的等比数列。

3. 斐波那契数列（Fibonacci Sequence）： 斐波那契数列是一种特殊的数列，其中每一项是前两项之和。通常以 $F_1 = 1$ 和 $F_2 = 1$ 作为起始项，然后依次为 $1, 1, 2, 3, 5, 8, \ldots$。

4. 调和数列（Harmonic Sequence）： 调和数列的每一项是其倒数的和。例如，$1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots$ 就是一个调和数列。

我们这里研究的递推方程所构成的整体都是一个数列，正如斐波那契数列一样，它们是特殊的数列，有自己的递推方程，在一般情况下，我们称作”k 阶常系数线性齐次递推”。

什么是”k 阶常系数线性齐次递推”#

“k 阶常系数线性齐次递推” 是一个数学术语，用来描述一个特定类型的递推关系。

递推关系： 是一个数列中的每一项都是前面某几项的函数，通常用一个递推式来表示。递推式可以是线性的，也可以是非线性的。

齐次递推关系： 是指递推式右边等于零的情况，即没有外部驱动力，数列只受自身前几项的影响。这可以表示为一种自我包含的数学模型。

常系数： 表示递推式中的系数是常数，即不随着数列的变化而变化。

k 阶 指的是递推式中涉及到的项与其前面的 k 项相关。

所以，“k 阶常系数线性齐次递推” 也就是指一个数列满足一个线性的、齐次的、常系数递推关系，其中每一项与其前面的 k 项有关。这种递推关系可以表示为：

$a*n = c_1 a*{n-1} + c*2 a*{n-2} + \ldots + c*k a*{n-k} + f(n)$

其中，$a_n$ 表示数列的第 $n$ 项，$c_1, c_2, \ldots, c_k$ 是常数系数，$a_{n-1}, a_{n-2}, \ldots, a_{n-k}$ 是数列的前 $k$ 项。

最后的$f(n)$可以是一个常数或者多项式，如果$g_n$等于 0，那么最后移项得到的递推式右边就是零，也就是满足齐次递推关系。

解这种递推关系通常涉及找到递推式的通解，从而得到数列的通项公式。这可以通过使用代数、数学归纳法等方法来实现。

我们今天就是讲讲如何用代数方法求出这个所谓的通项公式。

齐次情况#

我们先来分析常系数和齐次的情况，也就是最后的$g_n$为零的情况，那么对于一个 k 阶常系数线性齐次递推关系，我们可以假设它的通解是一个指数形式，然后把这个带入递推方程，最后得到一个特征方程。

无重根时#

对于一个 k 阶常系数线性齐次递推关系：

其特征方程可以通过假设数列的通解具有指数形式，然后代入递推关系来得到。

假设数列的通解形式为：

代入递推关系得到：

将上述方程整理为零等式：

这个零等式称为特征方程。解这个特征方程，即找到它的根（也称为特征根），将会揭示递推关系的解的性质。（这就是我们之前说的是指递推式右边等于零的情况）

但请注意，特征方程的根可能是实数也可能是复数，具体取决于递推关系中的常数系数。解特征方程后，通解可以表示为特征根的线性组合。

需要注意的是，在某些情况下，特征方程可能有重复根（以下简称重根），这可能会导致解的形式稍有不同。解特征方程并找到相应的通解是解决 k 阶常系数线性齐次递推关系的关键步骤之一。关于重根的解决方案这里先按下不表，我们可以在后面用导数解决。

求特征根与通解#

比如我们前言中说的 $h_n - 5h_{n-1} + 6h_{n-2} = 0$，我们可以按照之前提到的方法来找到其通解。

首先，写出特征方程，我们假设通解具有指数形式：

$r^n - 5r^{n-1} + 6r^{n-2} = 0$

然后，尝试解特征方程以找到特征根 $r$。我们将特征方程分解为 $(r - 2)(r - 3) = 0$，我们得到两个特征根：$r_1 = 2$ 和 $r_2 = 3$。

现在，我们可以使用这些特征根来构建通解。递推关系的通解是特征根的线性组合，即：

$h(n) = \sum_{i} A_i \cdot r_i^n$

那么对于这个式子来说，通解的一般形式为：

$h_n = A \cdot r_1^n + B \cdot r_2^n$

代入特征根 $r_1 = 2$ 和 $r_2 = 3$，我们可以得到以下通解：

$h_n = A \cdot 2^n + B \cdot 3^n$

这就是 $h_n - 5h_{n-1} + 6h_{n-2} = 0$ 的通解。我们可以根据初始条件（例如$h_1$和$h_2$）来确定常数 $A$ 和 $B$ 的值，从而得到特定的数列解。

总结一下，也就是对于 $h_n - 5h_{n-1} + 6h_{n-2} = 0$ 这个递推关系方程来说，其转化后的特征方程的解为特征根 $r_1 = 2$ 和 $r_2 = 3$，通解为 $h_n = A \cdot 2^n + B \cdot 3^n$，其中 $A$ 和 $B$ 是待定常数，可以通过初始条件来确定。

那么假设 $h_1 = 2$ ， $h_2 = 5$，求解过程如下：

1. 当 $n = 1$ 时，根据初始条件 $h_1$：

$h_1 = A \cdot 2^1 + B \cdot 3^1$

2. 当 $n = 2$ 时，根据初始条件 $h_2$：

$h_2 = A \cdot 2^2 + B \cdot 3^2$

现在我们有一个包含两个方程（一个针对 $h_1$，另一个针对 $h_2$）和两个未知数（$A$ 和 $B$）的线性方程组。我们可以用这个线性方程组来解常数 $A$ 和 $B$：

1. 根据 $h_1$ 的初始条件，$h_1 = 2$：

$2 = 2A + 3B$

2. 根据 $h_2$ 的初始条件，$h_2 = 5$：

$5 = 4A + 9B$

解方程组后，我们就可以得到 $A$ 和 $B$ 的值，然后将它们代入通解 $h_n = A \cdot 2^n + B \cdot 3^n$ 中，从而得到特定的数列解。（求解得 $A = -1; B = 1$)

这样我们就把原矩阵快速幂中的$k^3$优化了，只剩下了快速幂的$O(\log n)$，这在 $k$ 极大时是很有效的。

有重根时#

当特征方程有重复的特征根时，情况会有所不同，让我们通过一个具体的例子来说明如何处理。考虑以下的齐次递推关系：

$h_n - 4h_{n-1} + 4h_{n-2} = 0$

首先，我们写出特征方程并求解特征根：

$r^2 - 4r + 4 = 0$

这是一个重复特征根的情况，可以因式分解为 $(r - 2)^2 = 0$，因此有一个重复的特征根 $r = 2$。

现在，我们写出新的特征解，我们把它叫做对应的齐次解（在一般情况下，特征解所对应的齐次解就是它本身），那么递推关系的通解是所有齐次解的线性组合，即： $h(n) = \sum_{i} (A_{1i} + A_{2i} n + A_{3i} n^2 + \ldots) \cdot r_i^n$

对于当前情况来说，就是下面的样子：

$h_{h_2}(n) = (A_1 + A_2 n) \cdot 2^n$

这里，我们引入了多项式项 $A_1 + A_2 n$，其中 $A_1$ 和 $A_2$ 是待定常数。

最后，我们写出通解，将原特征根和齐次解结合：

$h(n) = h_{h_2}^{(1)}(n) + h_{h_2}^{(2)}(n) = (A_1 + A_2 n) \cdot 2^n + B \cdot 2^n$

这就是考虑了重复特征根的递推关系的通解。通解中包含了一个多项式项和一个指数项，分别对应于重复特征根的齐次解和原特征根。

要确定待定常数 $A_1, A_2$ 和 $B$，我们可以使用初始条件。例如，如果我们知道初始条件 $h_0 = 1$ 和 $h_1 = 4$，可以将这些值代入通解中，然后解方程组来求解待定常数。

非齐次情况#

说完齐次情况，我们来说说非齐次情况，也就是$f(n)$不为零的时候。

叠加原理#

需要注意的是，k 阶常系数线性递推方程具有一个叠加原理，这是因为线性方程的性质导致了这种叠加性质。

考虑一个 k 阶常系数线性递推方程，形式如下：

$a_k h_n + a_{k-1} h_{n-1} + \ldots + a_1 h_{n-k+1} + a_0 h_{n-k} = f(n)$

其中，$a_k, a_{k-1}, \ldots, a_1, a_0$ 是常数系数，$g_n$ 是非齐次项（可能是已知函数或数列）。

叠加原理表明，如果我们有两个线性递推方程：

$a_k h_n^{(1)} + a_{k-1} h_{n-1}^{(1)} + \ldots + a_1 h_{n-k+1}^{(1)} + a_0 h_{n-k}^{(1)} = f(n)^{(1)}$

和

$a_k h_n^{(2)} + a_{k-1} h_{n-1}^{(2)} + \ldots + a_1 h_{n-k+1}^{(2)} + a_0 h_{n-k}^{(2)} = f(n)^{(2)}$

那么这两个方程的和也是一个满足叠加原理的方程：

$a_k (h_n^{(1)} + h_n^{(2)}) + a_{k-1} (h_{n-1}^{(1)} + h_{n-1}^{(2)}) + \ldots + a_1 (h_{n-k+1}^{(1)} + h_{n-k+1}^{(2)}) + a_0 (h_{n-k}^{(1)} + h_{n-k}^{(2)}) = f(n)^{(1)} + f(n)^{(2)}$

这意味着，如果我们有两个递推方程及其相应的非齐次项，我们可以将这两个方程相加，从而得到一个新的递推方程，其非齐次项是原来两个方程的非齐次项的和。

这种叠加原理在解决复杂问题时非常有用，因为它允许我们将问题分解为更简单的部分，然后将这些部分的解组合在一起——这个就是我们破获非齐次状态的关键。

解决方式#

联系之前的叠加原理，我们进行逆操作求解：首先把原来的递推方程分成两份，找到对应齐次递推关系的通解，然后再找到非齐次项的特解。将齐次解和非齐次特解相加，就可以得到非齐次递推关系的通解。

1. 找到齐次递推关系的通解： 首先，忽略非齐次项，找到对应的齐次递推关系的通解。这可以通过之前提到的特征解法来完成，其中需要解特征方程并得到齐次解。假设齐次递推关系的通解为 $h_h(n)$。

2. 找到非齐次项的特解： 现在，考虑非齐次项。根据非齐次项的形式，选择一个合适的特解形式。这可以通过待定系数法来完成，假设非齐次项的特解为 $h_p(n)$。

3. 写出非齐次递推关系的通解： 非齐次递推关系的通解是齐次解和非齐次特解的和，即 $h(n) = h_h(n) + h_p(n)$。

总结起来，求解非齐次的常系数线性递推关系的通解需要分别找到对应齐次递推关系的通解和非齐次项的特解，然后将它们通过叠加原理相加。在找到特解时，通常需要根据非齐次项的形式和问题的性质来选择适当的特解形式。这种方法适用于解决一般形式的非齐次递推关系。

回到之前的题目，我们可以将给定的齐次递推关系 $h_n - 5h_{n-1} + 6h_{n-2} = 0$ 加上一个常数项 $c$，得到非齐次递推关系：

$h_n - 5h_{n-1} + 6h_{n-2} = c$

现在，让我们按照之前的步骤来求解这个非齐次递推关系的通解。

1. 找到齐次递推关系的通解： 首先，考虑齐次部分 $h_n - 5h_{n-1} + 6h_{n-2} = 0$。我们已经知道其特征方程是 $r^2 - 5r + 6 = 0$，可以分解为 $(r - 2)(r - 3) = 0$，得到特征根 $r_1 = 2$ 和 $r_2 = 3$。因此，齐次递推关系的通解是： $h_h(n) = A \cdot 2^n + B \cdot 3^n$

2. 找到非齐次项的特解： 现在考虑非齐次项 $c$。由于这是一个常数项，我们可以选择特解为一个常数，即 $h_p(n) = D$，其中 $D$ 是待定常数。

3. 写出非齐次递推关系的通解： 非齐次递推关系的通解是齐次解和非齐次特解的和，即： $h(n) = h_h(n) + h_p(n) = A \cdot 2^n + B \cdot 3^n + D$

这就是带有常数项的非齐次递推关系的通解。在确定待定常数 $A, B$ 和 $D$ 时，我们同样可以使用初始条件来求解。将初始条件代入通解中，解方程组来确定这些常数，从而得到特定的数列解。

非常系数#

特征解法虽然比较万能，但是在处理特定形式的非齐次项时可能会比较麻烦，特别是当非齐次项的形式比较复杂或者无法与齐次解相关联的情况。

而对于非常系数的线性递推关系，特别是当非齐次项具有一般形式时，生成函数是一种非常强大的工具，可以用来解决问题。生成函数可以将递推关系转化为代数方程，从而更容易地求解非齐次递推关系的通解。

因此关于非常系数的线性递推关系的解法，此篇暂时按下不表，待以后讲生成函数时再详细解释其解法。