常系数线性齐次递推关系学习笔记

初中的班主任好像生病了,本来准备和同学一起去看望老师,但是好像去不了QAQ
真的很想见一见初中的同学,好想他们呀

阅读这篇文章你所需要的前置技能大概有:基础的线性代数,以及看懂渣叙述的深厚语文功底 =w=
可能有表述不清或者错误的地方,欢迎指正!

定义

$h_{1}, h_{2}, \cdots , h_{n}, \cdots $是一个数列,称这个数列满足k阶线性递推关系是指存在量$a_{1}, a_{2}, \cdots , a_{k}(a_{k} \neq 0)$和量$b_{n}$(这些

量$a_{1}, a_{2}, \cdots a_{k}, b_{n}$可能依赖于$n$),使得

例如斐波那契数列,就是一个典型的满足2阶递推关系的递推式。

如同栗子中所示,我们称线性递推关系是齐次的,如果$b_{n}$是常数0;而我们称它是常系数的,如果量

$a_{1}, a_{2}, \cdots , a_{k}$是常数,形如:

求解

我们求解常系数线性齐次递推关系要依赖于是否能找到与$h_{n}$相关的某个多项式方程的根。

其实求解常系数线性齐次递推关系和微分方程求解的方法极其相似。

我们求解常系数线性齐次递推关系需要依赖一下几个定理。

定理1

定义

设$q$是一个非$0$的数,则$h_{n} = q^{n}$是下面常系数线性齐次递推关系

$h_{n} = a_{1}h_{n - 1} + a_{2}h_{n - 2} + \cdots + a_{k}h_{n - k}(n \geq k, a_{k} \neq 0)$的解,当且仅当$q$是下

面这个多项式方程$x^{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - \cdots - a_{k} = 0$的根。

证明

如果$h_{n} = q^{n}$是下面常系数线性齐次递推关系$h_{n} = a_{1}h_{n - 1} + a_{2}h_{n - 2} + \cdots + a_{k}h_{n - k}(n \geq k, a_{k} \neq 0)$的解,那

么我们将$h_{n} = q^{n}$带入以上常系数线性递推关系,可以得到

若对于所有$n \geq k$,$q^{n} - a_{1}q^{n - 1} - a_{2}q^{n - 2} - \cdots - a_{k}q^{n - k} = 0$都有解($q$有解),则$h_{n} = q^{n}$为常系数线性齐次

递推关系的解。

假设$q \neq 0$,我们可以将等式两边同时消去$q^{n - k}$,因此对于每一个$n \geq k$都有一个的方程最后都会化为:

那我们现在得出了结论若要得出$h_{n} = q^{n}$为递推式的解,当且仅当$q$为多项式方程的解。

现在只需证明$q$为多项式方程的根即可。

因为假设$a_{k} \neq 0$,所以$0$不是多项式方程的根。因此,一定存在$k$个不等于$0$的根$q_{1}, q_{2}, \cdots , q_{k}$(这些根可以是复

数,我也不知道为什么QAQ)。

现在假设这$k$个根互不相同,那么为递推式$k$个不同的解。

而递推关系的线性性齐次性意味着对于任意选定的常数$c_{1}, c_{2}, \cdots, c_{k}$存在,

使得其也为常系数齐次线性递推式的解。

定理2

定义

若多项式方程存在$k$个不同的根$q_{1}, q_{2}, \cdots, q_{k}$,则$h_{n} = c_{1}q_{1}^{n} + c_{2}q_{2}^{n} + \cdots + c_{k}q_{k}^{n}$在下述意义下是

$h_{n} = a_{1}h_{n - 1} + a_{2}h_{n - 2} + \cdots + a_{k}h_{n - k}(n \geq k, a_{k} \neq 0)$的通解:无论给定怎样的初始值$h_{0}, h_{1}, \cdots, h_{k - 1}$,都存

在常数$c_{1}, c_{2}, \cdots, c_{k}$,使得$h_{n} = c_{1}q_{1}^{n} + c_{2}q_{2}^{n} + \cdots + c_{k}q_{k}^{n}$是满足

$h_{n} = a_{1}h_{n - 1} + a_{2}h_{n - 2} + \cdots + a_{k}h_{n - k}(n \geq k, a_{k} \neq 0)$和初始条件的唯一数列。

证明

好了定理1证明完了,那么现在只需要证明$h_{n} = c_{1}q_{1}^{n} + c_{2}q_{2}^{n} + \cdots + c_{k}q_{k}^{n}$在下述意义下是

$h_{n} = a_{1}h_{n - 1} + a_{2}h_{n - 2} + \cdots + a_{k}h_{n - k}(n \geq k, a_{k} \neq 0)$的通解。

我们假设指定初始值:

我们是否能都选出常数$c_{1}, c_{2}, \cdots, c_{k}$($c$在这里相当于未知数)使得$h_{n} = c_{1}q_{1}^{n} + c_{2}q_{2}^{n} + \cdots + c_{k}q_{k}^{n}$中的$h_{n}$满足

上述初始条件,等价于,无论选择怎样的$b_{0}, b_{1}, \cdots , b_{k - 1}$使得下列方程组有解:

我们把方程的系数矩阵表示出来是这样的:

觉不觉得这个矩阵很熟悉,对呀,不就是范德蒙矩阵吗QWQ,而范德蒙矩阵的行列式可表示为(这个就不证明

啦)

当且仅当$q_{1}, q_{2}, \cdots, q_{k}$两两之间互不相同的时候,系数矩阵才不为$0$。而系数矩阵才不为$0$,这也意味着方程组对

于$b_{0}, b_{1}, \cdots, b_{k - 1}$的每一种选择都有唯一解(方程有唯一解(克莱姆法则))。

如果想进一步了解的话可以看n阶行列式

应用

有常系数线性齐次递推式如下,求递推关系

首先我们可以得出递推式的特征方程:

解得:

因此

为常系数线性齐次递推关系的通解。

现在只需要求出常系数$c_{1}, c_{2}, c_{3}$使得方程组成立即可:

解得:

因此,

为原常系数线性齐次递推式的解,相当于原递推式的封闭形式。

参考资料

  1. 《组合数学》 原书第5版 P142
Partager