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

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

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

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

q q q 是非 0 0 0 复数 , 则有以下等价关系 :

q q q 是特征方程的特征根 ⇔ \Leftrightarrow ⇔ q n q^n qn 是递推方程的解 ★

证明上述定理 :

按照定义 , 将 递推方程的解 q n q^n qn , 代入原来的递推方程 ,

递推方程的解是 q n q^n qn , 代表了 第 n n n 项的值是 q n q^n qn , 即 H ( n ) = q n H(n) = q^n H(n)=qn ;

递推方程 : 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 ,

• 第 n n n 项 H ( n ) H(n) H(n) 的值是 q n q^n qn
• 第 n − 1 n-1 n−1 项 H ( n − 1 ) H(n-1) H(n−1) 的值是 q n − 1 q^{n-1} qn−1
• 第 n − 2 n-2 n−2 项 H ( n − 2 ) H(n-2) H(n−2) 的值是 q n − 2 q^{n-2} qn−2

                 ⋮ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots                 ⋮

• 第 n − k n-k n−k 项 H ( n − k ) H(n-k) H(n−k) 的值是 q n − k q^{n-k} qn−k

代入后结果是 :

      q n \ \ \ \ \ q^n      qn 是递推方程的解

⇔ q n − a 1 q n − 1 − a 2 q n − 2 − ⋯ − a k q n − k = 0 \Leftrightarrow q^n - a_1q^{n-1} - a_2q^{n-2} - \cdots - a_kq^{n-k} = 0 ⇔qn−a1​qn−1−a2​qn−2−⋯−ak​qn−k=0

将 q n − k q^{n-k} qn−k 作为公因式提取出来 ;

⇔ q n − k ( q k − a 1 q k − 1 − a 2 q k − 2 − ⋯ − a k ) = 0 \Leftrightarrow q^{n-k} ( q^k - a_1q^{k-1} - a_2q^{k-2} - \cdots - a_k ) = 0 ⇔qn−k(qk−a1​qk−1−a2​qk−2−⋯−ak​)=0

上述两个乘积为 0 0 0 , q n − k q^{n-k} qn−k 肯定不为 0 0 0 , 则剩余部分结果是 0 0 0 ;

⇔ q k − a 1 q k − 1 − a 2 q k − 2 − ⋯ − a k = 0 \Leftrightarrow q^k - a_1q^{k-1} - a_2q^{k-2} - \cdots - a_k = 0 ⇔qk−a1​qk−1−a2​qk−2−⋯−ak​=0

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

⇔ \Leftrightarrow ⇔ q q q 是特征根

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

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

h 1 ( n ) h_1(n) h1​(n) 和 h 2 ( n ) h_2(n) h2​(n) 都是同一个递推方程的解 ,

c 1 , c 2 c_1 , c_2 c1​,c2​ 是任意常数 ,

使用这两个解作 线性组合 , c 1 h 1 ( n ) + c 2 h 2 ( n ) c_1h_1(n) + c_2h_2(n) c1​h1​(n)+c2​h2​(n) , 这个线性组合也是递推方程的解 ;

证明方法 :

将 c 1 h 1 ( n ) + c 2 h 2 ( n ) c_1h_1(n) + c_2h_2(n) c1​h1​(n)+c2​h2​(n) 组合代入递推方程的左边式子中 , 化简后为 0 0 0 ;

递推方程 : 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 ,

将 c 1 h 1 ( n ) + c 2 h 2 ( n ) c_1h_1(n) + c_2h_2(n) c1​h1​(n)+c2​h2​(n) 线性组合代入上述方程 ,

• H ( n ) H(n) H(n) 使用 c 1 h 1 ( n ) + c 2 h 2 ( n ) c_1h_1(n) + c_2h_2(n) c1​h1​(n)+c2​h2​(n) 代替
• H ( n − 1 ) H(n-1) H(n−1) 使用 c 1 h 1 ( n − 1 ) + c 2 h 2 ( n − 1 ) c_1h_1(n-1) + c_2h_2(n-1) c1​h1​(n−1)+c2​h2​(n−1) 代替
• H ( n − 2 ) H(n-2) H(n−2) 使用 c 1 h 1 ( n − 2 ) + c 2 h 2 ( n − 2 ) c_1h_1(n-2) + c_2h_2(n-2) c1​h1​(n−2)+c2​h2​(n−2) 代替
• H ( n − k ) H(n-k) H(n−k) 使用 c 1 h 1 ( n − k ) + c 2 h 2 ( n − k ) c_1h_1(n-k) + c_2h_2(n-k) c1​h1​(n−k)+c2​h2​(n−k) 代替

得到 :

( c 1 h 1 ( n ) + c 2 h 2 ( n ) ) (c_1h_1(n) + c_2h_2(n)) (c1​h1​(n)+c2​h2​(n)) − - − a 1 ( a_1( a1​( c 1 h 1 ( n − 1 ) + c 2 h 2 ( n − 1 ) c_1h_1(n-1) + c_2h_2(n-1) c1​h1​(n−1)+c2​h2​(n−1) ) − a 2 ) - a_2 )−a2​ ( c 1 h 1 ( n − 2 ) + c 2 h 2 ( n − 2 ) ) (c_1h_1(n-2) + c_2h_2(n-2)) (c1​h1​(n−2)+c2​h2​(n−2)) − ⋯ − a k ( - \cdots - a_k( −⋯−ak​( c 1 h 1 ( n − k ) + c 2 h 2 ( n − k ) c_1h_1(n-k) + c_2h_2(n-k) c1​h1​(n−k)+c2​h2​(n−k) ) = 0 ) = 0 )=0

将所有含有 c 1 h 1 c_1h_1 c1​h1​ 的项合并到一起 , 将所有含有 c 2 h 2 c_2h_2 c2​h2​ 的项 , 合并到一起 , 得到 :

c 1 ( h 1 ( n ) − a 1 h 1 ( n − 1 ) − a 2 h 1 ( n − 2 ) − ⋯ − a k h 1 ( n − k ) ) c_1( h_1(n) - a_1h_1(n-1) - a_2h_1(n-2) - \cdots - a_kh_1(n-k)) c1​(h1​(n)−a1​h1​(n−1)−a2​h1​(n−2)−⋯−ak​h1​(n−k)) + + + c 2 ( h 2 ( n ) − a 1 h 2 ( n − 1 ) − a 2 h 2 ( n − 2 ) − ⋯ − a k h k ( n − k ) ) c_2( h_2(n) - a_1h_2(n-1) - a_2h_2(n-2) - \cdots - a_kh_k(n-k)) c2​(h2​(n)−a1​h2​(n−1)−a2​h2​(n−2)−⋯−ak​hk​(n−k)) = 0 = 0 =0

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

• h 1 ( n ) h_1(n) h1​(n) 是递推方程的解 , 因此 c 1 ( h 1 ( n ) − a 1 h 1 ( n − 1 ) − a 2 h 1 ( n − 2 ) − ⋯ − a k h 1 ( n − k ) ) c_1( h_1(n) - a_1h_1(n-1) - a_2h_1(n-2) - \cdots - a_kh_1(n-k)) c1​(h1​(n)−a1​h1​(n−1)−a2​h1​(n−2)−⋯−ak​h1​(n−k)) 的值为 0 0 0 ;
• h 2 ( n ) h_2(n) h2​(n) 是递推方程的解 , 因此 c 2 ( h 2 ( n ) − a 1 h 2 ( n − 1 ) − a 2 h 2 ( n − 2 ) − ⋯ − a k h k ( n − k ) ) c_2( h_2(n) - a_1h_2(n-1) - a_2h_2(n-2) - \cdots - a_kh_k(n-k)) c2​(h2​(n)−a1​h2​(n−1)−a2​h2​(n−2)−⋯−ak​hk​(n−k)) 的值为 0 0 0 ;

三、递推方程解的形式

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

假定 q 1 , q 2 , ⋯   , q k q_1 , q_2 , \cdots , q_k q1​,q2​,⋯,qk​ 是递推方程的特征根 , 一元 k k k 次方程有 k k k 个根 ;

根据 “递推方程解与特征根之间的关系定理” , q 1 n , q 2 n , ⋯   , q k n q_1^n, q_2^n , \cdots , q_k^n q1n​,q2n​,⋯,qkn​ 都是递推方程的解 ,

将这 k k k 个解 , 作线性组合 , c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ ,

根据 “递推方程解的线性性质定理” , 上述线性组合 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 也是递推方程的解 ;

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

总结下过程 :

• 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是 0 0 0 ;
• 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;
• 特征方程次幂数 : 最高次幂是 特征方程项数 − 1 -1 −1 , 最低次幂 0 0 0 ;
• 写出 没有系数 的特征方程 ;
• 逐位将递推方程的系数 抄写 到特征方程中 ;
• 解特征根 : 将 特征方程的特征根解出来 , x = − b ± b 2 − 4 a c 2 a x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} x=2a−b±b2−4ac ​​
• 构造递推方程的解 : 构造 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 形式的线性组合 , 该线性组合就是递推方程的解 ;

满足 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 公式的所有递推方程 , 都具有 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 形式的解 ;