【组合数学】递推方程 ( 无重根递推方程求解实例 | 无重根下递推方程求解完整过程 )

文章目录

一、斐波那契数列求解
二、无重根下递推方程求解完整过程

一、斐波那契数列求解

1 . 斐波那契数列示例 :

( 1 ) 斐波那契数列 :

1 , 1 , 2 , 3 , 5 , 8 , 13 , cdots

( 2 ) 递推方程 :

F(n) = F(n-1) F(n-2)

描述 : 第

项等于第

n-1

项和第

n-2

项之和 ;

如 : 第

项的值

F(4) = 5

, 就等于

第

4-1=3

项的值

F(4-1)=F(3) = 3

加上第

4-2=2

项的值

F(4-2) = F(2) =2

;

( 3 ) 初值 :

F(0) = 1 , F(1) = 1

根据

F(0) = 1, F(1) = 1

可以计算

F(2)

, 根据

F(1),F(2)

可以计算

F(3)

, 根据

F(2)F(3)

可以计算

F(4)

cdots

, 根据

F(n-2) , F(n-1)

可以计算

F(n)

;

2 . 写出斐波那契数列的特征方程并求解特征根 :

递推方程 :

F(n) = F(n-1) F(n-2)

( 1 ) 递推方程标准形式 :

F(n) - F(n-1) - F(n-2) = 0

( 2 ) 递推方程写法 :

① 先确定特征方程的项数 : 与递推方程项数相同 ,

项 ;

② 在确定特征方程

的次幂 : 从

3-1=2

到

;

③ 初步写出没有系数的递推方程 :

x^2 x^1 x^0 = 0

④ 填充系数 : 然后将没有系数的特征方程

x^2 x^1 x^0 = 0

与

F(n) - F(n-1) - F(n-2) = 0

对应位的系数填充到特征方程中 :

x^2

前的系数对应

F(n)

项前的系数

;

x^1

前的系数对应

F(n-1)

项前的系数

-1

;

x^0

前的系数对应

F(n-2)

项前的系数

-1

;

则最终的特征方程是

1 x^2 (-1)x^1 (-1)x^0 = 0

, 化简后为 :

x^2 - x - 1 = 0

特征方程的特征根是 : 上述方程的解就是特征根 , 一般都是一元二次方程 ;

x = cfrac{1 pm sqrt{5}}{2}

参考 : 一元二次方程形式

ax^2 bx c = 0

解为 :

x = cfrac{-b pm sqrt{b^2 - 4ac}}{2a}

3 . 写出斐波那契数列的通解 :

斐波那契数列递推方程的特征根是 :

cfrac{1 pm sqrt{5}}{2}

;

q_1 = cfrac{1 sqrt{5}}{2}

q_2 =cfrac{1 - sqrt{5}}{2}

其通解的形式为

F(n) = c_1q_1^n c_2q_2^n cdots c_kq_k^n

将特征根

q_1 , q_2

代入上述通解形式后变成 :

F(n) = c_1 ( cfrac{1 sqrt{5}}{2} ) ^n c_2 ( cfrac{1 - sqrt{5}}{2} ) ^n

4 . 将递推方程初值代入通解 , 求解通解中的常数:

斐波那契数列递推方程初值 :

F(0) = 1 , F(1) = 1

代入上述初值

F(0) = 1 , F(1) = 1

到递推方程通解

F(n) = c_1 ( cfrac{1 sqrt{5}}{2} ) ^n c_2 ( cfrac{1 - sqrt{5}}{2} ) ^n

中 , 得到如下方程组 :

begin{cases} c_1 ( cfrac{1 sqrt{5}}{2} ) ^0 c_2 ( cfrac{1 - sqrt{5}}{2} ) ^0 = F(0) = 1 \\ c_1 ( cfrac{1 sqrt{5}}{2} ) ^1 c_2 ( cfrac{1 - sqrt{5}}{2} ) ^1 = F(1) = 1 end{cases}

化简后得到 :

begin{cases} c_1 c_2 = 1 \\ c_1 ( cfrac{1 sqrt{5}}{2} ) c_2 ( cfrac{1 - sqrt{5}}{2} ) = 1 end{cases}

解出上述方程组 :

c_1 =cfrac{1}{sqrt{5}} cfrac{1 sqrt{5}}{2}, c_2 =-cfrac{1}{sqrt{5}} cfrac{1 - sqrt{5}}{2}

将常数

c_1 =cfrac{1}{sqrt{5}} cfrac{1 sqrt{5}}{2}, c_2 =-cfrac{1}{sqrt{5}} cfrac{1 - sqrt{5}}{2}

代入到通解

F(n) = c_1 ( cfrac{1 sqrt{5}}{2} ) ^n c_2 ( cfrac{1 - sqrt{5}}{2} ) ^n

中 , 可以得到通解 :

F(n) = cfrac{1}{sqrt{5}} cfrac{1 sqrt{5}}{2} ( cfrac{1 sqrt{5}}{2} ) ^n - cfrac{1}{sqrt{5}} cfrac{1 - sqrt{5}}{2} ( cfrac{1 - sqrt{5}}{2} ) ^n

化简后为 :

F(n) = cfrac{1}{sqrt{5}}( cfrac{1 sqrt{5}}{2} ) ^{n 1} - cfrac{1}{sqrt{5}} ( cfrac{1 - sqrt{5}}{2} ) ^{n 1}

二、无重根下递推方程求解完整过程

无重根下递推方程求解完整过程 :

1 . 写出特征方程 :
- ( 1 ) 递推方程标准形式 : 写出递推方程标准形式 , 所有项都在等号左边 , 右边是
0
;
- ( 2 ) 特征方程项数 : 确定特征方程项数 , 与递推方程项数相同 ;
- ( 3 ) 特征方程次幂数 : 最高次幂是特征方程项数
-1
, 最低次幂
0
;
- ( 4 ) 写出没有系数的特征方程 ;
- ( 5 ) 逐位将递推方程的系数抄写到特征方程中 ;
2 . 解特征根 : 将特征方程的特征根解出来 ,

x = cfrac{-b pm sqrt{b^2 - 4ac}}{2a}

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

c_1q_1^n c_2q_2^n cdots c_kq_k^n

形式的线性组合 , 该线性组合就是递推方程的解 ;

4 . 求通解中的常数 : 将递推方程初值代入通解 , 得到

个

元方程组 , 通过解该方程组 , 得到通解中的常数 ;

( 1 ) 常数代入通解 : 得到最终的递推方程的解 ;

递推方程 -> 特征方程 -> 特征根 -> 通解 -> 代入初值求通解常数

数学

0 人点赞