常系数线性递推的线性代数推导

  // 这不是竞赛里那个多项式取模的东西，是离散课本里的特征根法
  抱着在离散课装逼的心态挖了这个坑，填了两个星期

  “推导”和“证明”这两个概念是有区别的，后者只是证明了这些结论是对的，而前者则是要说明它们的来源。但是到了“无重根”的部分，似乎我也无法完成“推导”而只能转向“证明”了。如果有 dalao 不吝赐教，我将不胜感激。

1. 递推中的线代

1.1 递推的本质

  考虑斐波那契数列 $f_n=f_{n-1}+f_{n-2}$，我们构造一个向量 $\vec v=\begin{bmatrix}f_{n-1} \\ f_{n-2}\end{bmatrix}$，把它乘一个矩阵 $A=\begin{bmatrix}1&1 \\ 1&0\end{bmatrix}$，会得到什么呢？

$$A\vec v=\begin{bmatrix}1&1 \\ 1&0\end{bmatrix}\begin{bmatrix}f_{n-1} \\ f_{n-2}\end{bmatrix}=\begin{bmatrix}f_{n-1}+f_{n-2} \\ f_{n-1}\end{bmatrix}=\begin{bmatrix}f_n \\ f_{n-1}\end{bmatrix} \tag 1$$

  会发现 $f$ 的下标往前推进了一位！这就产生了递推。

  事实上，对于递推关系 $f_n=\sum_{i=1}^k a_if_{n-i}$，都可以这样写：

$$A\vec v= \begin{bmatrix} a_1 & a_2 & \cdots & a_{k-1} & a_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix} \begin{bmatrix}f_{n-1} \\ f_{n-2} \\ f_{n-3}\\ \vdots \\ f_{n-k}\end{bmatrix} =\begin{bmatrix}\sum_{i=1}^k a_if_{n-i} \\ f_{n-1} \\ f_{n-2}\\ \vdots \\ f_{n-k+1}\end{bmatrix} =\begin{bmatrix}f_{n} \\ f_{n-1} \\ f_{n-2}\\ \vdots \\ f_{n-k+1}\end{bmatrix} \tag 2$$

  这个 $A$ 矩阵叫做转移矩阵。如果给定了前 $k$ 项的值 $f_0$~$f_{k-1}$，则可以构造初始向量 $\vec{v_0}=\begin{bmatrix}f_{k-1} \\ f_{k-2} \\ \vdots \\ f_0\end{bmatrix}$，那么 $A\vec{v_0}$ 就可以得到 $\begin{bmatrix}f_{k} \\ f_{k-1} \\ \vdots \\ f_1\end{bmatrix}$，$A^n\vec{v_0}$ 就可以得到 $\begin{bmatrix}f_{n+k-1} \\ f_{n+k-2} \\ \vdots \\ f_n\end{bmatrix}$。也就是说，如果我们要求 $f_n$，只需要求 $A^n\vec{v_0}$，然后拿最底下那个元素就可以了。

1.2 解的线性性与解空间

  若数列 $\{f_n\}$ 满足递推关系 $f_n=\sum_{i=1}^k a_if_{n-i}$，则称数列 $\{f_n\}$ 为该递推的一个解。显然，有如下性质：

1. 若 $\{f_n\}$ 为一个解，则对任意常数 $c$，$\{cf_n\}$ 也是一个解；

2. 若 $\{f_n\},\{g_n\}$ 都是解，那么 $\{f_n+g_n\}$ 也是一个解。

  因此，满足该递推关系的解具有线性性。

  只有递推关系的话解有无穷多个。但如果给出了初始向量，那么就可以递推出每一项，解也就唯一确定了，因此解是由初始向量决定的，并且是 one-to-one 的，可以表示为 $\{f_n\}=T(\vec{v_0})$。

  那么只要证明了以下两点，就可以证明这个 $T$ 是线性变换了：

1. $\forall c \in \mathbb{R},~\{cf_n\}=T(c\vec{v_0})$
2. 对于两组初始向量 $\vec{u_0},\vec{v_0}$，有 $T(\vec{u_0})+T(\vec{v_0})=T(\vec{u_0}+\vec{v_0})$

  这两点都可以根据递推关系对 $f_n$ 进行归纳而证得。因此，该变换 $\{f_n\}=T(\vec{v_0})$ 是线性变换。

  而由于 $T$ 是双射的，因此 $\dim(\{f_n\})=\dim(\vec{v_0})=k$，即解空间是 $k$ 维的。

2. 齐次

2.1 特征方程与特征向量

  考虑齐次递推关系 $f_n=\sum_{i=1}^k a_if_{n-i}$，前面说过这等价于求 $A^n\vec{v_0}$。我们来特征一波：

$$\det(A-\lambda I)= \begin{vmatrix} a_1-\lambda & a_2 & \cdots & a_{k-1} & a_k \\ 1 & -\lambda & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & -\lambda \end{vmatrix} \tag 3$$

  按第一行展开，得：

$$\begin{aligned} \det(A-\lambda I)&=(a_1-\lambda)(-\lambda)^{k-1}-a_2(-\lambda)^{k-2}+a_3(-\lambda)^{k-3}+\cdots+a_k \\ &=(-1)^k[\lambda^k-\sum_{i=1}^k a_i\lambda^{k-i}] \end{aligned} \tag 4$$

  因此特征方程为：

$$\lambda^k-\sum_{i=1}^k a_i\lambda^{k-i}=0 \tag 5$$

  这就是递推的特征方程的由来。

  有了特征方程就可以解出特征根，然后就看特征向量，即解 $(A-\lambda I)\vec v=0$。我们给 $A-\lambda I$ （$(3)$ 式）做高斯消元，第 1 行减去第 2 行的 $a_1-\lambda$ 倍，得：

$$\begin{bmatrix} 0 & -\lambda^2+a_1\lambda+a_2 & \cdots & a_{k-1} & a_k \\ 1 & -\lambda & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & -\lambda \end{bmatrix}$$

  再用第 1 行减去第 3 行的 $-\lambda^2+a_1\lambda+a_2$ 倍，重复下去，最终会得到：

$$\begin{bmatrix} 0 & 0 & \cdots & 0 & \lambda^k-\sum_{i=1}^k a_i\lambda^{k-i} \\ 1 & -\lambda & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & -\lambda \end{bmatrix}$$

  代入具体的特征根 $\lambda_i$，第 1 行就全都是 $0$ 了，因此解为 $\vec{x}=c\begin{bmatrix}\lambda^{k-1} \\ \vdots \\ \lambda^2 \\ \lambda \\ 1 \end{bmatrix}$。取 $c=1$ 作为特征向量 $\vec{v_i}$。

2.2 无重根

  现在假设特征方程 $(5)$ 有 $k$ 个不同的实数解 $\lambda_1,\cdots,\lambda_k$，那么就会有对应的 $k$ 个线性无关的特征向量 $\vec{v_1},\cdots,\vec{v_k}$，那么就可以将初始向量表示成特征向量的线性组合：

$$\vec{v_0}=\sum_{i=1}^k\beta_i\vec{v_i} \tag 6$$

  因此：

$$\begin{aligned} A^n\vec{v_0} &=A^n\sum_{i=1}^k\beta_i\vec{v_i} \\ &=\sum_{i=1}^k\beta_iA^n\vec{v_i} \\ &=\sum_{i=1}^k\beta_i\lambda_i^n\vec{v_i} \end{aligned} \tag 7$$

  若只看向量的最底下的元素在这个式子中的计算，$A^n\vec{v_0}$ 的最底下的元素是 $f_n$，$\vec{v_i}$ 的最底下的元素是 $1$，可以得出：

$$f_n=\sum_{i=1}^k\beta_i\lambda_i^n \tag 8$$

  这就得出了齐次线性递推的计算公式。

  如果 $\vec{v_0}$ 是给定的，即给出了初值 $f_0$~$f_{k-1}$，那么可以解线性方程组 $(6)$：

$$\begin{cases} f_0 &= \beta_1+\beta_2+\cdots+\beta_k \\ f_1 &= \beta_1\lambda_1+\beta_2\lambda_2+\cdots+\beta_k\lambda_k \\ \vdots \\ f_{k-1} &= \beta_1\lambda_1^{k-1}+\beta_2\lambda_2^{k-1}+\cdots+\beta_k\lambda_k^{k-1} \end{cases} \tag 9$$

  得到待定系数的 $\beta$ 值。

  如果 $\vec{v_0}$ 不是给定的，那么可以注意到，$\sum_{i=1}^k\beta_i\vec{v_i}$ 实际上表示了任意 $\vec{v_0}$，因为这些特征向量可以线性组合出任意 $k$ 维向量。因此，$(8)$ 式表示了一般解。

  由此又可以得出，$\{f_n|f_n=\lambda_1^n\}$、$\{f_n|f_n=\lambda_2^n\}$、……、$\{f_n|f_n=\lambda_k^n\}$ 都是解，并且是线性无关的，因此是一组基。这就印证了“解空间是 $k$ 维的”这个结论。

2.3 有重根

  有重根的话，就是说特征向量的个数不够 $k$ 个了，不能直接组合出初始向量了。但是解空间依然是 $k$ 维的，因此如果能构造出 $k$ 个线性无关的解，那么就仍然能够推出公式来。

  特征方程 $(5)$ 可以改写为如下特征多项式：

$$\begin{align} p(\lambda)&=\sum_{i=0}^kd_i\lambda^{k-i} \tag{10} \\ &=\prod_i(\lambda-\lambda_i)^{m_i} \tag{11} \end{align}$$

  其中 $d_0=1,~d_i=-c_i(i>1)$。对 $(11)$ 式求导可得下面这个性质：

Lemma 1：若 $\lambda_0$ 为重根，重数为 $m$，则特征多项式 $p(\lambda)=\sum_{i=0}^kd_i\lambda^{k-i}$ 在 $\lambda_0$ 处的 $1$ 至 $m$ 阶导都为 $0$，且 $m+1$ 阶导不为 $0$。

  根据递推关系 $f_n=\sum_{i=1}^k a_if_{n-i}$ 变形可得，数列 $\{f_n\}$ 为一个解当且仅当

$$\sum_{i=0}^k d_if_{n-i}=0 \tag{12}$$

  现假设有特征根 $\lambda$，且为二重根，那么 $\{f_n|f_n=\lambda^n\}$ 是递推关系的一个解。那么有

$$\begin{align} &&\sum_{i=0}^k d_i\lambda^{n-i}&=0 \tag{13} \\ \therefore&& \lambda^{n-k}\sum_{i=0}^k d_i\lambda^{k-i}&=0 \\ \therefore&& \lambda^{n-k}p(\lambda)&=0 \\ \therefore&& \lambda^{n-k+1}p(\lambda)&=0 \tag{14} \end{align}$$

  根据 Lemma 1，这个东西求导还是 $0$，那我给它逐项求导，得

$$\sum_{i=0}^k d_i(n-i+1)\lambda^{n-i}=0 \tag{15}$$

  $(15)$ 式减 $(13)$ 式便得

$$\sum_{i=0}^k d_i(n-i)\lambda^{n-i}=0 \tag{16}$$

  即可得到 $\{f_n|f_n=n\lambda^n\}$ 为一个解。

  如果 $\lambda$ 为三重根，那么可以对 $(16)$ 式做同样操作（两边乘 $\lambda$，求导，然后减去 $(16)$ 式），即可得到 $\{f_n|f_n=n^2\lambda^n\}$ 也是解。如此下去，若 $\lambda$ 为 $m$ 重根，则 $\{f_n|f_n=n^j\lambda^n\}~(0 \leq j < m)$ 都是解。

  也就是说，$m$ 重的特征根可以弄出 $m$ 个解，总共就有 $k$ 个解。这些解的形式是关于 $n$ 的多项式，因此它们仍然是线性无关的。那我们的这组基就做出来了，也就能得到那个解的公式了：

$$f_n=\sum_i(\beta_{i0}+\beta_{i1}n+\cdots+\beta_{i(m_i-1)}n^{m_i-1})\lambda_i^n \tag{17}$$

3. 非齐次

  现在是递推关系 $f_n=\sum_{i=1}^k a_if_{n-i}+P(n)s^n$，其中 $P(n)$ 为关于 $n$ 的多项式，设 $P(n)=\sum_{i=0}^t p_in^i$。

  根据解的线性性，解的形式应当是通解加特解。具体来说，先根据 $(12)$ 式变形有如下性质：

Lemma 2：数列 $\{f_n\}$ 为 $f_n=\sum_{i=1}^k a_if_{n-i}+P(n)s^n$ 的一个解，等价于 $\forall n \geq 0,~\vec v=\begin{bmatrix}f_{n+k} \\ f_{n+k-1} \\ \vdots \\ f_n\end{bmatrix}$ 满足 $\vec{d}\cdot\vec{v}=P(n)s^n$，其中 $\vec d=\begin{bmatrix}d_k \\ d_{k-1} \\ \vdots \\ d_0\end{bmatrix}$

  假设解出了 $f_n=\sum_{i=1}^k a_if_{n-i}$ 的通解 $\{f_n^{(h)}\}$，以及 $f_n=\sum_{i=1}^k a_if_{n-i}+P(n)s^n$ 的特解 $\{f_n^{(p)}\}$，对于 $\forall n \geq 0$，按 Lemma 2 的写法分别写成向量 $\vec{v^{(h)}}$ 和 $\vec{v^{(p)}}$，那么有

$$\begin{align} &&\vec{d}\cdot\vec{v^{(h)}}&=0 \\ &&\vec{d}\cdot\vec{v^{(p)}}&=P(n)s^n \\ \therefore&&\vec{d}\cdot(\vec{v^{(h)}}+\vec{v^{(p)}})&=P(n)s^n \tag{18} \end{align}$$

  因此解的形式为通解加特解。

  通解的解法已经有了，剩下的就是要构造一组特解，满足 $f_n=\sum_{i=1}^k a_if_{n-i}+P(n)s^n$。

  最好的方法，就是跟着它的形式：令 $f_n=Q(n)s^n$，其中 $Q(n)$ 是与 $P(n)$ 同次数的多项式，即 $Q(n)=\sum_{i=0}^t q_in^i$。然后代入递推式解出 $q$值：

$$Q(n)s^n=\sum_{i=1}^ka_iQ(n-i)s^{n-i}+P(n)s^n \tag{19}$$

  但如果 $s$ 是特征根的话，会出现一些问题：设 $s$ 为 $m$ 重根，根据 2.3，会有 $\sum_{i=0}^k d_i(n-i)^j\lambda^{n-i}=0$ 对于 $\forall j\in[0,m)$ 成立，那么会出现 $q_0$~$q_{m-1}$ 被完全消掉了，方程 $(19)$ 变成 $s^kp_tn^t+S(n)=0$（$S(n)$ 表示次数小于 $t$ 的多项式），这显然是不成立的。

  解决方法就是，给 $f_n$ 再乘多些 $n$，变成 $f_n=n^mQ(n)s^n$，把 $n$ 的次数顶上去，顶到 $n^m$ 就相当于 $\sum_{i=0}^k d_i(n-i)^{j+m}\lambda^{n-i}$，这就不会等于 $0$，就不会有系数被消掉了。

4. 参考资料

[1]第二节 常系数线性齐次递推关系 https://wenku.baidu.com/view/50c3348b856a561253d36f43.html