【组合数学】递推方程 ( 有重根下递推方程通解结构 | 线性无关解 | 有重根下的通解 | 有重根下的递推方程求解示例 | 递推方程公式解法总结 ) ★

一、线性无关解

线性无关解 :

如果 q q q 是递推方程的 e e e 重特征根 , 则

q n , n q n , n 2 q n , ⋯   , n e − 1 q n q^n , nq^n , n^2q^n , \cdots , n^{e-1}q^n qn,nqn,n2qn,⋯,ne−1qn

是递推方程的 线性无关的解 ;

e e e 是特征根的重数 ;

二、有重根下的通解

q 1 , q 2 , ⋯   , q t q_1, q_2, \cdots , q_t q1​,q2​,⋯,qt​ 是递推方程的 不相等的特征根 , 有 t t t 个不相等的特征根 ,

q i q_i qi​ 的重数是 e i e_i ei​ ,

某一个特征根 q i q_i qi​ , 其重复度是 e i e_i ei​ , 该 特征根 对应的 通解中的项 是 :

H i ( n ) = ( c i 1 + c i 2 n + ⋯ + c i e i n e i − 1 ) q i n H_i(n) = (c_{i1} + c_{i2}n + \cdots + c_{ie_i}n^{e_i - 1})q_i^n Hi​(n)=(ci1​+ci2​n+⋯+ciei​​nei​−1)qin​

上述通解项的 系数中 , 含有 e i e_i ei​ 个项 , 这 e i e_i ei​ 个项的常数之外的 n n n 次幂取值是从 0 0 0 到 e i − 1 e_i - 1 ei​−1 ,

该递推方程通解是 : H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n) H(n)=i=1∑t​Hi​(n)

二、有重根下的通解写法

有重根下的通解形式列出 :

1 . 特征根数 : q 1 , q 2 , ⋯   , q t q_1, q_2, \cdots , q_t q1​,q2​,⋯,qt​ 是递推方程特征根 , 不相等的特征根数 t t t ;

2 . 根据 特征根 写出通解中的项 H i ( n ) H_i(n) Hi​(n) : 特征根 q i q_i qi​ , 重复度 e i e_i ei​ , 其中 i i i 的取值是 0 0 0 到 t t t ; 第 i i i 个特征根对应的通解项 , 记作 H i ( n ) H_i(n) Hi​(n) ;

• ( 1 ) 组成 : 系数项 乘以 q i n q_i^n qin​ ;
• ( 2 ) 系数项 :
  • ① 个数 : 有 e i e_i ei​ 项 ; 系数项的个数 , 就是该特征根的重复度 ;
  • ② 形式 : 常数 乘以 n n n 的次幂 ; 如 : n e i − 1 n^{e_i-1} nei​−1 , 这里有 e i e_i ei​ 个常数 ;
    • 1 >常数 : 常数下标是从 c i 1 c_{i1} ci1​ 到 c i e i c_{ie_i} ciei​​ , 下标的右侧部分是 1 1 1 到 e i e_i ei​ ;
    • 2 > n n n 的次幂 : 幂的取值是从 0 0 0 到 e i − 1 e_i - 1 ei​−1 ;
    • 3 >建议排列方式 : 常数 和 次幂 , 最好都从小到大排列 , 常数下标 与 n n n 的幂 相差 1 1 1 ;
• ( 3 ) 通解第 i i i 项 : H i ( n ) = ( c i 1 + c i 2 n + ⋯ + c i e i n e i − 1 ) q i n H_i(n) = (c_{i1} + c_{i2}n + \cdots + c_{ie_i}n^{e_i - 1})q_i^n Hi​(n)=(ci1​+ci2​n+⋯+ciei​​nei​−1)qin​

3 . 写出通解 :

• ( 1 ) 通解项数 : 特征根数 t t t ;
• ( 2 ) 通解组成 : 每个特征根对应的通解项 , 加到一起 , 就是完整的通解 ;
• ( 3 ) 最终结果 : H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n) H(n)=i=1∑t​Hi​(n)

三、有重根下的递推方程求解示例

求解方法 :

1 . 特征方程 :

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

该递推方程目前就是标准形式 ;

( 2 ) 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;

5 5 5 项 ;

( 3 ) 特征方程次幂数 : 最高次幂是 特征方程项数 − 1 -1 −1 , 最低次幂 0 0 0 ;

x x x 的次幂从 0 0 0 到 4 4 4 ;

( 4 ) 写出 没有系数 的特征方程 ;

x 4 + x 3 + x 2 + x + 1 = 0 x^4 + x^3 + x^2 + x + 1 = 0 x4+x3+x2+x+1=0

( 5 ) 逐位将递推方程的系数 抄写 到特征方程中 ;

x 4 + x 3 − 3 x 2 − 5 x − 2 = 0 x^4 + x^3 - 3x^2 -5 x -2 = 0 x4+x3−3x2−5x−2=0

2 . 解特征根 : 将 特征方程的 特征根 解出来 , 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 , 2 -1, -1, -1, 2 −1,−1,−1,2 ;

3 . 构造递推方程的通解 :

( 1 ) 无重根 : 构造 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​ 形式的线性组合 , 该线性组合就是递推方程的 通解 ;

( 2 ) 有重根 : 参考下面的 “有重根下的通解形式列出” 内容 ;

此处的情况属于有重根的情况 , 参考下面的解法 :

重根 − 1 -1 −1 项需要按照 重根的通解项规则 写 ;

非重根 2 2 2 , 可以按照 一般的形式 写出 , 即 c 4 2 n c_42^n c4​2n , c 4 c_4 c4​ 是常数 , 4 4 4 代表这是第 4 4 4 个特征根 ;

重根是 − 1 -1 −1 , 重复度是 3 3 3 ;

H 1 ( n ) H_1(n) H1​(n) 代表该重根项 , 该项由 系数项 乘以 ( − 1 ) n (-1)^n (−1)n 组成 ;

系数项中有 3 3 3 项 ; 每个系数项的形式是 常数 乘以 n n n 的幂 ;

常数使用 c 1 , c 2 , c 3 c_1, c_2, c_3 c1​,c2​,c3​ 表示 , n n n 的幂 取值是 0 0 0 到 2 2 2 ( 系数项个数 − 1 -1 −1 ) ;

写出 − 1 -1 −1 特征根对应的通解项 : H 1 ( n ) = ( c 1 + c 2 n + c 3 n 2 ) ( − 1 ) n H_1(n) = (c_1 + c_2n + c_3n^2)(-1)^n H1​(n)=(c1​+c2​n+c3​n2)(−1)n

完整的通解是 :

H ( n ) = ( c 1 + c 2 n + c 3 n 2 ) ( − 1 ) n + c 4 2 n H(n) = (c_1 + c_2n + c_3n^2)(-1)^n + c_42^n H(n)=(c1​+c2​n+c3​n2)(−1)n+c4​2n

4 . 求通解中的常数 :

( 1 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到 k k k 个 k k k 元方程组 , 通过 解该方程组 , 得到 通解中的常数 ;

{ ( c 1 + 0 c 2 + 0 2 c 3 ) ( − 1 ) 0 + 2 0 c 4 = F ( 0 ) = 1 ( c 1 + 1 c 2 + 1 2 c 3 ) ( − 1 ) 1 + 2 1 c 4 = F ( 1 ) = 0 ( c 1 + 2 c 2 + 2 2 c 3 ) ( − 1 ) 2 + 2 2 c 4 = F ( 2 ) = 1 ( c 1 + 3 c 2 + 3 2 c 3 ) ( − 1 ) 3 + 2 3 c 4 = F ( 3 ) = 2 \begin{cases} ( c_1 + 0c_2 + 0^2c_3 )(-1)^0 + 2^0c_4 = F(0) = 1 \\\\ ( c_1 + 1c_2 + 1^2c_3 )(-1)^1 + 2^1c_4 = F(1) = 0 \\\\ ( c_1 + 2c_2 + 2^2c_3 )(-1)^2 + 2^2c_4 = F(2) = 1 \\\\ ( c_1 + 3c_2 + 3^2c_3 )(-1)^3 + 2^3c_4 = F(3) = 2 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​(c1​+0c2​+02c3​)(−1)0+20c4​=F(0)=1(c1​+1c2​+12c3​)(−1)1+21c4​=F(1)=0(c1​+2c2​+22c3​)(−1)2+22c4​=F(2)=1(c1​+3c2​+32c3​)(−1)3+23c4​=F(3)=2​

化简后为 :

{ c 1 + c 4 = 1 − c 1 − c 2 − c 3 + 2 c 4 = 0 c 1 + 2 c 2 + 4 c 3 + 4 c 4 = 1 − c 1 − 3 c 2 − 9 c 3 + 8 c 4 = 2 \begin{cases} c_1 +c_4= 1 \\\\ -c_1 - c_2 - c_3 + 2c_4 = 0 \\\\ c_1 +2 c_2 +4 c_3 + 4c_4= 1 \\\\ -c_1 - 3c_2 - 9c_3 + 8c_4= 2 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​c1​+c4​=1−c1​−c2​−c3​+2c4​=0c1​+2c2​+4c3​+4c4​=1−c1​−3c2​−9c3​+8c4​=2​

解上述 4 4 4 个常数值为 : c 1 = 7 9 , c 2 = − 1 3 , c 3 = 0 , c 4 = 2 9 c_1 = \cfrac{7}{9}, c_2 = -\cfrac{1}{3}, c_3 = 0, c_4 = \cfrac{2}{9} c1​=97​,c2​=−31​,c3​=0,c4​=92​

( 2 ) 代入常数获得通解 : 将常数代入通解 , 就可以得到最终的递推方程的解 ;

完整的通解 :

H ( n ) = 7 9 ( − 1 ) n − 1 3 ( − 1 ) n + 2 9 2 n H(n) = \cfrac{7}{9} (-1)^n - \cfrac{1}{3} (-1)^n + \cfrac{2}{9}2^n H(n)=97​(−1)n−31​(−1)n+92​2n

四、递推方程公式解法总结

递推方程求解完整过程 :

1 . 特征方程 :

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

( 2 ) 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;

( 3 ) 特征方程次幂数 : 最高次幂是 特征方程项数 − 1 -1 −1 , 最低次幂 0 0 0 ;

( 4 ) 写出 没有系数 的特征方程 ;

( 5 ) 逐位将递推方程的系数 抄写 到特征方程中 ;

2 . 解特征根 : 将 特征方程的 特征根 解出来 , x = − b ± b 2 − 4 a c 2 a x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} x=2a−b±b2−4ac ​​

3 . 构造递推方程的通解 :

( 1 ) 无重根 : 构造 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​ 形式的线性组合 , 该线性组合就是递推方程的 通解 ;

( 2 ) 有重根 : 参考下面的 “有重根下的通解形式列出” 内容 ;

4 . 求通解中的常数 :

( 1 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到 k k k 个 k k k 元方程组 , 通过 解该方程组 , 得到 通解中的常数 ;

( 2 ) 代入常数获得通解 : 将常数代入通解 , 就可以得到最终的递推方程的解 ;

有重根下的通解形式列出 :

1 . 特征根数 : q 1 , q 2 , ⋯   , q t q_1, q_2, \cdots , q_t q1​,q2​,⋯,qt​ 是递推方程特征根 , 不相等的特征根数 t t t ;

2 . 根据 特征根 写出通解中的项 H i ( n ) H_i(n) Hi​(n) : 特征根 q i q_i qi​ , 重复度 e i e_i ei​ , 其中 i i i 的取值是 0 0 0 到 t t t ; 第 i i i 个特征根对应的通解项 , 记作 H i ( n ) H_i(n) Hi​(n) ;

• ( 1 ) 组成 : 系数项 乘以 q i n q_i^n qin​ ;
• ( 2 ) 系数项 :
  • ① 个数 : 有 e i e_i ei​ 项 ; 系数项的个数 , 就是该特征根的重复度 ;
  • ② 形式 : 常数 乘以 n n n 的次幂 ; 如 : n e i − 1 n^{e_i-1} nei​−1 , 这里有 e i e_i ei​ 个常数 ;
    • 1 >常数 : 常数下标是从 c i 1 c_{i1} ci1​ 到 c i e i c_{ie_i} ciei​​ , 下标的右侧部分是 1 1 1 到 e i e_i ei​ ;
    • 2 > n n n 的次幂 : 幂的取值是从 0 0 0 到 e i − 1 e_i - 1 ei​−1 ;
    • 3 >建议排列方式 : 常数 和 次幂 , 最好都从小到大排列 , 常数下标 与 n n n 的幂 相差 1 1 1 ;
• ( 3 ) 通解第 i i i 项 : H i ( n ) = ( c i 1 + c i 2 n + ⋯ + c i e i n e i − 1 ) q i n H_i(n) = (c_{i1} + c_{i2}n + \cdots + c_{ie_i}n^{e_i - 1})q_i^n Hi​(n)=(ci1​+ci2​n+⋯+ciei​​nei​−1)qin​

3 . 写出通解 :

• ( 1 ) 通解项数 : 特征根数 t t t ;
• ( 2 ) 通解组成 : 每个特征根对应的通解项 , 加到一起 , 就是完整的通解 ;
• ( 3 ) 最终结果 : H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n) H(n)=i=1∑t​Hi​(n)

递推方程 -> 特征方程 -> 特征根 -> 通解 -> 代入初值求通解常数