【组合数学】递推方程 ( 特征方程与特征根 | 特征方程示例 | 一元二次方程根公式 )

一、特征方程与特征根

常系数线性齐次递推方程标准型 :

{ H ( n ) − a 1 H ( n − 1 ) − a 2 H ( n − 2 ) − ⋯ − a k H ( n − k ) = 0 H ( 0 ) = b 0 , H ( 1 ) = b 1 , H ( 2 ) = b 2 , ⋯   , H ( k − 1 ) = b k − 1 \begin{cases} H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0 \\\\ H(0) = b_0 , H(1) = b_1 , H(2) = b_2 , \cdots , H(k-1) = b_{k-1} \end{cases} ⎩⎪⎨⎪⎧​H(n)−a1​H(n−1)−a2​H(n−2)−⋯−ak​H(n−k)=0H(0)=b0​,H(1)=b1​,H(2)=b2​,⋯,H(k−1)=bk−1​​

常系数 是指数列的 项之前的 系数 a 1 , a 2 , ⋯   , a k a_1 , a_2 , \cdots , a_k a1​,a2​,⋯,ak​ 都是常数 , a k ≠ 0 a_k \not=0 ak​​=0 ;

b 0 , b 1 , b 2 , ⋯   , b k − 1 b_0 , b_1, b_2 , \cdots , b_{k-1} b0​,b1​,b2​,⋯,bk−1​ 是 递推方程的 k − 1 k-1 k−1 个初值 ;

写出特征方程 :

x k − a 1 x k − 1 − ⋯ − a k = 0 x^k - a_1x^{k-1} - \cdots - a^k = 0 xk−a1​xk−1−⋯−ak=0

特征方程、递推方程的项数、特征方程的次幂数 :

• 特征方程、递推方程的项数 : 特征方程项的个数 与 常系数线性齐次 递推方程项的个数相同 , 有 k + 1 k+1 k+1 项 ;

• 特征方程的次幂数 : 总共有 k + 1 k+1 k+1 项 , 特征方程项的 x x x 的次幂 从 k k k 到 0 0 0 , 总共有 k + 1 k + 1 k+1 项 ;

递推方程 与 特征方程关系 :

• x k x^k xk 前的系数 1 1 1 对应 H ( n ) H(n) H(n) 项前的系数 1 1 1 ;

• x k − 1 x^{k-1} xk−1 前的系数 − a 1 -a_1 −a1​ 对应 H ( n − 1 ) H(n-1) H(n−1) 项前的系数 − a 1 -a_1 −a1​ ;

⋮ \vdots ⋮

• x 0 x^{0} x0 前的系数 − a k -a_k −ak​ 对应 H ( n − k ) H(n-k) H(n−k) 项前的系数 − a k -a_k −ak​ ;

由 递推方程 : H ( n ) − a 1 H ( n − 1 ) − a 2 H ( n − 2 ) − ⋯ − a k H ( n − k ) = 0 H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0 H(n)−a1​H(n−1)−a2​H(n−2)−⋯−ak​H(n−k)=0

可以导出 1 1 1 元 k k k 次特征方程 : x k − a 1 x k − 1 − ⋯ − a k = 0 x^k - a_1x^{k-1} - \cdots - a^k = 0 xk−a1​xk−1−⋯−ak=0

该 1 1 1 元 k k k 次特征方程 称为 原递推方程的 特征方程 ;

该 1 1 1 元 k k k 次特征方程 有 k k k 个根 , 称为 递推方程 的特征根 ;

由递推方程到特征方程 ( 重点 ) :

• 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是 0 0 0 ;
• 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;
• 特征方程次幂数 : 最高次幂是 特征方程项数 − 1 -1 −1 , 最低次幂 0 0 0 ;
• 写出 没有系数 的特征方程 ;
• 逐位将递推方程的系数 抄写 到特征方程中 ;

解出上述特征方程 , 就可以得到特征根 , 一般都是一元二次方程 ;

一元二次方程形式 a x 2 + b x + c = 0 ax^2 + bx + c = 0 ax2+bx+c=0

解为 : x = − b ± b 2 − 4 a c 2 a x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} x=2a−b±b2−4ac ​​

二、特征方程与特征根 示例 ( 重要 )

1 . 斐波那契数列示例 :

( 1 ) 斐波那契数列 : 1 , 1 , 2 , 3 , 5 , 8 , 13 , ⋯ 1 , 1 , 2 , 3 , 5 , 8 , 13 , \cdots 1,1,2,3,5,8,13,⋯

( 2 ) 递推方程 : F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2) F(n)=F(n−1)+F(n−2)

描述 : 第 n n n 项等于第 n − 1 n-1 n−1 项 和 第 n − 2 n-2 n−2 项之和 ;

如 : 第 4 4 4 项的值 F ( 4 ) = 5 F(4) = 5 F(4)=5 , 就等于

第 4 − 1 = 3 4-1=3 4−1=3 项的值 F ( 4 − 1 ) = F ( 3 ) = 3 F(4-1)=F(3) = 3 F(4−1)=F(3)=3

加上 第 4 − 2 = 2 4-2=2 4−2=2 项的值 F ( 4 − 2 ) = F ( 2 ) = 2 F(4-2) = F(2) =2 F(4−2)=F(2)=2 ;

( 3 ) 初值 : F ( 0 ) = 1 , F ( 1 ) = 1 F(0) = 1 , F(1) = 1 F(0)=1,F(1)=1

根据 F ( 0 ) = 1 , F ( 1 ) = 1 F(0) = 1, F(1) = 1 F(0)=1,F(1)=1 可以计算 F ( 2 ) F(2) F(2) , 根据 F ( 1 ) , F ( 2 ) F(1),F(2) F(1),F(2) 可以计算 F ( 3 ) F(3) F(3) , 根据 F ( 2 ) F ( 3 ) F(2)F(3) F(2)F(3) 可以 计算 F ( 4 ) F(4) F(4) , ⋯ \cdots ⋯ , 根据 F ( n − 2 ) , F ( n − 1 ) F(n-2) , F(n-1) F(n−2),F(n−1) 可以计算 F ( n ) F(n) F(n) ;

2 . 写出斐波那契数列的特征方程 :

递推方程 : F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2) F(n)=F(n−1)+F(n−2)

( 1 ) 递推方程标准形式 : F ( n ) − F ( n − 1 ) − F ( n − 2 ) = 0 F(n) - F(n-1) - F(n-2) = 0 F(n)−F(n−1)−F(n−2)=0

( 2 ) 递推方程写法 :

① 先确定特征方程的项数 : 与递推方程项数相同 , 3 3 3 项 ;

② 在确定特征方程 x x x 的次幂 : 从 3 − 1 = 2 3-1=2 3−1=2 到 0 0 0 ;

③ 初步写出没有系数的递推方程 : x 2 + x 1 + x 0 = 0 x^2 + x^1 + x^0 = 0 x2+x1+x0=0

④ 填充系数 : 然后将没有系数的特征方程 x 2 + x 1 + x 0 = 0 x^2 + x^1 + x^0 = 0 x2+x1+x0=0 与 F ( n ) − F ( n − 1 ) − F ( n − 2 ) = 0 F(n) - F(n-1) - F(n-2) = 0 F(n)−F(n−1)−F(n−2)=0 对应位的系数填充到特征方程中 :

• x 2 x^2 x2 前的系数 对应 F ( n ) F(n) F(n) 项前的系数 1 1 1 ;
• x 1 x^1 x1 前的系数 对应 F ( n − 1 ) F(n-1) F(n−1) 项前的系数 − 1 -1 −1 ;
• x 0 x^0 x0 前的系数 对应 F ( n − 2 ) F(n-2) F(n−2) 项前的系数 − 1 -1 −1 ;

则最终的 特征方程是 1 x 2 + ( − 1 ) x 1 + ( − 1 ) x 0 = 0 1 x^2 + (-1)x^1 + (-1)x^0 = 0 1x2+(−1)x1+(−1)x0=0 , 化简后为 :

x 2 − x − 1 = 0 x^2 - x - 1 = 0 x2−x−1=0

特征方程的特征根是 : 上述方程的解就是特征根 , 一般都是一元二次方程 ;

x = 1 ± 5 2 x = \cfrac{1 \pm \sqrt{5}}{2} x=21±5 ​​

参考 : 一元二次方程形式 a x 2 + b x + c = 0 ax^2 + bx + c = 0 ax2+bx+c=0 解为 : x = − b ± b 2 − 4 a c 2 a x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} x=2a−b±b2−4ac ​​