【组合数学】递推方程 ( 特解形式 | 特解求法 | 特解示例 )

韩曙亮

发布于 2023-03-28 18:31:19

5110

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、特解形式与求法

H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = f(n)

n\geq k , a_k\not= 0, f(n) \not= 0

上述方程左侧与 “常系数线性齐次递推方程” 是一样的 , 但是右侧不是

, 而是一个基于

的函数

f(n)

, 这种类型的递推方程称为 “常系数线性非齐次递推方程” ;

\overline{H(n)}

是上述递推方程对应 “常系数线性齐次递推方程”

H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = 0

的通解 ,

H^*(n)

是一个特解 ,

“常系数线性非齐次递推方程” 的通解是

H(n) = \overline{H(n)} + H^*(n)

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

本博客中开始介绍特解

H^*(n)

的求法 ;

特解与 “常系数线性非齐次递推方程” 中的右部

f(n)

有关 ,

f(n)

为

的

次多项式 ,

特解

H^*(n)

也是

的

次多项式 ;

1 . 特解形式 :

( 1 ) 特解形式 : 特解

H^*(n)

是

的

次多项式 ,

的幂取值从

到

, 因此其项数有

t+1

项 ;

( 2 ) 特解每项组成 :

① 项数 :

t+1

项

② 组成 : 特解项由常数乘以

的次幂组成 , 常数是未知的 ;

③ 常数 :

t+1

个常数 , 使用下标标识好 ;

的幂 : 幂取值从

到

;

( 3 ) 举例 : 特解

H^*(n)

是

的

次多项式 ;

特解项数 : 则特解项数是

2 + 1 = 3

项 ;

特解每项组成 : 特解每一项由常数乘以

的次幂组成 ,

个常数设为

P_1, P_2, P_3

个

的次幂 , 幂取值从

到

因此特解的形式为

H^*(n) = P_1n^2 + P_2n^1 + P_3n^0

化简后为 :

H^*(n) = P_1n^2 + P_2n + P_3

2 . 特解求法 :

( 1 ) 先写出特解的形式 : 特解

H^*(n)

也是

的

次多项式 ; 如 :

f(n)

为

的

次多项式 , 则特解为

H^*(n) = P_1n^2 + P_2n + P_3

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

二、特解形式与求法示例

递推方程 :

a_n + 5a_{n-1} + 6a_{n-2}=3n^2

;

1 . 特解形式 :

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

右侧的

3n^2

与特解相关 ,

3n^2

为

的

次多项式 ,

因此特解

H^*(n)

也是

的

次多项式 ;

2 . 写出特解形式 :

特解项数 : 则特解项数是

2 + 1 = 3

项 ;

特解每项组成 : 特解每一项由常数乘以

的次幂组成 ,

个常数设为

P_1, P_2, P_3

个

的次幂 , 幂取值从

到

因此特解的形式为

H^*(n) = P_1n^2 + P_2n^1 + P_3n^0

化简后为 :

H^*(n) = P_1n^2 + P_2n + P_3

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

将特解

H^*(n) = P_1n^2 + P_2n + P_3

代入到递推方程

a_n + 5a_{n-1} + 6a_{n-2}=3n^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

4 . 分析

的幂写出方程组 :

左右两侧是相等的 , 这里根据

的次幂前的系数 , 写出方程组 ;

分析

的次幂的系数 :

n^2

系数分析 : 右侧是

3n^2

, 因此

n^2

前的系数是

; 将左侧展开 ,

n^2

前的系数相加 , 最终等于

;

12P_1n^2 = 3n^2

n^1

系数分析 : 右侧没有

n^1

, 即没有

项 , 因此左侧的

项之前的系数为

; 将左侧展开 ,

前的系数相加 , 最终等于

;

-34P_1n + 12P_2n = 0n

n^0

系数分析 : 右侧没有

n^0

, 即没有

项 ( 纯数字项 ) , 因此左侧的数字项为

; 将左侧展开 , 数字项最终等于

;

29P_1 - 17P_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}

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

\begin{cases} P_1 = \cfrac{1}{4} \\\\ P_2 = \cfrac{7}{24} \\\\ P_3 = \cfrac{115}{288} \end{cases}

特解是 :

H^*(n) = \cfrac{1}{4} n^2 + \cfrac{7}{24}n + \cfrac{115}{288}

最终通解是 :

H(n) = c_1(-2)^n + c_2(-3)^n + \cfrac{1}{4} n^2 + \cfrac{7}{24}n + \cfrac{115}{288}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

函数

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

博客

函数

数学

登录后参与评论

0 条评论

热度