【组合数学】递推方程 ( 递推方程解与特征根之间的关系定理 | 递推方程解的线性性质定理 | 递推方程解的形式 )

2023-03-28 18:29:16 浏览数 (5)

文章目录

  • 一、递推方程解与特征根之间的关系定理
  • 二、递推方程解的线性性质定理
  • 三、递推方程解的形式

一、递推方程解与特征根之间的关系定理

特征根 与 递推方程的解 之间是存在关系的 , 如果知道了这个内在联系 , 就可以 根据特征根 , 写出递推方程的解的模式 , 即 通解 ;

递推方程解与特征根相关定理 :

q

是非

0

复数 , 则有以下等价关系 :

q

是特征方程的特征根

Leftrightarrow
q^n

是递推方程的解 ★

证明上述定理 :

按照定义 , 将 递推方程的解

q^n

, 代入原来的递推方程 ,

递推方程的解是

q^n

, 代表了 第

n

项的值是

q^n

, 即

H(n) = q^n

;

递推方程 :

H(n) - a_1H(n-1) - a_2H(n-2) - cdots - a_kH(n-k) = 0

,

  • 第
n

项

H(n)

的值是

q^n
  • 第
n-1

项

H(n-1)

的值是

q^{n-1}
  • 第
n-2

项

H(n-2)

的值是

q^{n-2}
vdots
  • 第
n-k

项

H(n-k)

的值是

q^{n-k}

代入后结果是 :

q^n

是递推方程的解

Leftrightarrow q^n - a_1q^{n-1} - a_2q^{n-2} - cdots - a_kq^{n-k} = 0

将

q^{n-k}

作为公因式提取出来 ;

Leftrightarrow q^{n-k} ( q^k - a_1q^{k-1} - a_2q^{k-2} - cdots - a_k ) = 0

上述两个乘积为

0

,

q^{n-k}

肯定不为

0

, 则剩余部分结果是

0

;

Leftrightarrow q^k - a_1q^{k-1} - a_2q^{k-2} - cdots - a_k = 0

上述方程 , 正好是特征方程 , 该特征方程的解 , 就是特征根

q

;

Leftrightarrow
q

是特征根

二、递推方程解的线性性质定理

递推方程解的线性性质定理 :

h_1(n)

和

h_2(n)

都是同一个递推方程的解 ,

c_1 , c_2

是任意常数 ,

使用这两个解作 线性组合 ,

c_1h_1(n) c_2h_2(n)

, 这个线性组合也是递推方程的解 ;

证明方法 :

将

c_1h_1(n) c_2h_2(n)

组合代入递推方程的左边式子中 , 化简后为

0

;

递推方程 :

H(n) - a_1H(n-1) - a_2H(n-2) - cdots - a_kH(n-k) = 0

,

将

c_1h_1(n) c_2h_2(n)

线性组合代入上述方程 ,

H(n)

使用

c_1h_1(n) c_2h_2(n)

代替

H(n-1)

使用

c_1h_1(n-1) c_2h_2(n-1)

代替

H(n-2)

使用

c_1h_1(n-2) c_2h_2(n-2)

代替

H(n-k)

使用

c_1h_1(n-k) c_2h_2(n-k)

代替

得到 :

(c_1h_1(n) c_2h_2(n))
-
a_1(
c_1h_1(n-1) c_2h_2(n-1)
) - a_2
(c_1h_1(n-2) c_2h_2(n-2))
- cdots - a_k(
c_1h_1(n-k) c_2h_2(n-k)
) = 0

将所有含有

c_1h_1

的项合并到一起 , 将所有含有

c_2h_2

的项 , 合并到一起 , 得到 :

c_1( h_1(n) - a_1h_1(n-1) - a_2h_1(n-2) - cdots - a_kh_1(n-k))
c_2( h_2(n) - a_1h_2(n-1) - a_2h_2(n-2) - cdots - a_kh_k(n-k))
= 0

上述式子中 蓝色部分 和 红色部分 分别都是

0
h_1(n)

是递推方程的解 , 因此

c_1( h_1(n) - a_1h_1(n-1) - a_2h_1(n-2) - cdots - a_kh_1(n-k))

的值为

0

;

h_2(n)

是递推方程的解 , 因此

c_2( h_2(n) - a_1h_2(n-1) - a_2h_2(n-2) - cdots - a_kh_k(n-k))

的值为

0

;

三、递推方程解的形式

将之前将的 “递推方程解与特征根之间的关系定理” 与 “递推方程解的线性性质定理” 结合在一起 , 就可以 根据特征根 , 将递推方程的解写出来 ;

假定

q_1 , q_2 , cdots , q_k

是递推方程的特征根 , 一元

k

次方程有

k

个根 ;

根据 “递推方程解与特征根之间的关系定理” ,

q_1^n, q_2^n , cdots , q_k^n

都是递推方程的解 ,

将这

k

个解 , 作线性组合 ,

c_1q_1^n c_2q_2^n cdots c_kq_k^n

,

根据 “递推方程解的线性性质定理” , 上述线性组合

c_1q_1^n c_2q_2^n cdots c_kq_k^n

也是递推方程的解 ;

此时找到了递推方程的解的一种形式 ;

总结下过程 :

  • 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是
0

;

  • 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;
  • 特征方程次幂数 : 最高次幂是 特征方程项数
-1

, 最低次幂

0

;

  • 写出 没有系数 的特征方程 ;
  • 逐位将递推方程的系数 抄写 到特征方程中 ;
  • 解特征根 : 将 特征方程的特征根解出来 ,
x = cfrac{-b pm sqrt{b^2 - 4ac}}{2a}
  • 构造递推方程的解 : 构造
c_1q_1^n c_2q_2^n cdots c_kq_k^n

形式的线性组合 , 该线性组合就是递推方程的解 ;

满足

H(n) - a_1H(n-1) - a_2H(n-2) - cdots - a_kH(n-k) = 0

公式的所有递推方程 , 都具有

c_1q_1^n c_2q_2^n cdots c_kq_k^n

形式的解 ;

数学

0 人点赞