一階線性遞推指形如 a n + 1 = f ( a n ) a_{n+1}=f(a_n) a n + 1 = f ( a n ) f f f
設數列 { a n } \lbrace a_n\rbrace { a n } a n + 1 = p a n + q a_{n+1}=pa_n+q a n + 1 = p a n + q p q ( p − 1 ) ≠ 0 pq(p-1)\not=0 pq ( p − 1 ) = 0
假設遞推公式可寫成 a n + 1 + t = p ( a n + t ) a_{n+1}+t=p(a_n+t) a n + 1 + t = p ( a n + t ) t = q / ( p − 1 ) t=q/(p-1) t = q / ( p − 1 ) { a n + q p − 1 } \lbrace a_n+\frac{q}{p-1}\rbrace { a n + p − 1 q }
這種方法也可理解為尋找不動點 的方法.
圖為遞推數列 { a n } \lbrace a_n\rbrace { a n } a 1 = 1 a_1=1 a 1 = 1 ( a 1 , 0 ) (a_1,0) ( a 1 , 0 ) f f f a 2 , a 3 , a 4 , … , a n a_2,a_3,a_4,\dots,a_n a 2 , a 3 , a 4 , … , a n A A A f f f y = x y=x y = x
解線性方程 p x + q = x px+q=x p x + q = x q / ( p − 1 ) q/(p-1) q / ( p − 1 ) t t t { b n } \lbrace b_n\rbrace { b n } b n = a n + q / ( p − 1 ) b_n=a_n+q/(p-1) b n = a n + q / ( p − 1 ) f ( x ) = p x + q f(x)=px+q f ( x ) = p x + q p q ( p − 1 ) ≠ 0 pq(p-1)\not=0 pq ( p − 1 ) = 0
若將遞推式稍加改動, 變為 a n + 1 = p a n + q n + r a_{n+1}=pa_n+qn+r a n + 1 = p a n + q n + r
設 a n + 1 + k ( n + 1 ) + l = p ( a n + k n + l ) a_{n+1}+k(n+1)+l=p(a_n+kn+l) a n + 1 + k ( n + 1 ) + l = p ( a n + k n + l )
{ ( p − 1 ) k = q p l − k − l = r
\begin{cases}
(p-1)k=q\\
pl-k-l=r
\end{cases}
{ ( p − 1 ) k = q pl − k − l = r 解得 k = q / ( p − 1 ) k=q/(p-1) k = q / ( p − 1 ) l = r / ( p − 1 ) + q / ( p − 1 ) 2 l=r/(p-1)+q/(p-1)^2 l = r / ( p − 1 ) + q / ( p − 1 ) 2
{ a n + q p − 1 n + ( r p − 1 + q ( p − 1 ) 2 ) } \left\lbrace a_n+\frac{q}{p-1}n+\left(\frac{r}{p-1}+\frac{q}{(p-1)^2}\right)\right\rbrace { a n + p − 1 q n + ( p − 1 r + ( p − 1 ) 2 q ) } 是等比數列, 之後的步驟同上.
二階線性遞推指形如 a n + 2 = f ( a n + 1 ) + g ( a n ) a_{n+2}=f(a_{n+1})+g(a_n) a n + 2 = f ( a n + 1 ) + g ( a n ) f , g f,g f , g
先考慮最基本的情況, 即 a n + 2 = p a n + 1 + q a n a_{n+2}=pa_{n+1}+qa_n a n + 2 = p a n + 1 + q a n
假設 a n + 2 − s a n + 1 = t ( a n + 2 − s a n ) a_{n+2}-sa_{n+1}=t(a_{n+2}-sa_n) a n + 2 − s a n + 1 = t ( a n + 2 − s a n ) { a n } \lbrace a_n\rbrace { a n } s s s t t t a n + 2 − t a n + 1 = s ( a n + 2 − t a n ) a_{n+2}-ta_{n+1}=s(a_{n+2}-ta_n) a n + 2 − t a n + 1 = s ( a n + 2 − t a n )
展開與原式比較可得方程組:
{ s + t = p s t = − q
\begin{cases}
s+t=p\\
st=-q
\end{cases}
{ s + t = p s t = − q 根據韋達定理, s , t s,t s , t x 2 − p x − q = 0 x^2-px-q=0 x 2 − p x − q = 0 特征方程 , s , t s,t s , t 特征根 , 因此該方法也被稱為特征根法.
接下來分兩種情況考慮.
若 s = t s=t s = t a n + 2 − s a n + 1 = s ( a n + 1 − s a n ) a_{n+2}-sa_{n+1}=s(a_{n+1}-sa_n) a n + 2 − s a n + 1 = s ( a n + 1 − s a n ) a n + 2 = s n ( a 2 − s a 1 ) + s a n + 1 a_{n+2}=s^n(a_2-sa_1)+sa_{n+1} a n + 2 = s n ( a 2 − s a 1 ) + s a n + 1
s a n + 1 = s n ( a 2 − s a 1 ) + s 2 a n s 2 a n = s n ( a 2 − s a 1 ) + s 3 a n − 1 ⋯ ⋯ s n − 1 a 3 = s n ( a 2 − s a 1 ) + s n a 2
\begin{align*}
&sa_{n+1}=s^n(a_2-sa_1)+s^2a_n\\
&s^2a_n=s^n(a_2-sa_1)+s^3a_{n-1}\\
&\cdots\cdots\\
&s^{n-1}a_3=s^n(a_2-sa_1)+s^na_2
\end{align*}
s a n + 1 = s n ( a 2 − s a 1 ) + s 2 a n s 2 a n = s n ( a 2 − s a 1 ) + s 3 a n − 1 ⋯⋯ s n − 1 a 3 = s n ( a 2 − s a 1 ) + s n a 2 再用累加, 便可得到:
a n + 2 = n ⋅ s n ( a 2 − s a 1 ) + s n a 2 a_{n+2}=n\cdot s^n(a_2-sa_1)+s^na_2 a n + 2 = n ⋅ s n ( a 2 − s a 1 ) + s n a 2 即
a n = ( n − 2 ) ⋅ s n − 2 ( a 2 − s a 1 ) + s n − 2 a 2 a_{n}=(n-2)\cdot s^{n-2}(a_2-sa_1)+s^{n-2}a_2 a n = ( n − 2 ) ⋅ s n − 2 ( a 2 − s a 1 ) + s n − 2 a 2 若 s ≠ t s\not=t s = t s , t s,t s , t
a n + 1 − s a n = t n − 1 ( a 2 − s a 1 ) a n + 1 − t a n = s n − 1 ( a 2 − t a 1 )
\begin{align*}
a_{n+1}-sa_n&=t^{n-1}(a_2-sa_1)\\
a_{n+1}-ta_n&=s^{n-1}(a_2-ta_1)
\end{align*}
a n + 1 − s a n a n + 1 − t a n = t n − 1 ( a 2 − s a 1 ) = s n − 1 ( a 2 − t a 1 ) 兩式相減可得:
( t − s ) a n = t n − 1 ( a 2 − s a 1 ) − s n − 1 ( a 2 − t a 1 ) (t-s)a_n=t^{n-1}(a_2-sa_1)-s^{n-1}(a_2-ta_1) ( t − s ) a n = t n − 1 ( a 2 − s a 1 ) − s n − 1 ( a 2 − t a 1 ) 於是得到通項公式:
a n = 1 t − s ( t n − 1 ( a 2 − s a 1 ) − s n − 1 ( a 2 − t a 1 ) ) a_n=\frac{1}{t-s}\left(t^{n-1}(a_2-sa_1)-s^{n-1}(a_2-ta_1)\right) a n = t − s 1 ( t n − 1 ( a 2 − s a 1 ) − s n − 1 ( a 2 − t a 1 ) ) 特別地, 當 p = q = a 1 = a 2 = 1 p=q=a_1=a_2=1 p = q = a 1 = a 2 = 1
{ s = 1 − 5 2 t = 1 + 5 2
\begin{cases}
s=\frac{1-\sqrt{5}}{2}\\
t=\frac{1+\sqrt{5}}{2}
\end{cases}
{ s = 2 1 − 5 t = 2 1 + 5 代入上式可得 Fibonacci 數列通項公式:
a n = 1 t − s ( t n − s n ) = 5 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] a_n=\frac{1}{t-s}(t^{n}-s^{n})=\frac{\sqrt{5}}{5}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] a n = t − s 1 ( t n − s n ) = 5 5 [ ( 2 1 + 5 ) n − ( 2 1 − 5 ) n ] 若特徵方程沒有實根, 那它必有兩個共軛複根 s , t s,t s , t a n + 2 = a n + 1 − a n a_{n+2}=a_{n+1}-a_n a n + 2 = a n + 1 − a n a 1 = 1 a_1=1 a 1 = 1 a 2 = 2 a_2=2 a 2 = 2 x 2 − x + 1 = 0 x^2-x+1=0 x 2 − x + 1 = 0 s , t = ( 1 ± 3 i ) / 2 s,t=(1\pm\sqrt3\mathrm{i})/2 s , t = ( 1 ± 3 i ) /2
a n = − 3 i 3 [ ( 1 + 3 i 2 ) n − 1 ⋅ ( 3 + 3 i 2 ) − ( 1 − 3 i 2 ) n − 1 ⋅ ( 3 − 3 i 2 ) ] a_n=-\frac{\sqrt3\mathrm{i}}{3}\left[\left(\frac{1+\sqrt3\mathrm{i}}{2}\right)^{n-1}\cdot\left(\frac{3+\sqrt{3}\mathrm{i}}{2}\right)-\left(\frac{1-\sqrt3\mathrm{i}}{2}\right)^{n-1}\cdot\left(\frac{3-\sqrt{3}\mathrm{i}}{2}\right)\right] a n = − 3 3 i ( 2 1 + 3 i ) n − 1 ⋅ ( 2 3 + 3 i ) − ( 2 1 − 3 i ) n − 1 ⋅ ( 2 3 − 3 i ) 計算該數列的前幾項, 發現其為以 1 , 2 , 1 , − 1 , − 2 , − 1 1,2,1,-1,-2,-1 1 , 2 , 1 , − 1 , − 2 , − 1 周期性 數列, 顯然這樣的性質在特征根為實數的二階遞推數列中是不可能的. 那麼, 滿足什麼條件的數列有此性質呢?
設 s , t = r ( cos θ ± i sin θ ) s,t=r(\cos\theta\pm\mathrm{i}\sin\theta) s , t = r ( cos θ ± i sin θ )
a n = r n − 2 sin θ [ a 2 sin ( n − 1 ) θ − r a 1 sin ( n − 2 ) θ ] a_n=\frac{r^{n-2}}{\sin\theta}\left[a_2\sin(n-1)\theta-ra_1\sin(n-2)\theta\right] a n = sin θ r n − 2 [ a 2 sin ( n − 1 ) θ − r a 1 sin ( n − 2 ) θ ] 然後一個含複數的式子就直接轉換成了一個簡單的三角函數, 用該式計算a n a_n a n
a 3 = r sin θ ( a 2 sin 2 θ − r a 1 sin θ ) a 4 = r 2 sin θ ( a 2 sin 3 θ − r a 1 sin 2 θ ) a 5 = r 3 sin θ ( a 2 sin 4 θ − r a 1 sin 3 θ ) ⋯ ⋯
\begin{align*}
a_3&=\frac{r}{\sin\theta}(a_2\sin2\theta-ra_1\sin\theta)\\
a_4&=\frac{r^2}{\sin\theta}(a_2\sin3\theta-ra_1\sin2\theta)\\
a_5&=\frac{r^3}{\sin\theta}(a_2\sin4\theta-ra_1\sin3\theta)\\
&\cdots\cdots
\end{align*}
a 3 a 4 a 5 = sin θ r ( a 2 sin 2 θ − r a 1 sin θ ) = sin θ r 2 ( a 2 sin 3 θ − r a 1 sin 2 θ ) = sin θ r 3 ( a 2 sin 4 θ − r a 1 sin 3 θ ) ⋯⋯ 由此可知, 若數列存在周期性, 必須滿足如下兩點:
特征根的模長 r = 1 r=1 r = 1
輻角 θ = p π / q \theta=p\pi/q θ = p π / q p , q ∈ Z ∖ { 0 } p,q\in\mathbb{Z}\setminus\lbrace 0\rbrace p , q ∈ Z ∖ { 0 } gcd ( p , q ) = 1 \gcd(p,q)=1 g cd( p , q ) = 1
滿足這兩點後, 數列必為周期數列, 且可以確定周期長度為 2 q / gcd ( p , 2 ) 2q/\gcd(p,2) 2 q / g cd( p , 2 )
對於 a n + 2 = p a n + 1 + q a n + r a_{n+2}=pa_{n+1}+qa_n+r a n + 2 = p a n + 1 + q a n + r a n + 2 = p a n + 1 + q a n + r n + s a_{n+2}=pa_{n+1}+qa_n+rn+s a n + 2 = p a n + 1 + q a n + r n + s
對於 k k k a n + k = c 1 a n + k − 1 + c 2 a n + k − 2 + ⋯ + c k a n a_{n+k}=c_1a_{n+k-1}+c_2a_{n+k-2}+\cdots+c_ka_n a n + k = c 1 a n + k − 1 + c 2 a n + k − 2 + ⋯ + c k a n k ≥ 2 k\geq2 k ≥ 2
用矩陣來表示遞推關係, 那麼 Fibonacci 數列就可表示為:
[ a n + 1 a n ] = [ 1 1 1 0 ] [ a n a n − 1 ] \begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}a_{n}\\a_{n-1}\end{bmatrix} [ a n + 1 a n ] = [ 1 1 1 0 ] [ a n a n − 1 ] 可以直接連乘起來得到通項公式:
[ a n + 1 a n ] = [ 1 1 1 0 ] n [ 1 1 ] \begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^n\begin{bmatrix}1\\1\end{bmatrix} [ a n + 1 a n ] = [ 1 1 1 0 ] n [ 1 1 ] 同樣地, k k k
[ a n a n − 1 ⋯ a n − k + 2 a n − k + 1 ] = [ c 1 c 2 ⋯ c k − 1 c k 1 0 ⋯ 0 0 0 1 ⋯ 0 0 ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ 0 0 0 0 ⋯ 1 0 ] n − 1 [ a k a k − 1 ⋯ a 2 a 1 ] \begin{bmatrix}a_{n}\\a_{n-1}\\\cdots\\a_{n-k+2}\\a_{n-k+1}\end{bmatrix}=\begin{bmatrix}c_1&c_2&\cdots&c_{k-1}&c_k\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&0&0\\0&0&\cdots&1&0\end{bmatrix}^{n-1}\begin{bmatrix}a_{k}\\a_{k-1}\\\cdots\\a_{2}\\a_{1}\end{bmatrix} a n a n − 1 ⋯ a n − k + 2 a n − k + 1 = c 1 1 0 ⋮ 0 0 c 2 0 1 ⋮ 0 0 ⋯ ⋯ ⋯ ⋱ ⋯ ⋯ c k − 1 0 0 ⋮ 0 1 c k 0 0 ⋮ 0 0 n − 1 a k a k − 1 ⋯ a 2 a 1 理論上求出上式中 k × k k\times k k × k n n n
好吧現在學過線性代數了, 但是要想完全解決這邊留的問題大概還是不太可能, 當然關鍵是現在對這個問題也沒那麼大興趣了. 下面僅用線性代數知識求出 Fibonacci 數列的通項公式.
設
X n = [ a n + 1 a n ] , A = [ 1 1 1 0 ]
X_n=\begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix},\enspace A=\begin{bmatrix}1&1\\1&0\end{bmatrix}
X n = [ a n + 1 a n ] , A = [ 1 1 1 0 ] 則 X n = A n − 1 X 1 X_n=A^{n-1}X_1 X n = A n − 1 X 1
X 1 = [ 1 1 ] X_1=\begin{bmatrix}1\\1\end{bmatrix} X 1 = [ 1 1 ] 下面寫出 A A A
∣ λ E − A ∣ = ∣ λ − 1 − 1 − 1 λ ∣ = λ 2 − λ − 1 |\lambda E-A|=\begin{vmatrix}\lambda-1&-1\\-1&\lambda\end{vmatrix}=\lambda^2-\lambda-1 ∣ λ E − A ∣ = λ − 1 − 1 − 1 λ = λ 2 − λ − 1 令 ∣ λ E − A ∣ = 0 |\lambda E-A|=0 ∣ λ E − A ∣ = 0
λ 1 = 1 + 5 2 , λ 2 = 1 − 5 2 \lambda_1=\frac{1+\sqrt{5}}{2},\enspace\lambda_2=\frac{1-\sqrt{5}}{2} λ 1 = 2 1 + 5 , λ 2 = 2 1 − 5 令
T = [ λ 1 λ 2 1 1 ] T=\begin{bmatrix}\lambda_1&\lambda_2\\1&1\end{bmatrix} T = [ λ 1 1 λ 2 1 ] 從而可以把 A A A
T − 1 A T = [ λ 1 0 0 λ 2 ] , A = T [ λ 1 0 0 λ 2 ] T − 1 T^{-1}AT=\begin{bmatrix}\lambda_1&0\\0&\lambda_2\end{bmatrix},\enspace A=T\begin{bmatrix}\lambda_1&0\\0&\lambda_2\end{bmatrix}T^{-1} T − 1 A T = [ λ 1 0 0 λ 2 ] , A = T [ λ 1 0 0 λ 2 ] T − 1 再進行連乘就容易多了, 對角矩陣兩邊的 T T T T − 1 T^{-1} T − 1
X n = [ a n + 1 a n ] = T [ λ 1 n − 1 0 0 λ 2 n − 1 ] T − 1 [ 1 1 ] = 1 5 [ λ 1 n + 1 − λ 2 n + 1 λ 1 n − λ 2 n ] X_n=\begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix}=T\begin{bmatrix}\lambda_1^{n-1}&0\\0&\lambda_2^{n-1}\end{bmatrix}T^{-1}\begin{bmatrix}1\\1\end{bmatrix}=\frac{1}{\sqrt{5}}\begin{bmatrix}\lambda_1^{n+1}-\lambda_2^{n+1}\\\lambda_1^{n}-\lambda_2^{n}\end{bmatrix} X n = [ a n + 1 a n ] = T [ λ 1 n − 1 0 0 λ 2 n − 1 ] T − 1 [ 1 1 ] = 5 1 [ λ 1 n + 1 − λ 2 n + 1 λ 1 n − λ 2 n ] 即
a n = 1 5 ( λ 1 n − λ 2 n ) a_n=\frac{1}{\sqrt{5}}\left(\lambda_1^n-\lambda_2^n\right) a n = 5 1 ( λ 1 n − λ 2 n ) 這與我們之前用初等方法得到的結果是相同的.
相應地, 推廣到 k k k k k k k k k k k k k k k n n n
對於分子無常數項的分式遞推數列, 直接兩邊取倒數即可.
遞推關係 (注意遞推式函數圖像經過原點)
a n = p a n − 1 q a n − 1 + r a_n=\frac{pa_{n-1}}{qa_{n-1}+r} a n = q a n − 1 + r p a n − 1 取倒數得
1 a n = q p ⋅ 1 a n − 1 + r p \frac{1}{a_n}=\frac{q}{p}\cdot\frac{1}{a_{n-1}}+\frac{r}{p} a n 1 = p q ⋅ a n − 1 1 + p r 於是得到一階線性遞推數列 { 1 / a n } \lbrace 1/a_n\rbrace { 1/ a n }
對於一般形式的分式遞推數列, 即形如 x n = ( a x n − 1 + b ) / ( c x n − 1 + d ) x_n=(ax_{n-1}+b)/(cx_{n-1}+d) x n = ( a x n − 1 + b ) / ( c x n − 1 + d )
有了一階線性遞推的經驗, 我們直接考慮方程
a x + b c x + d = x \frac{ax+b}{cx+d}=x c x + d a x + b = x 即 c x 2 + ( d − a ) x − b = 0 cx^2+(d-a)x-b=0 c x 2 + ( d − a ) x − b = 0 特征方程 , 其根同樣可稱為特征根 .
解這個二次方程可以得到兩個根, 下面分兩種情況考慮.
若 x 1 = x 2 = α x_1=x_2=\alpha x 1 = x 2 = α α \alpha α
對於此問題, 有一種直觀的理解方法. 像本文一開始那樣用圖像表示遞推過程:
如圖, A A A ( α , α ) (\alpha,\alpha) ( α , α ) f f f y = x y=x y = x A A A α \alpha α A A A y = x y=x y = x − 1 -1 − 1 1 1 1
{ g ( x ) = p x q x + r g ′ ( 0 ) = 1 ⇒ 1 g ( x ) = 1 x + λ
\begin{cases}
g(x)=\frac{px}{qx+r}\\
g'(0)=1
\end{cases}
\Rightarrow \frac{1}{g(x)}=\frac{1}{x}+\lambda
{ g ( x ) = q x + r p x g ′ ( 0 ) = 1 ⇒ g ( x ) 1 = x 1 + λ 其中 p , q , r , λ p,q,r,\lambda p , q , r , λ
但這好像有些兜圈子了, 更 “簡單” 的方法是直接把 α = ( a − d ) / 2 c \alpha=(a-d)/2c α = ( a − d ) /2 c
1 x n − α = 1 x n − 1 − α + 2 c a + d \frac{1}{x_{n}-\alpha}=\frac{1}{x_{n-1}-\alpha}+\frac{2c}{a+d} x n − α 1 = x n − 1 − α 1 + a + d 2 c 例如, x n = ( x n − 1 − 1 ) / ( x n − 1 + 3 ) x_n=(x_{n-1}-1)/(x_{n-1}+3) x n = ( x n − 1 − 1 ) / ( x n − 1 + 3 ) x 2 + 2 x + 1 = 0 x^2+2x+1=0 x 2 + 2 x + 1 = 0 x 1 = x 2 = − 1 x_1=x_2=-1 x 1 = x 2 = − 1
x n + 1 = x n − 1 − 1 x n − 1 + 3 + 1 = 2 x n − 1 + 2 x n − 1 + 3 x_n+1=\frac{x_{n-1}-1}{x_{n-1}+3}+1=\frac{2x_{n-1}+2}{x_{n-1}+3} x n + 1 = x n − 1 + 3 x n − 1 − 1 + 1 = x n − 1 + 3 2 x n − 1 + 2 兩邊取倒數得:
1 x n + 1 = 1 x n + 1 + 1 + 1 2 \frac{1}{x_n+1}=\frac{1}{x_{n+1}+1}+\frac{1}{2} x n + 1 1 = x n + 1 + 1 1 + 2 1 若 x 1 = β 1 ≠ x 2 = β 2 x_1=\beta_1\not=x_2=\beta_2 x 1 = β 1 = x 2 = β 2
x n − β 1 = a x n − 1 + b c x n − 1 + d − β 1 = ( a − β 1 c ) ( x n − 1 − β 1 ) c x n − 1 + d x n − β 2 = a x n − 1 + b c x n − 1 + d − β 2 = ( a − β 2 c ) ( x n − 1 − β 2 ) c x n − 1 + d
\begin{align*}
x_n-\beta_1=\frac{ax_{n-1}+b}{cx_{n-1}+d}-\beta_1=\frac{(a-\beta_1c)(x_{n-1}-\beta_1)}{cx_{n-1}+d}\\
x_n-\beta_2=\frac{ax_{n-1}+b}{cx_{n-1}+d}-\beta_2=\frac{(a-\beta_2c)(x_{n-1}-\beta_2)}{cx_{n-1}+d}
\end{align*}
x n − β 1 = c x n − 1 + d a x n − 1 + b − β 1 = c x n − 1 + d ( a − β 1 c ) ( x n − 1 − β 1 ) x n − β 2 = c x n − 1 + d a x n − 1 + b − β 2 = c x n − 1 + d ( a − β 2 c ) ( x n − 1 − β 2 ) 兩式相除得到:
x n − β 1 x n − β 2 = a − β 1 c a − β 2 c ⋅ x n − 1 − β 1 x n − 1 − β 2 \frac{x_n-\beta_1}{x_n-\beta_2}=\frac{a-\beta_1c}{a-\beta_2c}\cdot\frac{x_{n-1}-\beta_1}{x_{n-1}-\beta_2} x n − β 2 x n − β 1 = a − β 2 c a − β 1 c ⋅ x n − 1 − β 2 x n − 1 − β 1 得到一個相關的等比數列, 略加處理即可得到原數列通項公式.
例如, x n = ( x n − 1 − 2 ) / ( x n − 1 + 4 ) x_n=(x_{n-1}-2)/(x_{n-1}+4) x n = ( x n − 1 − 2 ) / ( x n − 1 + 4 ) x 2 + 3 x + 2 = 0 x^2+3x+2=0 x 2 + 3 x + 2 = 0 x 1 = − 1 x_1=-1 x 1 = − 1 x 2 = − 2 x_2=-2 x 2 = − 2
x n + 1 = 2 x n − 1 + 2 x n − 1 + 4 x n + 2 = 3 x n − 1 + 6 x n − 1 + 4
\begin{align*}
x_n+1=\frac{2x_{n-1}+2}{x_{n-1}+4}\\
x_n+2=\frac{3x_{n-1}+6}{x_{n-1}+4}
\end{align*}
x n + 1 = x n − 1 + 4 2 x n − 1 + 2 x n + 2 = x n − 1 + 4 3 x n − 1 + 6 兩式相除得到:
x n + 1 x n + 2 = 2 3 ⋅ x n − 1 + 1 x n − 1 + 2 \frac{x_n+1}{x_n+2}=\frac{2}{3}\cdot\frac{x_{n-1}+1}{x_{n-1}+2} x n + 2 x n + 1 = 3 2 ⋅ x n − 1 + 2 x n − 1 + 1 以上就是基本的不動點法. 事實上, 題目中還可能出現高次的分式遞推, 本質也是用上述方法, 但需要一些額外的處理, 具體情況具體分析.
如果分式遞推數列特征根是複數, 那麼不動點就不存在了. 正如在二階線性遞推部分所討論的, 可以將複根代入公式, 不影響最終結果. 那麼就產生了一個問題: 這樣的情況下該分式遞推數列是否可能是周期數列?
不妨先看一下一些不動點不存在的分式數列迭代圖像:
遞推公式: a n = ( a n − 1 − 1 ) / ( a n − 1 + 1 ) a_n=(a_{n-1}-1)/(a_{n-1}+1) a n = ( a n − 1 − 1 ) / ( a n − 1 + 1 ) x 1 = i x_1=\mathrm{i} x 1 = i x 2 = − i x_2=-\mathrm{i} x 2 = − i 8 8 8
遞推公式: a n = ( a n − 1 − 2 ) / ( a n − 1 + 2 ) a_n=(a_{n-1}-2)/(a_{n-1}+2) a n = ( a n − 1 − 2 ) / ( a n − 1 + 2 ) x 1 = ( − 1 + 7 i ) / 2 x_1=(-1+\sqrt{7}\mathrm{i})/2 x 1 = ( − 1 + 7 i ) /2 x 2 = ( − 1 − 7 i ) / 2 x_2=(-1-\sqrt{7}\mathrm{i})/2 x 2 = ( − 1 − 7 i ) /2
遞推公式: a n = ( − a n − 1 − 5 ) / ( a n − 1 + 1 ) a_n=(-a_{n-1}-5)/(a_{n-1}+1) a n = ( − a n − 1 − 5 ) / ( a n − 1 + 1 ) x 1 = − 1 + 2 i x_1=-1+2\mathrm{i} x 1 = − 1 + 2 i x 2 = − 1 − 2 i x_2=-1-2\mathrm{i} x 2 = − 1 − 2 i 4 4 4
看過以上三個例子, 基本就能總結規律了. 與二階線性遞推中對特征根模長與輻角的要求不同, 這裡的要求是複根的實部和虛部都為有理數. 這樣, 對初始值進行迭代就終將回歸自身, 形成周期, 否則會迭代到函數上的每一點. 當然, 以上僅為猜想, 並沒有證明, 等有時間了再研究一下這個問題.
上面說的全都是套路性的方法, 實際的數列題當然不可能這麼簡單, 一般需要對非線性的遞推式進行特殊處理. 下面舉兩道例題.
例1 設 a 1 = a 2 = 1 a_1=a_2=1 a 1 = a 2 = 1 a n = ( a n − 1 2 + 2 ) / a n − 2 a_n=(a_{n-1}^2+2)/a_{n-2} a n = ( a n − 1 2 + 2 ) / a n − 2 { a n } \lbrace a_n\rbrace { a n }
又是二階又是分式遞推, 還是二次的, 第一眼看完全沒有頭緒. 那就憑感覺化簡一下, 第一步先把分子乘過去, 使兩邊齊次:
a n a n − 2 = a n − 1 2 + 2 a_na_{n-2}=a_{n-1}^2+2 a n a n − 2 = a n − 1 2 + 2 然後再寫一項:
a n + 1 a n − 1 = a n 2 + 2 a_{n+1}a_{n-1}=a_{n}^2+2 a n + 1 a n − 1 = a n 2 + 2 兩式相減消去常數項:
a n + 1 a n − 1 − a n a n − 2 = a n 2 − a n − 1 2 a_{n+1}a_{n-1}-a_na_{n-2}=a_n^2-a_{n-1}^2 a n + 1 a n − 1 − a n a n − 2 = a n 2 − a n − 1 2 這樣, 式子的項數反而增加到了4項, 但還是沒有明顯的規律. 繼續化簡, 整理一下, 提取公因數:
a n ( a n + a n − 2 ) = a n − 1 ( a n + 1 + a n − 1 ) a_n(a_n+a_{n-2})=a_{n-1}(a_{n+1}+a_{n-1}) a n ( a n + a n − 2 ) = a n − 1 ( a n + 1 + a n − 1 ) 居然直接就配成常數列了, 但下標不連續很不方便, 於是把括號除到另一半得到:
a n a n + 1 + a n − 1 = a n − 1 a n + a n − 2 = a 2 a 3 + a 1 = 1 4 \frac{a_n}{a_{n+1}+a_{n-1}}=\frac{a_{n-1}}{a_n+a_{n-2}}=\frac{a_2}{a_3+a_1}=\frac{1}{4} a n + 1 + a n − 1 a n = a n + a n − 2 a n − 1 = a 3 + a 1 a 2 = 4 1 於是可知 4 a n = a n + 1 + a n − 1 4a_n=a_{n+1}+a_{n-1} 4 a n = a n + 1 + a n − 1
例2 設 x 0 = 0 x_0=0 x 0 = 0 x n + 1 = 3 x n + 8 x n 2 + 1 x_{n+1}=3x_n+\sqrt{8x_n^2+1} x n + 1 = 3 x n + 8 x n 2 + 1 { x n } \lbrace x_n\rbrace { x n }
還是往齊次去湊, 把 3 x n 3x_n 3 x n
x n + 1 2 − 6 x n x n + 1 + x n 2 − 1 = 0 x_{n+1}^2-6x_nx_{n+1}+x_n^2-1=0 x n + 1 2 − 6 x n x n + 1 + x n 2 − 1 = 0 這是個對稱式, 所以再寫一項:
x n − 1 2 − 6 x n x n − 1 + x n 2 − 1 = 0 x_{n-1}^2-6x_nx_{n-1}+x_n^2-1=0 x n − 1 2 − 6 x n x n − 1 + x n 2 − 1 = 0 於是可知 x n + 1 x_{n+1} x n + 1 x n − 1 x_{n-1} x n − 1 x 2 − 6 x n x + x n 2 − 1 = 0 x^2-6x_nx+x_n^2-1=0 x 2 − 6 x n x + x n 2 − 1 = 0
x n + 1 + x n − 1 = 6 x n x_{n+1}+x_{n-1}=6x_n x n + 1 + x n − 1 = 6 x n 接下來按照二階線性遞推的方法計算即可.x n + 1 = a x n + ( a 2 − 1 ) x n 2 + b x_{n+1}=ax_n+\sqrt{(a^2-1)x_n^2+b} x n + 1 = a x n + ( a 2 − 1 ) x n 2 + b
這個例題比較有意思的一點是, 數列中每一項都是整數. 如果遞推式的係數 a a a b b b
