文章目錄

• 一、通解定義
• 二、無重根下遞推方程通解結構定理

一、通解定義

---

遞推方程解的形式 : 滿足 $H(n)?a_{1}H(n?1)?a_{2}H(n?2)???a_{k}H(n?k)=0$ 公式的所有遞推方程 , 都具有 $c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 形式的解 ;

下面開始討論之前得到的 解的形式 $c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 是否概括了所有解的共同模式 ; 數(shù)列中所有的項是否都遵從該模式 ;

如果有些不同的初值 , 不遵循上述模式 , 那該解就 不能作為 所有的 該族 遞推方程 的解的通用格式 ;

遞推方程通解定義 :

如果遞推方程 , 每個解 $h(n)$ 都存在一組常數(shù) $c_1^{\prime },c_2^{\prime },?,c_k^{\prime }$ ,

使得 $h(n)=c_1^{\prime }{q}_1^n+c_2^{\prime }{q}_2^n+?+c_k^{\prime }{q}_k^n$ 成立 ,

則稱 $c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 是 遞推方程的 通解 ;

分析 :

遞推方程解個數(shù) : 遞推方程有多少解呢 , 將特征方程解出特征根 , 特征根個數(shù) , 就是遞推方程解的個數(shù) ;

常數(shù)確定 : $h(n)$ 是數(shù)列的第 $n$ 項 , $h(n)$ 是否能表達成 $c_1^{\prime }{q}_1^n+c_2^{\prime }{q}_2^n+?+c_k^{\prime }{q}_k^n$ 格式 , 找到一組常數(shù) $c_1^{\prime },c_2^{\prime },?,c_k^{\prime }$ , 使得上述解的格式確定下來即可 , 這些常數(shù)是由初值確認的 ;

二、無重根下遞推方程通解結構定理

---

無重根下遞推方程通解結構定理 :

如果 $q_1,q_2,?,q_k$ 是 遞推方程 不相等 的 特征根 ,

則 $H(n)=c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 為通解 ;

隨便在遞推方程中 , 拿出一個方程出來 , 其解一定是 $H(n)=c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 格式 , 只不過是不同的初值 , 對應不同的 $c_1,c_2,?,c_k$ 常數(shù) ;

證明上述定理 :

$H(n)=c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 是遞推方程的解 , 由之前已經(jīng)證明過的定理得出 :

• $q$ 是特征方程的特征根 $?$ $q^n$ 是遞推方程的解
• $h_1(n)$ 和 $h_2(n)$ 都是同一個遞推方程的解 , $c_1,c_2$ 是任意常數(shù) , 兩個解的線性組合 $c_1{h}_1(n)+c_2{h}_2(n)$ , 這個線性組合也是遞推方程的解 ;

下面證明任意一個解都可以表達成通解的格式 ;

假定 $h(n)$ 是任意一個解 ,

該遞推方程有 $k$ 個初值如下 :

• $h(0)=b_0$
• $h(1)=b_1$
• $h(2)=b_2$

$?$

• $h(k?1)=b_{k?1}$

將 $k$ 個初值 , 代入上述通解格式 $H(n)=c_1{q}_1^n+c_2{q}_2^n+?+c_k{q}_k^n$ 中 , 得到如下方程組 :

$?\begin{array}{l}{c}_1^{\prime }+c_2^{\prime }+?+c_k^{\prime }=b_0\\ \\ c_1^{\prime }{q}_1+c_2^{\prime }{q}_2+?+c_k^{\prime }{q}_k=b_1\\ \\ ?\\ \\ c_1^{\prime }{q}_1^{k?1}+c_2^{\prime }{q}_2^{k?1}+?+c_k^{\prime }{q}_k^{k?1}=b^{k?1}\end{array}$

上述的方程組是否能唯一地確定一組 $c_1,c_2,?,c_k$ 常數(shù) , 如果可以說明該解是遞推方程的通解 , 如果不能 , 則該解不是遞推方程的通解 ;

將上述 $c_1,c_2,?,c_k$ 看做 $k$ 個未知數(shù) , 并且 該方程組中有 $k$ 個方程 , 該方程組存在唯一解的條件是 :

系數(shù)行列式 不等于 $0$ ,

符號表示為 : $\prod _{1\le i<j\le k}(q_i?q_k)=0$

文字描述 : 系數(shù)行列式是所有 系數(shù) $q_1,q_2,?,q_{k?1}$ 的 兩兩相減乘積不為 $0$ , 即 $q_1,q_2,?,q_{k?1}$ 中 不存在兩兩相等的情況 ;

總結

以上是生活随笔為你收集整理的【组合数学】递推方程 ( 通解定义 | 无重根下递推方程通解结构定理 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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