【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )

一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式

如果 “常系数线性非齐次递推方程” 的非齐次部分 , 是 n n n 的 t t t 次多项式 , 与 β n \beta^n βn 的指数 , 的组合 ;

那么其特解的形式 , 是 n n n 的 t t t 次多项式 , 与 P β n P\beta^n Pβn 的 和 ;

递推方程 : a n − 2 a n − 1 = n + 3 n a_n - 2a_{n-1} = n + 3^n an​−2an−1​=n+3n

初值 : a 0 = 0 a_0 = 0 a0​=0

通解形式 ( 重要 ) :

① 非齐次部分是 n n n 的 t t t 次多项式 :

• 特征根不为 1 1 1 , 特解是 n n n 的 t t t 次多项式 ;
• 如果特征根为 1 1 1 , 且重数为 e e e , 那么特解是 n n n 的 t + e t + e t+e 次多项式 ;

② 非齐次部分是 P β n P\beta^n Pβn :

• 特征根不能是底 β \beta β , 特解是 P β n P\beta^n Pβn ;
• 特征根是底 β \beta β , 该特征根重数为 e e e , 特解是 P n e β n Pn^e\beta^n Pneβn ;

③ 齐次部分没有重根 : H ( n ) = c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​

④ 齐次部分有重根 : 通解第 i i i 项 , 特征根 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​ , 最终通解 H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n) H(n)=i=1∑t​Hi​(n) ;

参考博客 : 【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )

计算齐次部分通解 :

递推方程齐次部分标准形式 : a n − 2 a n − 1 = 0 a_n - 2a_{n-1} = 0 an​−2an−1​=0

特征方程 : x − 2 = 0 x - 2 = 0 x−2=0

特征根 : x = 2 x=2 x=2

齐次部分通解 : a n ‾ = c 2 n \overline{a_n} =c2^n an​​=c2n

计算非齐次部分通解 :

上述递推方程非齐次部分是 n + 3 n n + 3^n n+3n , 由两部分构成 :

n n n 的 t t t 次多项式 : n n n , 特征根不为 1 1 1 , 对应的特解是 n n n 的 t t t 次多项式 , 形式为 P 1 n + P 2 P_1n + P_2 P1​n+P2​ ;

β n \beta^n βn 指数 : 3 n 3^n 3n , 特征根不是底 3 3 3 , 对应的特解是 P β n P\beta^n Pβn 形式 , 形式为 P 3 3 n P_33^n P3​3n ;

完整的特解 : a n ∗ = P 1 n + P 2 + P 3 3 n a^*_n = P_1n + P_2 + P_33^n an∗​=P1​n+P2​+P3​3n

将特解代入到递推方程 :

( P 1 n + P 2 + P 3 3 n ) − 2 [ P 1 ( n − 1 ) + P 2 + P 3 3 n − 1 ] = n + 3 n (P_1n + P_2 + P_33^n) - 2[P_1(n-1) + P_2 + P_33^{n-1}] = n + 3^n (P1​n+P2​+P3​3n)−2[P1​(n−1)+P2​+P3​3n−1]=n+3n

将左边式子展开 :

− P 1 n + ( 2 P 1 − P 2 ) + P 3 3 n − 1 = n + 3 n -P_1n + (2P_1 - P_2) + P_33^{n-1}=n+3^n −P1​n+(2P1​−P2​)+P3​3n−1=n+3n

根据分析 n n n 的次幂项 , 常数项 , 3 n 3^n 3n 项的对应关系 , 可以得到以下方程组 :

{ − P 1 = 1 2 P 1 − P 2 = 0 P 3 3 = 1 \begin{cases} -P_1 = 1 \\\\ 2P_1 - P_2 = 0 \\\\ \cfrac{P_3}{3} =1 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧​−P1​=12P1​−P2​=03P3​​=1​

解上述方程组 , 结果为 :

{ P 1 = − 1 P 2 = − 2 P 3 = 3 \begin{cases} P_1 = -1 \\\\ P_2 = -2 \\\\ P_3 =3 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​P1​=−1P2​=−2P3​=3​

特解 : 将上述常数代入到 a n ∗ = P 1 n + P 2 + P 3 3 n a^*_n = P_1n + P_2 + P_33^n an∗​=P1​n+P2​+P3​3n 中 , 得到最终特解 : a n ∗ = − n − 2 + 3 n + 1 a^*_n = -n - 2 + 3^{n+1} an∗​=−n−2+3n+1 ;

齐次部分通解形式 : a n ‾ = c 2 n \overline{a_n} =c2^n an​​=c2n

完整通解 : a n = a n ‾ + a n ∗ = c 2 n − n − 2 + 3 n + 1 a_n = \overline{a_n} + a^*_n = c2^n -n - 2 + 3^{n+1} an​=an​​+an∗​=c2n−n−2+3n+1

将初值 a 0 = 0 a_0 = 0 a0​=0 代入上述通解 :

c 2 0 − 0 − 2 + 3 0 + 1 = 0 c2^0 - 0 - 2 + 3^{0+1} = 0 c20−0−2+30+1=0

c − 2 + 3 = 0 c - 2 + 3 = 0 c−2+3=0

c = − 1 c=-1 c=−1

最终递推方程的通解是 a n = 2 n − n − 2 + 3 n + 1 a_n = 2^n -n - 2 + 3^{n+1} an​=2n−n−2+3n+1

二、递推方程通解的四种情况

通解形式 ( 重要 ) :

① 非齐次部分是 n n n 的 t t t 次多项式 :

• 特征根不为 1 1 1 , 特解是 n n n 的 t t t 次多项式 ;
• 如果特征根为 1 1 1 , 且重数为 e e e , 那么特解是 n n n 的 t + e t + e t+e 次多项式 ;

② 非齐次部分是 P β n P\beta^n Pβn :

• 特征根不能是底 β \beta β , 特解是 P β n P\beta^n Pβn ;
• 特征根是底 β \beta β , 该特征根重数为 e e e , 特解是 P n e β n Pn^e\beta^n Pneβn ;

③ 齐次部分没有重根 : H ( n ) = c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​

④ 齐次部分有重根 : 通解第 i i i 项 , 特征根 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​ , 最终通解 H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n) H(n)=i=1∑t​Hi​(n) ;

参考博客 : 【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )