遞歸數列,凡異出版社,1994年3月初版,ISBN:957694130X
線性遞迴關係之求解(下) - 中研院數學研究所
二階常係數線性齊次遞迴方程的解法(單一方程)
對於 an+p1an−1+p2an−2=0, 通解的主要思路是通過用 an=xn 代換, 把上述方程轉化到特徵方程 x2+p1x+p2=0, 解此特徵方程即得原方程的通解. 最後把初始條件帶入通解, 得到特解.
- 當 Δ>0 時, 有兩相異實根, x1=q1, x2=q2
通解為 an=c1qn1+c2qn2.
- 當 Δ=0 時, 有兩相等實根, x1=x2=q
通解為 an=(c1+c2n)qn.
- 當 Δ<0 時, 有一對共軛複數根, x1=r(cosθ+isinθ), x2=r(cosθ−isinθ)
通解為 an=an=rn(c1cosnθ+c2sinnθ).
遞迴方程組的解法
設有兩個數列 a1,a2,...an,... 和 b1,b2,...bn,... 同時滿足遞迴方程組 {an+1=p1an+q1bnbn+1=p2an+q2bn, 其中 pi, qi(i=1,2) 是實常數. 這個遞迴方程組稱為二元遞迴方程組.
二階遞迴數列的求和問題
設有兩個數列 a1,a2,...an,... 和 b1,b2,...bn,... 同時滿足遞迴方程組 {an+1=p1an+q1bnbn+1=p2an+q2bn, 其中 pi, qi(i=1,2) 是實常數. 這個遞迴方程組稱為二元遞迴方程組.
- 代入消去法
- 行列式法
對於方程組 {an+1=p1an+q1bnbn+1=p2an+q2bn, 若 |p1q1p2q2|=0, 即 p1=λp2, q1=λq2.
對於 |p1p2q1q2|≠0, 我們求形如 an=Axn, bn=Bxn 的解(A, B 為待定係數).
二階常係數線性非齊次遞迴方程的解法
若存在兩個常數 p1, p2, 對任意 n≥2, 有 an+p1an−1+p2an−2=f(n), 其中 f(n)≠0, 則稱此方程為「二階常係數線性非其次遞迴方程」, 對應之齊次特徵方程為 x2+p1x+p2=0
若存在兩個常數 p1, p2, 對任意 n≥2, 有 an+p1an−1+p2an−2=f(n), 其中 f(n)≠0, 則稱此方程為「二階常係數線性非其次遞迴方程」, 對應之齊次特徵方程為 x2+p1x+p2=0
通解 = 對應的齊次方程的通解 + 非齊次方程的任何一個特解
就 f(n) 的幾種特殊類型函數, 我們討論它的特解形式. 以下列出六種:
- f(n) 是 n 的二次多項式, 即 f(n)=a2n2+a1n+a0
把特解代入特徵方程式, 比較係數得到 {A2(1+p1+p2)=a2A1(1+p1+p2)−2A2(p1+2p2)=a1A0(1+p1+p2)−A1(p1+p2)+A2(p1+4p2)=a0
因為 x=1 不是 x2+p1x+p2=0 的根, 即 1+p1+p2≠0, 故 A2, A1 和 A0 都可以確定.
(2) 若 x=1 是特徵方程式的單根, 則特解為 a∗n=n(A2n2+A1n+A0).
(3) 若 x=1 是特徵方程式的重根, 則特解為 a∗n=n2(A2n2+A1n+A0).
- f(n) 是指數函數, 即 f(n)=c⋅kn
(1) 若 x=k 不是特徵方程式的根 則特解為 a∗n=Bkn. (B 是待解係數)
(2) 若 x=k 是特徵方程式的單根 則特解為 a∗n=nBkn.
(3) 若 x=k 是特徵方程式的重根 則特解為 a∗n=n2Bkn.
- f(n) 是正弦或餘弦函數, 即 f(n)=c⋅cosnθ 或 f(n)=c⋅sinnθ
- f(n) 是一個指數函數與多項式的積, 即 f(n)=g(n)⋅kn, 其中 k 是常數, g(n) 是關於 n 的 m 次多項式
- f(n) 是指數函數與正弦(或餘弦)函數的積, 即 f(n)=kncosnθ 或 f(n)=kncosnθ
- f(n) 是多項式與正弦(或餘弦)函數的積, 即 f(n)=g(n)cosnθ 或 f(n)=g(n)sinnθ
二階遞迴數列的求和問題
一般來說, 數列 {an} 的求和問題, 關鍵是找出其通項公式再求和. 但是, 對於遞迴數列, 我們可以不求出它的通項, 直接從它所適合的遞迴方程中求出這個遞迴數列的前 n 項的和.
假設數列 {an} 是二階遞迴列, 所適合的二階線性齊次遞迴方程為 f(x)=0(二次多項式), 則 {an} 的前 n 項和 Sn 對應之特徵方程是 (x−1)f(x)=0, 它只比 {an} 的特徵方程多了一個特徵根 x=1.
(hint: 用 an=Sn−Sn−1(n≥2) 代換)
遞迴方程的其他各種解法
當特徵方程式的根不易求出, 或遞迴方程不是線性或常係數時, 需要透過其他的途徑求解.
(hint: 用 an=Sn−Sn−1(n≥2) 代換)
遞迴方程的其他各種解法
當特徵方程式的根不易求出, 或遞迴方程不是線性或常係數時, 需要透過其他的途徑求解.
- 數學歸納法
- 迭代法與逐差法
- 變量代換法(換元法) e.g. 非線性轉成線性, 變係數轉為常係數...等
- 母函數解法
沒有留言:
張貼留言