【组合数学】递推方程 ( 特特解示例 1 汉诺塔 完整求解过程 | 特解示例 2 特征根为 1 的情况下的特解处理 )

一、特解示例 1 ( 汉诺塔 )

Hanoi 问题 :

• 递推方程为 : T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1 T(n)=2T(n−1)+1
• 初值 : T ( 1 ) = 1 T(1) = 1 T(1)=1

求该递推方程的解 ?

先解出其特解

1 . 特解形式 :

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

右侧的 1 1 1 与特解相关 ,

1 1 1 为 n n n 的 0 0 0 次多项式 ,

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

2 . 写出特解形式 :

特解项数 : 则 特解项数 是 0 + 1 = 1 0 + 1 = 1 0+1=1 项 ;

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

• 1 1 1 个常数 设为 P 1 P_1 P1​ ,

• 1 1 1 个 n n n 的次幂 , 幂取值 0 0 0 ,

因此特解的形式为 T ∗ ( n ) = P 1 n 0 T^*(n) = P_1n^0 T∗(n)=P1​n0 ,

化简后为 : T ∗ ( n ) = P 1 T^*(n) = P_1 T∗(n)=P1​

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

将特解 T ∗ ( n ) = P 1 T^*(n) = P_1 T∗(n)=P1​ ,

代入到递推方程 T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1 T(n)=2T(n−1)+1 中 ,

得到 :

P 1 = 2 P 1 + 1 P_1 = 2P_1 + 1 P1​=2P1​+1

解方程结果 : P 1 = − 1 P_1 = -1 P1​=−1

特解为 : T ∗ ( n ) = − 1 T^*(n) = -1 T∗(n)=−1

递推方程求解完整过程 : 求解上述汉诺塔 常系数线性齐次递推方程 部分的通解 , T ( n ) − 2 T ( n − 1 ) = 0 T(n) - 2 T(n-1) = 0 T(n)−2T(n−1)=0 ;

1 . 特征方程 :

( 1 ) 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是 0 0 0 ;

T ( n ) − 2 T ( n − 1 ) = 0 T(n) - 2 T(n-1) = 0 T(n)−2T(n−1)=0

( 2 ) 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;

2 2 2 项 ;

( 3 ) 特征方程次幂数 : 最高次幂是 特征方程项数 − 1 -1 −1 , 最低次幂 0 0 0 ;

最低次幂 0 0 0 , 最高次幂 1 1 1 ;

( 4 ) 写出 没有系数 的特征方程 ;

x + 1 = 0 x + 1 = 0 x+1=0

( 5 ) 逐位将递推方程的系数 抄写 到特征方程中 ;

x − 2 = 0 x - 2 = 0 x−2=0

2 . 解特征根 : 将 特征方程的 特征根 解出来 , x = − b ± b 2 − 4 a c 2 a x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} x=2a−b±b2−4ac ​​

特征根 q 1 = 2 q_1=2 q1​=2 ;

3 . 构造递推方程的通解 :

( 1 ) 无重根 : 构造 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 形式的线性组合 , 该线性组合就是递推方程的 通解 ;

递推方程的齐次部分通解是 : T ( n ) ‾ = c 2 n \overline{T(n)} = c2^n T(n)​=c2n

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

非齐次部分的特解是 : T ∗ ( n ) = − 1 T^*(n) = -1 T∗(n)=−1

因此汉诺塔递推方程的通解是 : T ( n ) = c 2 n − 1 T(n) = c2^n - 1 T(n)=c2n−1

( 2 ) 有重根 : 参考下面的 “有重根下的通解形式列出” 内容 ;

4 . 求通解中的常数 :

( 1 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到 k k k 个 k k k 元方程组 , 通过 解该方程组 , 得到 通解中的常数 ;

将初值 T ( 1 ) = 1 T(1) = 1 T(1)=1 代入上述通解 T ( n ) = c 2 n − 1 T(n) = c2^n - 1 T(n)=c2n−1 , 得到 2 c − 1 = 1 2c - 1 = 1 2c−1=1

常数 c = 1 c = 1 c=1 ;

( 2 ) 代入常数获得通解 : 将常数代入通解 , 就可以得到最终的递推方程的解 ;

将常数 c = 1 c=1 c=1 代入通解 , 最终得到的就是递推方程的解 :

T ( n ) = 2 n − 1 T(n) = 2^n - 1 T(n)=2n−1

二、特解示例 2 ( 特征根为 1 的情况 )

递推方程为 : H ( n ) − H ( n − 1 ) = 7 n H(n) - H(n-1) = 7n H(n)−H(n−1)=7n , 求该递推方程通解 ?

先求其齐次部分 H ( n ) − H ( n − 1 ) = 0 H(n) - H(n-1) = 0 H(n)−H(n−1)=0 的通解 ;

写出特征方程 : x − 1 = 0 x - 1 = 0 x−1=0 , 特征根是 q = 1 q= 1 q=1 ;

齐次部分通解形式 : H ( n ) ‾ = c 1 1 n = c 1 \overline{H(n)} =c_11^n = c_1 H(n)​=c1​1n=c1​

求其特解 ( 失败尝试 ) :

上述是常系数 线性 非齐次方程 , 那么先求其 非齐次 部分对应的 特解 ,

右侧是 n n n 的 1 1 1 次方程 , 则对应的特解是 H ∗ ( n ) = P 1 n + P 2 H^*(n) = P_1n + P_2 H∗(n)=P1​n+P2​ , 将上述特解 , 代入到递推方程中 ,

     P 1 n + P 2 − ( P 1 ( n − 1 ) + P 2 ) = 7 n \ \ \ \ P_1n + P_2 - (P_1(n - 1) + P_2) =7n     P1​n+P2​−(P1​(n−1)+P2​)=7n , 化简后变成 :

     P 1 n + P 2 − P 1 n + P 1 − P 2 = 7 n \ \ \ \ P_1n + P_2 - P_1n + P_1 - P_2 = 7n     P1​n+P2​−P1​n+P1​−P2​=7n

     P 1 = 7 n \ \ \ \ P_1 = 7n     P1​=7n

此时无法解出特解中的常数 P 1 , P 2 P_1, P_2 P1​,P2​ , 因此不能设置特解为 n n n 的 1 1 1 次方程 ,

出现这种问题的原因是 , 齐次部分 , 特征方程是 x − 1 = 0 x-1 = 0 x−1=0 , 对应的的特征根是 1 1 1 ,

特征根为 1 1 1 时 , 多项式的最高项会抵消掉 , 常数项也会被抵消掉 ;

求特解 , 将 n n n 的次幂提高 1 1 1 :

提高的次幂是 特征根 1 1 1 的重复度 , 如果重复度为 2 2 2 , 则需要提高 2 2 2 次幂 ;

为了解决上述问题 , 这里需要将 n n n 的次幂提高 1 1 1 , 将特解形式中的一次方项 , 设置成平方项 , 其中常数项不设置 , 即使设置了也会抵消掉 , 无法求出常数项值 ;

将特解设置成 n n n 的 2 2 2 次方程 ,

特解形式为 H ∗ ( n ) = P 1 n 2 + P 2 n H^*(n) = P_1n^2 + P_2n H∗(n)=P1​n2+P2​n ;

将特解代入递推方程中 :

P 1 n 2 + P 2 n − ( P 1 ( n − 1 ) 2 + P 2 ( n − 1 ) ) = 7 n P_1n^2 + P_2n - ( P_1(n-1)^2 + P_2(n-1) )=7n P1​n2+P2​n−(P1​(n−1)2+P2​(n−1))=7n

P 1 n 2 + P 2 n − ( P 1 ( n 2 − 2 n + 1 ) + P 2 ( n − 1 ) ) = 7 n P_1n^2 + P_2n - ( P_1(n^2 -2n + 1) + P_2(n-1) )=7n P1​n2+P2​n−(P1​(n2−2n+1)+P2​(n−1))=7n

P 1 n 2 + P 2 n − P 1 n 2 + 2 P 1 n − P 1 − P 2 n + P 2 = 7 n P_1n^2 + P_2n - P_1n^2 + 2P_1n - P_1 - P_2n + P_2=7n P1​n2+P2​n−P1​n2+2P1​n−P1​−P2​n+P2​=7n

2 P 1 n − P 1 + P 2 = 7 n 2P_1n - P_1 + P_2=7n 2P1​n−P1​+P2​=7n

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

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

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

• n 2 n^2 n2 系数分析 : 右侧没有 n 2 n^2 n2 , 因此左侧的 n 2 n^2 n2 项之前的系数为 0 0 0 ; 左侧也没有 n 2 n^2 n2 项 , 无法抽取方程 ;

• n 1 n^1 n1 系数分析 : 右侧是 7 n 7n 7n , 因此 n n n 前的系数是 7 7 7 ; 将左侧展开 , n n n 前的系数是 2 P 1 2P_1 2P1​ ; 2 P 1 n = 7 n 2P_1n = 7n 2P1​n=7n

• n 0 n^0 n0 系数分析 : 右侧是 0 0 0 ; 将左侧展开 , n 0 n^0 n0 前的系数是 P 2 − P 1 P_2-P_1 P2​−P1​ ; P 2 − P 1 = 0 P_2-P_1 = 0 P2​−P1​=0

最终得到方程组 :

{ 2 P 1 = 7 − P 1 + P 2 = 0 \begin{cases} 2P_1 = 7 \\\\ -P_1 + P_2 = 0 \end{cases} ⎩⎪⎨⎪⎧​2P1​=7−P1​+P2​=0​

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

{ P 1 = 7 2 P 2 = 7 2 \begin{cases} P_1 = \cfrac{7}{2} \\\\ P_2 = \cfrac{7}{2} \end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​P1​=27​P2​=27​​

特解是 : H ∗ ( n ) = 7 2 n 2 + 7 2 n H^*(n) = \cfrac{7}{2} n^2 + \cfrac{7}{2}n H∗(n)=27​n2+27​n

齐次部分通解形式 : H ( n ) ‾ = c 1 \overline{H(n)} = c_1 H(n)​=c1​

最终通解是 : H ( n ) = H ( n ) ‾ + H ∗ ( n ) = c 1 + 7 2 n 2 + 7 2 n H(n) = \overline{H(n)} + H^*(n) = c_1 +\cfrac{7}{2} n^2 + \cfrac{7}{2}n H(n)=H(n)​+H∗(n)=c1​+27​n2+27​n