H ( n ) − a 1 H ( n − 1 ) − ⋯ − a k H ( n − k ) = f ( n ) H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = f(n) H(n)−a1​H(n−1)−⋯−ak​H(n−k)=f(n) , n ≥ k , a k ≠ 0 , f ( n ) ≠ 0 n\geq k , a_k\not= 0, f(n) \not= 0 n≥k,ak​​=0,f(n)​=0

上述方程左侧 与 “常系数线性齐次递推方程” 是一样的 , 但是右侧不是 0 0 0 , 而是一个基于 n n n 的 函数 f ( n ) f(n) f(n) , 这种类型的递推方程称为 “常系数线性非齐次递推方程” ;

H ( n ) ‾ \overline{H(n)} H(n)​ 是上述递推方程对应 “常系数线性齐次递推方程” H ( n ) − a 1 H ( n − 1 ) − ⋯ − a k H ( n − k ) = 0 H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = 0 H(n)−a1​H(n−1)−⋯−ak​H(n−k)=0 的通解 ,

H ∗ ( n ) H^*(n) H∗(n) 是一个特解 ,

“常系数线性非齐次递推方程” 的通解是 H ( n ) = H ( n ) ‾ + H ∗ ( n ) H(n) = \overline{H(n)} + H^*(n) H(n)=H(n)​+H∗(n)

在 【组合数学】递推方程 ( 无重根递推方程求解实例 | 无重根下递推方程求解完整过程 ) 博客中介绍了 “常系数线性齐次递推方程” 的通解求法 ;

本博客中开始介绍 特解 H ∗ ( n ) H^*(n) H∗(n) 的求法 ;

特解与 “常系数线性非齐次递推方程” 中的右部 f ( n ) f(n) f(n) 有关 ,

f ( n ) f(n) f(n) 为 n n n 的 t t t 次多项式 ,

特解 H ∗ ( n ) H^*(n) H∗(n) 也是 n n n 的 t t t 次多项式 ;

1 . 特解形式 :

( 1 ) 特解形式 : 特解 H ∗ ( n ) H^*(n) H∗(n) 是 n n n 的 t t t 次多项式 , n n n 的幂取值从 0 0 0 到 t t t , 因此其 项数有 t + 1 t+1 t+1 项 ;

( 2 ) 特解每项组成 :

( 3 ) 举例 : 特解 H ∗ ( n ) H^*(n) H∗(n) 是 n n n 的 2 2 2 次多项式 ;

特解项数 : 则 特解项数 是 2 + 1 = 3 2 + 1 = 3 2+1=3 项 ;

特解每项组成 : 特解每一项由 常数 乘以 n n n 的次幂 组成 ,

3 3 3 个常数 设为 P 1 , P 2 , P 3 P_1, P_2, P_3 P1​,P2​,P3​ ,

3 3 3 个 n n n 的次幂 , 幂取值 从 0 0 0 到 2 2 2 ,

因此特解的形式为 H ∗ ( n ) = P 1 n 2 + P 2 n 1 + P 3 n 0 H^*(n) = P_1n^2 + P_2n^1 + P_3n^0 H∗(n)=P1​n2+P2​n1+P3​n0 ,

化简后为 : H ∗ ( n ) = P 1 n 2 + P 2 n + P 3 H^*(n) = P_1n^2 + P_2n + P_3 H∗(n)=P1​n2+P2​n+P3​

2 . 特解求法 :

( 1 ) 先写出特解的形式 : 特解 H ∗ ( n ) H^*(n) H∗(n) 也是 n n n 的 t t t 次多项式 ; 如 : f ( n ) f(n) f(n) 为 n n n 的 2 2 2 次多项式 , 则特解为 H ∗ ( n ) = P 1 n 2 + P 2 n + P 3 H^*(n) = P_1n^2 + P_2n + P_3 H∗(n)=P1​n2+P2​n+P3​

( 2 ) 特解代入递推方程 : 然后将特解代入递推方程 , 将特解中的系数确定下来 ;

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

1 . 特解形式 :

上述递推方程左侧是 “常系数线性齐次递推方程” 形式 , 不用管 ,

右侧的 3 n 2 3n^2 3n2 与特解相关 ,

3 n 2 3n^2 3n2 为 n n n 的 2 2 2 次多项式 ,

因此特解 H ∗ ( n ) H^*(n) H∗(n) 也是 n n n 的 2 2 2 次多项式 ;

2 . 写出特解形式 :

特解项数 : 则 特解项数 是 2 + 1 = 3 2 + 1 = 3 2+1=3 项 ;

特解每项组成 : 特解每一项由 常数 乘以 n n n 的次幂 组成 ,

3 3 3 个常数 设为 P 1 , P 2 , P 3 P_1, P_2, P_3 P1​,P2​,P3​ ,

3 3 3 个 n n n 的次幂 , 幂取值 从 0 0 0 到 2 2 2 ,

因此特解的形式为 H ∗ ( n ) = P 1 n 2 + P 2 n 1 + P 3 n 0 H^*(n) = P_1n^2 + P_2n^1 + P_3n^0 H∗(n)=P1​n2+P2​n1+P3​n0 ,

化简后为 : H ∗ ( n ) = P 1 n 2 + P 2 n + P 3 H^*(n) = P_1n^2 + P_2n + P_3 H∗(n)=P1​n2+P2​n+P3​

3 . 将特解代入递推方程 :

将特解 H ∗ ( n ) = P 1 n 2 + P 2 n + P 3 H^*(n) = P_1n^2 + P_2n + P_3 H∗(n)=P1​n2+P2​n+P3​ ,

代入到递推方程 a n + 5 a n − 1 + 6 a n − 2 = 3 n 2 a_n + 5a_{n-1} + 6a_{n-2}=3n^2 an​+5an−1​+6an−2​=3n2 中 ,

得到 :

( P 1 n 2 + P 2 n + P 3 ) + 5 ( P 1 ( n − 1 ) 2 + P 2 ( n − 1 ) + P 3 ) + 6 ( P 1 ( n − 2 ) 2 + P 2 ( n − 2 ) + P 3 ) = 3 n 2 (P_1n^2 + P_2n + P_3) + 5(P_1(n-1)^2 + P_2(n-1) + P_3) + 6(P_1(n-2)^2 + P_2(n-2) + P_3)=3n^2 (P1​n2+P2​n+P3​)+5(P1​(n−1)2+P2​(n−1)+P3​)+6(P1​(n−2)2+P2​(n−2)+P3​)=3n2

4 . 分析 n n n 的幂写出方程组 :

左右两侧是相等的 , 这里 根据 n n n 的次幂前的系数 , 写出方程组 ;

分析 n n n 的次幂的系数 :

最终得到方程组 :

{ 12 P 1 = 3 − 34 P 1 + 12 P 2 = 0 29 P 1 − 17 P 2 + 12 P 3 = 0 \begin{cases} 12P_1 = 3 \\\\ -34P_1 + 12P_2 = 0 \\\\ 29P_1 - 17P_2 + 12 P_3 = 0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​12P1​=3−34P1​+12P2​=029P1​−17P2​+12P3​=0​

解上述方程组 , 得到结果 :

{ P 1 = 1 4 P 2 = 7 24 P 3 = 115 288 \begin{cases} P_1 = \cfrac{1}{4} \\\\ P_2 = \cfrac{7}{24} \\\\ P_3 = \cfrac{115}{288} \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​P1​=41​P2​=247​P3​=288115​​

特解是 : H ∗ ( n ) = 1 4 n 2 + 7 24 n + 115 288 H^*(n) = \cfrac{1}{4} n^2 + \cfrac{7}{24}n + \cfrac{115}{288} H∗(n)=41​n2+247​n+288115​

最终通解是 :

H ( n ) = c 1 ( − 2 ) n + c 2 ( − 3 ) n + 1 4 n 2 + 7 24 n + 115 288 H(n) = c_1(-2)^n + c_2(-3)^n + \cfrac{1}{4} n^2 + \cfrac{7}{24}n + \cfrac{115}{288} H(n)=c1​(−2)n+c2​(−3)n+41​n2+247​n+288115​