文章目录
一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式
二、递推方程通解的四种情况
一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式
如果 “常系数线性非齐次递推方程” 的非齐次部分 , 是 n nn 的 t tt 次多项式 , 与 β n \beta^nβ
n
的指数 , 的组合 ;
那么其特解的形式 , 是 n nn 的 t tt 次多项式 , 与 P β n P\beta^nPβ
n
的 和 ;
递推方程 : a n − 2 a n − 1 = n + 3 n a_n - 2a_{n-1} = n + 3^na
n
−2a
n−1
=n+3
n
初值 : a 0 = 0 a_0 = 0a
0
=0
通解形式 ( 重要 ) :
① 非齐次部分是 n nn 的 t tt 次多项式 :
特征根不为 1 11 , 特解是 n nn 的 t tt 次多项式 ;
如果特征根为 1 11 , 且重数为 e ee , 那么特解是 n nn 的 t + e t + et+e 次多项式 ;
② 非齐次部分是 P β n P\beta^nPβ
n
:
特征根不能是底 β \betaβ , 特解是 P β n P\beta^nPβ
n
;
特征根是底 β \betaβ , 该特征根重数为 e ee , 特解是 P n e β n Pn^e\beta^nPn
e
β
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^nH(n)=c
1
q
1
n
+c
2
q
2
n
+⋯+c
k
q
k
n
④ 齐次部分有重根 : 通解第 i ii 项 , 特征根 q i q_iq
i
, 重数 e i e_ie
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^nH
i
(n)=(c
i1
+c
i2
n+⋯+c
ie
i
n
e
i
−1
)q
i
n
, 最终通解 H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n)H(n)=
i=1
∑
t
H
i
(n) ;
参考博客 : 【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
计算齐次部分通解 :
递推方程齐次部分标准形式 : a n − 2 a n − 1 = 0 a_n - 2a_{n-1} = 0a
n
−2a
n−1
=0
特征方程 : x − 2 = 0 x - 2 = 0x−2=0
特征根 : x = 2 x=2x=2
齐次部分通解 : a n ‾ = c 2 n \overline{a_n} =c2^n
a
n
=c2
n
计算非齐次部分通解 :
上述递推方程非齐次部分是 n + 3 n n + 3^nn+3
n
, 由两部分构成 :
n nn 的 t tt 次多项式 : n nn , 特征根不为 1 11 , 对应的特解是 n nn 的 t tt 次多项式 , 形式为 P 1 n + P 2 P_1n + P_2P
1
n+P
2
;
β n \beta^nβ
n
指数 : 3 n 3^n3
n
, 特征根不是底 3 33 , 对应的特解是 P β n P\beta^nPβ
n
形式 , 形式为 P 3 3 n P_33^nP
3
3
n
;
完整的特解 : a n ∗ = P 1 n + P 2 + P 3 3 n a^*_n = P_1n + P_2 + P_33^na
n
∗
=P
1
n+P
2
+P
3
3
n
将特解代入到递推方程 :
( 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(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 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−P
1
n+(2P
1
−P
2
)+P
3
3
n−1
=n+3
n
根据分析 n nn 的次幂项 , 常数项 , 3 n 3^n3
n
项的对应关系 , 可以得到以下方程组 :
{ − P 1 = 1 2 P 1 − P 2 = 0 P 3 3 = 1
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪−P1=12P1−P2=0P33=1
{−P1=12P1−P2=0P33=1
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎧
−P
1
=1
2P
1
−P
2
=0
3
P
3
=1
解上述方程组 , 结果为 :
{ P 1 = − 1 P 2 = − 2 P 3 = 3
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪P1=−1P2=−2P3=3
{P1=−1P2=−2P3=3
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎧
P
1
=−1
P
2
=−2
P
3
=3
特解 : 将上述常数代入到 a n ∗ = P 1 n + P 2 + P 3 3 n a^*_n = P_1n + P_2 + P_33^na
n
∗
=P
1
n+P
2
+P
3
3
n
中 , 得到最终特解 : a n ∗ = − n − 2 + 3 n + 1 a^*_n = -n - 2 + 3^{n+1}a
n
∗
=−n−2+3
n+1
;
齐次部分通解形式 : a n ‾ = c 2 n \overline{a_n} =c2^n
a
n
=c2
n
完整通解 : 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}a
n
=
a
n
+a
n
∗
=c2
n
−n−2+3
n+1
将初值 a 0 = 0 a_0 = 0a
0
=0 代入上述通解 :
c 2 0 − 0 − 2 + 3 0 + 1 = 0 c2^0 - 0 - 2 + 3^{0+1} = 0c2
0
−0−2+3
0+1
=0
c − 2 + 3 = 0 c - 2 + 3 = 0c−2+3=0
c = − 1 c=-1c=−1
最终递推方程的通解是 a n = 2 n − n − 2 + 3 n + 1 a_n = 2^n -n - 2 + 3^{n+1}a
n
=2
n
−n−2+3
n+1
二、递推方程通解的四种情况
通解形式 ( 重要 ) :
① 非齐次部分是 n nn 的 t tt 次多项式 :
特征根不为 1 11 , 特解是 n nn 的 t tt 次多项式 ;
如果特征根为 1 11 , 且重数为 e ee , 那么特解是 n nn 的 t + e t + et+e 次多项式 ;
② 非齐次部分是 P β n P\beta^nPβ
n
:
特征根不能是底 β \betaβ , 特解是 P β n P\beta^nPβ
n
;
特征根是底 β \betaβ , 该特征根重数为 e ee , 特解是 P n e β n Pn^e\beta^nPn
e
β
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^nH(n)=c
1
q
1
n
+c
2
q
2
n
+⋯+c
k
q
k
n
④ 齐次部分有重根 : 通解第 i ii 项 , 特征根 q i q_iq
i
, 重数 e i e_ie
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^nH
i
(n)=(c
i1
+c
i2
n+⋯+c
ie
i
n
e
i
−1
)q
i
n
, 最终通解 H ( n ) = ∑ i = 1 t H i ( n ) H(n) = \sum\limits_{i=1}^tH_i(n)H(n)=
i=1
∑
t
H
i
(n) ;
参考博客 : 【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
