文章目錄

• 一、斐波那契數(shù)列求解
• 二、無(wú)重根下遞推方程求解完整過(guò)程

一、斐波那契數(shù)列求解

---

1 . 斐波那契數(shù)列示例 :

( 1 ) 斐波那契數(shù)列 : $1,1,2,3,5,8,13,?$

( 2 ) 遞推方程 : $F(n)=F(n?1)+F(n?2)$

描述 : 第 $n$ 項(xiàng)等于第 $n?1$ 項(xiàng) 和 第 $n?2$ 項(xiàng)之和 ;

如 : 第 $4$ 項(xiàng)的值 $F(4)=5$ , 就等于

第 $4?1=3$ 項(xiàng)的值 $F(4?1)=F(3)=3$

加上 第 $4?2=2$ 項(xiàng)的值 $F(4?2)=F(2)=2$ ;

( 3 ) 初值 : $F(0)=1,F(1)=1$

根據(jù) $F(0)=1,F(1)=1$ 可以計(jì)算 $F(2)$ , 根據(jù) $F(1),F(2)$ 可以計(jì)算 $F(3)$ , 根據(jù) $F(2)F(3)$ 可以 計(jì)算 $F(4)$ , $?$ , 根據(jù) $F(n?2),F(n?1)$ 可以計(jì)算 $F(n)$ ;

2 . 寫出斐波那契數(shù)列的特征方程并求解特征根 :

遞推方程 : $F(n)=F(n?1)+F(n?2)$

( 1 ) 遞推方程標(biāo)準(zhǔn)形式 : $F(n)?F(n?1)?F(n?2)=0$

( 2 ) 遞推方程寫法 :

① 先確定特征方程的項(xiàng)數(shù) : 與遞推方程項(xiàng)數(shù)相同 , $3$ 項(xiàng) ;

② 在確定特征方程 $x$ 的次冪 : 從 $3?1=2$ 到 $0$ ;

③ 初步寫出沒(méi)有系數(shù)的遞推方程 : $x^2+x^1+x^0=0$

④ 填充系數(shù) : 然后將沒(méi)有系數(shù)的特征方程
$x^2+x^1+x^0=0$ 與
$F(n)?F(n?1)?F(n?2)=0$ 對(duì)應(yīng)位的系數(shù)填充到特征方程中 :

• $x^2$ 前的系數(shù) 對(duì)應(yīng) $F(n)$ 項(xiàng)前的系數(shù) $1$ ;
• $x^1$ 前的系數(shù) 對(duì)應(yīng) $F(n?1)$ 項(xiàng)前的系數(shù) $?1$ ;
• $x^0$ 前的系數(shù) 對(duì)應(yīng) $F(n?2)$ 項(xiàng)前的系數(shù) $?1$ ;

則最終的 特征方程是 $1x^2+(?1)x^1+(?1)x^0=0$ , 化簡(jiǎn)后為 :

$$x^2?x?1=0$$

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

$x=\frac{1\pm \sqrt{5}}{2}$

參考 : 一元二次方程形式
$a{x}^2+bx+c=0$
解為 : $x=\frac{?b\pm \sqrt{b^2?4ac}}{2a}$

3 . 寫出斐波那契數(shù)列的通解 :

斐波那契數(shù)列遞推方程的特征根是 : $\frac{1\pm \sqrt{5}}{2}$ ;

$q_1=\frac{1+\sqrt{5}}{2}$ , $q_2=\frac{1?\sqrt{5}}{2}$

其通解的形式為 $F(n)=c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$

將特征根 $q_1,q_2$ 代入上述通解形式后變成 :

$$F(n)=c_1(\frac{1+\sqrt{5}}{2}{)}^n+c_2(\frac{1?\sqrt{5}}{2}{)}^n$$

4 . 將遞推方程初值代入 通解 , 求解通解中的常數(shù):

斐波那契數(shù)列 遞推方程初值 : $F(0)=1,F(1)=1$

代入上述初值 $F(0)=1,F(1)=1$ 到 遞推方程通解 $F(n)=c_1(\frac{1+\sqrt{5}}{2}{)}^n+c_2(\frac{1?\sqrt{5}}{2}{)}^n$ 中 , 得到如下方程組 :

$?\begin{array}{l}{c}_1(\frac{1+\sqrt{5}}{2}{)}^0+c_2(\frac{1?\sqrt{5}}{2}{)}^0=F(0)=1\\ \\ c_1(\frac{1+\sqrt{5}}{2}{)}^1+c_2(\frac{1?\sqrt{5}}{2}{)}^1=F(1)=1\end{array}$

化簡(jiǎn)后得到 :

$?\begin{array}{l}{c}_1+c_2=1\\ \\ c_1(\frac{1+\sqrt{5}}{2})+c_2(\frac{1?\sqrt{5}}{2})=1\end{array}$

解出上述方程組 : $c_1=\frac{1}{\sqrt{5}}\frac{1+\sqrt{5}}{2},c_2=?\frac{1}{\sqrt{5}}\frac{1?\sqrt{5}}{2}$

將常數(shù) $c_1=\frac{1}{\sqrt{5}}\frac{1+\sqrt{5}}{2},c_2=?\frac{1}{\sqrt{5}}\frac{1?\sqrt{5}}{2}$ 代入到通解 $F(n)=c_1(\frac{1+\sqrt{5}}{2}{)}^n+c_2(\frac{1?\sqrt{5}}{2}{)}^n$ 中 , 可以得到通解 :

$$F(n)=\frac{1}{\sqrt{5}}\frac{1+\sqrt{5}}{2}(\frac{1+\sqrt{5}}{2}{)}^n?\frac{1}{\sqrt{5}}\frac{1?\sqrt{5}}{2}(\frac{1?\sqrt{5}}{2}{)}^n$$

化簡(jiǎn)后為 :

$$F(n)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2}{)}^{n+1}?\frac{1}{\sqrt{5}}(\frac{1?\sqrt{5}}{2}{)}^{n+1}$$

二、無(wú)重根下遞推方程求解完整過(guò)程

---

無(wú)重根下遞推方程求解完整過(guò)程 :

• 1 . 寫出特征方程 :
  • ( 1 ) 遞推方程標(biāo)準(zhǔn)形式 : 寫出遞推方程 標(biāo)準(zhǔn)形式 , 所有項(xiàng)都在等號(hào)左邊 , 右邊是 $0$ ;
  • ( 2 ) 特征方程項(xiàng)數(shù) : 確定 特征方程項(xiàng)數(shù) , 與 遞推方程項(xiàng)數(shù)相同 ;
  • ( 3 ) 特征方程次冪數(shù) : 最高次冪是 特征方程項(xiàng)數(shù) $?1$ , 最低次冪 $0$ ;
  • ( 4 ) 寫出 沒(méi)有系數(shù) 的特征方程 ;
  • ( 5 ) 逐位將遞推方程的系數(shù) 抄寫 到特征方程中 ;
• 2 . 解特征根 : 將 特征方程的特征根解出來(lái) , $x=\frac{?b\pm \sqrt{b^2?4ac}}{2a}$
• 3 . 構(gòu)造遞推方程的通解 : 構(gòu)造 $c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 形式的線性組合 , 該線性組合就是遞推方程的解 ;
• 4 . 求通解中的常數(shù) : 將遞推方程初值代入通解 , 得到 $k$ 個(gè) $k$ 元方程組 , 通過(guò)解該方程組 , 得到通解中的常數(shù) ;
  • ( 1 ) 常數(shù)代入通解 : 得到最終的遞推方程的解 ;

遞推方程 -> 特征方程 -> 特征根 -> 通解 -> 代入初值求通解常數(shù)

總結(jié)

以上是生活随笔為你收集整理的【组合数学】递推方程 ( 无重根递推方程求解实例 | 无重根下递推方程求解完整过程 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。