【组合数学】递推方程 ( 常系数线性非齐次递推方程求解 | 递推方程标准型及通解 | 递推方程通解证明 )

一、递推方程标准型及通解

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 ) − 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) 常系数线性齐次递推方程 :       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 ) − 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) 的左部 ,

将带 上划线 的 H ( n ) ‾ \overline{H(n)} H(n)​ 项合并 , 一定为 0 0 0 ,

将带 ∗ * ∗ 星号 的 H ∗ ( n ) H^*(n) H∗(n) 项合并 , 一定为 f ( n ) f(n) f(n) ,

0 + f ( n ) 0 + f(n) 0+f(n) 最终结果还是 f ( n ) f(n) f(n) , 与右侧的 f ( n ) f(n) f(n) 相等 ;

递推方程的任何一个解 , 都是一个 齐次通解 , 加上 一个特解 的格式 ;

二、递推方程通解证明

证明 : 递推方程的通解 , 一定 是一个 齐次通解 , 加上 一个特解 的格式 ;

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

假设 h ( n ) h(n) h(n) 是递推方程的通解 , 证明该 h ( n ) h(n) h(n) 是一个 齐次通解 , 加上 一个特解 之和 ;

将 h ( n ) h(n) h(n) 代入上述递推方程中 ,

① 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)

特解 H ∗ ( n ) H^*(n) H∗(n) 也是递推方程的解 , 将 H ∗ ( n ) H^*(n) H∗(n) 代入递推方程 , 左右也是相等的 ,

② 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)

将上述 ① ② 两个等式的 左部与左部相减 , 右部与右部相减 ,

( h ( n ) − a 1 h ( n − 1 ) − ⋯ − a k h ( n − k ) ) ( h(n) - a_1h(n-1) - \cdots - a_kh(n-k) ) (h(n)−a1​h(n−1)−⋯−ak​h(n−k)) − - − ( H ∗ ( n ) − a 1 H ∗ ( n − 1 ) − ⋯ − a k H ∗ ( n − k ) ) ( H^*(n) - a_1H^*(n-1) - \cdots - a_kH^*(n-k) ) (H∗(n)−a1​H∗(n−1)−⋯−ak​H∗(n−k)) = 0 =0 =0

合并上式中的项 :

[ h ( n ) − H ∗ ( n ) ] − a 1 [ h ( n − 1 ) − H ∗ ( n − 1 ) ] − ⋯ − a k [ h ( n − k ) − H ∗ ( n − k ) ] = 0 [ h(n) - H^*(n) ] - a_1[ h(n-1) - H^*(n-1) ] - \cdots - a_k[ h(n-k) - H^*(n-k) ] = 0 [h(n)−H∗(n)]−a1​[h(n−1)−H∗(n−1)]−⋯−ak​[h(n−k)−H∗(n−k)]=0

上述方程是齐次方程 , h ( n ) − H ∗ ( n ) h(n) - H^*(n) h(n)−H∗(n) 是齐次方程的通解 ,

那么 h ( n ) h(n) h(n) 就是 齐次方程通解 与 特解 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) 格式一定是通解 ;