怎麼用特徵根法和不動點法求數列的通項公式?

12-29

例如數列中含有an an-1 an+1 或者an an-1.可以用高中生能懂得方法講一下嘛

其實是處理一類叫做線性齊次遞推方程的方法，這當中用到的思想其實是很深刻的，和線性代數有密切的關係，我其實覺得一個對線性代數沒有了解的高中生是沒有指望能夠徹底理解這個方法的，而且在學了線性代數之後，這當中的原理簡直是顯而易見的，尤其是學習了線性齊次微分方程之後，會發現這兩者幾乎是一樣的思路和方法。所以對於高中生來說，還是先粗略理解一下，如果有想不明白的地方，可以等以後學習了線性代數之後就會更明白了。

這兩種方法其實是解決這樣一類遞推問題：
$a_{n} + p_{k-1} a_{n-1} + p_{k-2} a_{n-2} + ... + p_1a_{n-k+1} + p_0a_{n-k} = f(n)$
其中， $a_n$ 是我們要求的數列，它的每一項 $a_{n}$ 由前k項遞推得到，我們叫它k階線性遞推方程。 $p_k$ 是一系列常數，與n無關。當右側的 $f(n) = 0$ 的時候，我們叫它k階齊次線性遞推方程；否則叫k階非齊次線性遞推方程。
在其中我們要求 $p_0 e 0$ ，否則它就是至多k-1階的了。
舉個例子，斐波那契序列
$a_{n+1} = a_{n} + a_{n-1}$
它可以改寫成
$a_n - a_{n-1} - a_{n-2} = 0$ ，也就是一個2階齊次線性遞推方程。
如果我們要求的是
$a_{n+1} = a_n + a_{n-1} - n$
那麼可以改寫成
$a_n - a_{n-1} - a_{n-2} = -n + 1$

------------------------------------------------------分割-------------------------------------------------------------

我們從比較容易的齊次的問題開始，也就是 $f(n) = 0$ 。
我們不著急求方程的解的形式，首先先看看為什麼叫做線性。對於這個方程，如果有兩個數列 ${b_n}, {c_n}$ 都符合這個遞推方程，那麼考慮數列 ${ alpha b_n + eta c_n}$ ，有：
$(alpha b_n + eta c_n) + p_{k-1}(alpha b_{n-1} + eta c_{n-1}) + ... + p_0(alpha b_{n-k} + eta c_{n-k})$
$= alpha(b_n + p_{k-1}b_{n-1} + ... + p_0b_{n-k}) + eta (c_n + p_{k-1}c_{n-1} + ... + p_0c_{n-k})$
$= 0$
將每一項分別乘以固定的係數，然後相加，在數學上叫做線性組合。它可以進一步推廣到三項或者以上 ${ alpha b_n + eta c_n + gamma d_n + ...}$ 。也就是說：
對於線性齊次遞推方程，如果有一組解滿足方程條件，則這組解的線性組合也滿足方程條件。

我們可以用若干個「有特徵的」解來作為代表，用它們的線性組合來表示其他的解。這組解在線性代數中叫做基底（base）。但不是所有的解都有用，比如說我們已經求出 ${b_n}$ 和 ${c_n}$ ，如果我們把 ${b_n + c_n}$ 合進來一起做線性組合，我們會發現得到的所有的解都是 ${ b_n }$ 和 ${c_n}$ 本身線性組合的結果，因為 ${b_n + c_n}$ 本身也是前兩項的線性組合，所以三項的線性組合仍然是前兩項的線性組合。這在線性代數上叫做線性相關與線性無關。簡單來說，如果有一個解已經可以表示成其他解的線性組合了，那麼這個解就沒有什麼用了，我們直接用其他解的線性組合就好。線性無關也就是說任意一個解都不能表述成其他解的線性組合，或者等效來說：

對於基底 ${b_n^{(1)}},{b_n^{(2)}},{b_n^{(3)}},...$ （它們表示各不相同的數列），如果線性組合
${alpha_1 b_n^{(1)} + alpha_2 b_n^{(2)} + alpha_3 b_n^{(3)} + ...} = 0$ （也就是說，線性組合的結果是全為0的數列）
只在
$alpha_1 = alpha_2 = ... = 0$
的時候成立，則我們說這些基底線性無關。顯然它表明基底中每一項都不能表示為其他項的線性組合。
全0的數列是個特殊的解，它跟任意其他解都是線性相關的（係數取0就行了）。因為它太平凡了所以也叫做平凡解。基底當中不會包含這個解。

那麼對於k階線性齊次遞推方程來說，我們知道，如果前k項都確定了，那麼第k+1項就可以通過前k項算出來，第k+2項也可以跟著算出來，由此，後面所有的項都確定了。那麼如果我們已知了k組線性無關的解，要求給定前k項初值的解，我們可以按前k項的值列出方程：
$left{egin{array}{c}alpha_1 b_1^{(1)} + alpha_2 b_1^{(2)} + ... + alpha_k b_1^{(k)} = a_1 \ alpha_1 b_2^{(1)} + alpha_2 b_2^{(2)} + ... + alpha_k b_2^{(k)} = a_2 \ ... \ alpha_1 b_k^{(1)} + alpha_2 b_k^{(2)} + ... + alpha_k b_k^{(k)} = a_kend{array} ight.$
k個線性無關的方程，k個未知數，剛好能解出唯一的解。這說明有k個線性無關的解作為基底，則任意其他解都可以表示成這k個解的線性組合。在線性代數中，這說明解空間的維度是k，不過不需要深入理解這個概念。

複習：
線性齊次遞推方程的解的線性組合仍然是線性齊次遞推方程的解；
線性相關與線性無關；
k階線性齊次遞推方程有k個線性無關的解

------------------------------------------------------分割-------------------------------------------------------------

但是我們還沒有說怎麼求解的問題。不過從前面的結果中，我們得到了一種思路：我們不需要想辦法對任意的初值求解；相反，我們無視初值，找到k個特殊的解，保證它們線性無關，然後利用初值的方程式解出每個基底對應的係數，從而求出相應的解。
我們求出一組特殊的等比數列的解來作為基底。為什麼想到選擇等比數列可以扯到母函數、z-變換等一系列問題上，我們不發散思路，總之當基底是等比數列 $b_n = x^{n}, x e 0$ （我們不需要設出前面的係數，因為只要底數相同，不同係數之間只差一個比例，這是線性相關的思想）的時候：
$x^{n} + p_{k-1} x^{n-1} + ... + p_0 x^{n-k} = 0$
$x^k + p_{k-1}x^{k-1} + ... + p_0 = 0$
這是一個一元k次的方程，帶上複數根在內，剛好有k個根，由於 $p_0 e 0$ ，顯然 $x = 0$ 不是這些根之一。如果這些根互不相同，那麼這k個等比數列剛好就是k個解。用線性代數的方法可以證明它們是線性無關的，這跟范德蒙矩陣的性質有關，不展開講，總之知道這件事就行了。

那麼如果有重根呢？
根據微積分的原理，如果多項式 $g(x) = 0$ 在某個 $x_1$ 上有重根，則它在這一點上的一階導數也為0，證明這一點可以考慮 $g(x) = a_0(x - x_0)(x - x_1)...(x - x_k)$ 的代數基本定理展開的形式，它的導數可以用乘積導數公式展開，有重根的時候，重根展開的兩項都為0。同樣，如果有三個重根，則不僅一階導數為0，二階導數也為0。也就是說：
$(x^{n} + p_{k-1} x^{n-1} + ... + p_0 x^{n-k})$
如果有多重根則二階導數、三階導數也為0。對比左邊直接求導的係數：
$(x^{n} + p_{k-1} x^{n-1} + ... + p_0 x^{n-k})$
我們就可以得到： $b_n = n x^n$ 也是原遞推方程的解。如果有三個重根，則 $b_n = n^2 x^n$ 也是，有m重根的時候，
$b_n = x^n, b_n = n x^n, b_n = n^2x^n, ..., b_n = n^{m-1}x^n$ 都是原遞推方程的根
高階導數本來是n(n-1)(n-2)...的形式，考慮到線性性，用任意一個線性無關的都可以， $n^m$ 形式的比較簡單。如果你喜歡把係數寫成 $A_n^m$ ， $C_n^m$ 也可以，只要是線性無關的就行。

以上內容對於高中生可能難了一點，總之記住：
假設原數列是等比數列，得到一個k階方程，解出這個方程的所有根，每個根對應一個解；如果有重根，則依次用 $n x^n, n^2 x^n, ...$ 來替換它。得到的k組解是整個齊次遞推方程的基底，它們是線性無關的。它們的組合可以表示任意一個特徵方程的解。

假設原數列為等比數列後形成的一元k次方程
$x^k + p_{k-1}x^{k-1} + ... + p_0 = 0$
就叫做這個齊次線性遞推方程的特徵方程，這個方程的k個根就叫做這個方程的特徵根。這些方程構成的解就叫做特徵解。
求出特徵解之後，按要求的初值列方程，就可以將最終要求的解表示為特徵解的線性組合，從而求出最終要求的解。

------------------------------------------------------分割-------------------------------------------------------------

說完齊次的情況，再來說非齊次的情況。非齊次的情況其實沒有想像的那麼複雜，我們去掉最右邊的 $f(n)$ 得到一個齊次方程，用前面的方法，我們已經可以求出這個齊次方程的解。現在如果我們有任意一個非齊次方程的解 ${c_n}$ ，和任意一個相應齊次方程的解 ${ b_n }$ ，則顯然 ${ c_n + b_n }$ 也是相應非齊次方程的解。跟齊次的情況相同，也是前k項完全決定了後面項的值，因此非齊次方程的解可以表示為：
任意一個非齊次方程的解 + 齊次方程的解的基底的線性組合

一般我們會用各種方法湊出一個非齊次方程的解，這個解就叫做特解；而相應齊次方程的解叫做通解。我們最後要求的解就可以寫成通解 + 特解的形式，再通過解初值方程，得到通解中各個基底的係數，就可以解出非齊次的線性遞推方程。

湊出非齊次方程的解的情況就需要不動點法出場了。對於一階的情況，如果 $f(n)$ 是個與n無關的常數，我們可以假設原數列是常數數列，也就是 $a_n = a_{n-1} = ... = C$ ，然後代入遞推關係解出C的值，這在將遞推方程寫成 $a_{n+1} = h(a_{n})$ 的時候，相當於求 $h(x) = x$ 的不動點。可見不動點法其實是求特解的一種方法。
如果 $f(n)$ 是別的值呢？我們一般根據 $f(n)$ 的形式來湊這個特解，如果 $f(n)$ 是n的m階多項式，則 $a_n$ 的特解也是n的m階多項式；如果 $f(n)$ 是 $C_1q^n$ 的形式，特解也是 $C_2 q^n$ 的形式；如果 $f(n)$ 是幾種可以湊出特解的形式的和，可以將其中每一種形式湊出特解再求和，來得到一個完整的特解。
湊出特解之後再求出齊次線性遞推方程的通解，然後解初值方程就可以求出完整的通項。

------------------------------------------------------分割-------------------------------------------------------------

沒看懂不要緊，我們來舉幾個例子。首先來個比較簡單的， $a_n = a_{n-1} + a_{n-2} - n$ ，其中 $a_1 = 5, a_2 = 8$
改寫成
$a_n - a_{n-1} - a_{n-2} = - n$
湊一個特解，特解的形式應該是 $a_n = C_1 n + C_2$ ，代回原方程：
$C_1 n + C_2 - C_1 (n-1) - C_2 - C_1(n-2) - C_2 = -n$
$-C_1 n + (3C_1 - C_2) = -n$
因此
$C_1 = 1, C_2 = 3$
驗證一下， $a_n = n + 3$ 的確是原遞推方程的解。
再來求出通解，去掉非齊次項代入一個等比數列，特徵方程是
$x^2 - x - 1 = 0$
特徵根為
$x_1 = frac{1 + sqrt{5}}{2}, x_2 = frac{1 - sqrt{5}}{2}$
所以解的形式可以表示特徵解的線性和再加上特解：
$a_n = C_3 left(frac{1 + sqrt{5}}{2} ight)^n + C_4 left(frac{1 - sqrt{5}}{2} ight)^n + n + 3$
代入最早的遞推關係中，得到
$left{egin{array}{l}C_3 left(frac{1 + sqrt{5}}{2} ight) + C_4 left(frac{1 - sqrt{5}}{2} ight) = 1 \ C_3 left(frac{1 + sqrt{5}}{2} ight)^2 + C_4 left(frac{1 - sqrt{5}}{2} ight)^2 = 3end{array} ight.$
得到 $C_3 = C_4 = 1$ ，因此
$a_n = left(frac{1 + sqrt{5}}{2} ight)^n + left(frac{1 - sqrt{5}}{2} ight)^n + n + 3$

再來個稍微難一點的， $a_n = 4(a_{n-1} - a_{n-2}) + 1$ ，其中 $a_1 = 1, a_2 = 5$
改寫成
$a_n - 4a_{n-1} + 4_{n-2} = 1$
求特解，設 $a_n = C_1$ ，或者利用不動點法，解出特解為 $a_n = 1$
特徵方程是
$x^2 - 4x + 4 = 0$
它有重根 $x=2$ ，因此特徵解為 $2^n, n2^n$
所以最後可以表示為
$a_n = C_2 2^n + C_3 n2^n + 1$
代入初值得到
$left{egin{array}{l}2C_2 + 2C_3 + 1 = 1 \ 4C_2 + 8C_3 + 1 = 5end{array} ight.$
所以
$C_2 = -1, C_3 = 1$
$a_n = (n-1)2^n + 1$

有的時候，遞推方程一眼看上去根本不是線性的，但可以經過變換變成線性遞推方程，比較經典的是分式的形式，比如
$a_{n+1} = frac{a_n - 1}{2a_n - 3}$
我們希望把它湊成
$frac{1}{a_{n+1} - p} = frac{k_1}{a_n - p} + k_2$ 的形式，從而變成一個線性遞推的方程。整理得到
$a_{n+1} = frac{a_n - p}{k_2 a_n - pk_2 + k_1} + p = frac{(1+pk_2)a_n - p - p^2k_2 + k_1p}{k_2 a_n - pk_2 + k_1}$
比較係數得到
$frac{1+pk_2}{k_2} = frac{1}{2}$
$frac{-pk_2 + k_1}{k_2} = -frac{3}{2}$
$frac{-p-p^2k_2 + k_1p}{k_2} = -frac{1}{2}$
解出的過程不再細寫

謝邀

我這裡來說一類僅用高中數列知識就能理解的線性遞推關係 $a_n=pa_{n-1}+qa_{n-2},(n ge 3)$ 通項的求解方法，更一般的、深入的討論可參見 @靈劍的回答。

對於線性遞推關係 $a_n=pa_{n-1}+qa_{n-2},(n ge 3),$ 其中 $a_1,a_2$ 已知，想法是構造等比數列，從而求得通項。

引入待定參數 $x_1,x_2$ ,可將上式寫成 $a_n-x_1 a_{n-1} =x_2(a_{n-1}-x_1 a_{n-2})$ .
可見 ${a_n-x_1 a_{n-1} }$ 是以 $a_2-x_1a_1$ 為首項， $x_2$ 為公比的等比數列，因此
$a_n-x_1 a_{n-1}=x_2^{n-2} (a_2-x_1a_1).quad (1)$
同樣的， $a_n-x_1 a_{n-1} =x_2(a_{n-1}-x_1 a_{n-2})$ 也可以寫成 $a_n-x_2 a_{n-1} =x_1(a_{n-1}-x_2 a_{n-2})$ .
類似可得 $a_n-x_2 a_{n-1}=x_1^{n-2} (a_2-x_2a_1).quad (2)$

當 $x_1 eq x_2$ 時，聯立式 (1)(2)，消去 $a_{n-1}$ 可得
$(x_2-x_1)a_n =x_2^{n-1} (a_2-x_1 a_1)-x_1^{n-1} (a_2-x_2 a_1).$
故
$a_n =frac{x_2^{n-1} (a_2-x_1 a_1)-x_1^{n-1} (a_2-x_2 a_1)}{x_2-x_1}.$

那麼現在的問題就是 $x_1,x_2$ 是什麼，由於 $a_n-x_1 a_{n-1} =x_2(a_{n-1}-x_1 a_{n-2})$ 即是 $a_n=(x_1+x_2) a_{n-1} -x_1x_2 a_{n-2},$ 對比 $a_n=pa_{n-1}+qa_{n-2}$ 可知
$x_1+x_2=p,x_1x_2=-q.$
因此由韋達定理可知， $x_1,x_2$ 是方程 $x^2-px-q=0$ 的兩個根，至此 $x_1,x_2$ 就可以通過解方程求出。

我們把 $x^2-px-q=0$ 稱為線性遞推關係 $a_n=pa_{n-1}+qa_{n-2}$ 的特徵方程，它是將 $a_n=pa_{n-1}+qa_{n-2}$ 中的 $a_n,a_{n-1},a_{n-2}$ 分別用 $x^2,x,1$ 替換得到的。

然而，現在這個問題還沒有得到徹底解決，上述給出的 $a_n$ 通項的表達式是在特徵方程有兩個不相等的根時得到的，那麼如果特徵方程有兩個相等的根時， $a_n$ 的通項應該如何求解呢？

當特徵方程 $x^2-px-q=0$ 有兩個相等的根時，也即是 $x_1=x_2,$ 這時 $a_n-x_1 a_{n-1} =x_2(a_{n-1}-x_1 a_{n-2})$ 就變成了 $a_n-x_1 a_{n-1} =x_1(a_{n-1}-x_1 a_{n-2})$ ,現在通過構造等差數列來求解這一遞推式。

將 $a_n-x_1 a_{n-1} =x_1(a_{n-1}-x_1 a_{n-2})$ 兩邊同時除以 $x_1^n$ 可得
$frac{a_n}{x_1^n}-frac{a_{n-1}} {x_1^{n-1}} = frac{a_{n-1}} {x_1^{n-1}} -frac{a_{n-2}} {x_1^{n-2}}.$
這說明 $left{ frac{a_n}{x_1^n} ight}$ 是以 $frac{a_1}{x_1}$ 為首項， $frac{a_2}{x_1^2}-frac{a_1}{x_1}$ 為公差的等差數列，因此
$frac{a_n}{x_1^n} =frac{a_1}{x_1} +(n-1)left( frac{a_2}{x_1^2}-frac{a_1}{x_1} ight),$
即
$a_n=a_1 x_1^{n-1} +(n-1)left( a_2 x_1^{n-2} -a_1 x_1^{n-1} ight).$

至此，線性遞推關係 $a_n=pa_{n-1}+qa_{n-2},(n ge 3)$ 通項的問題就得到了徹底的解決。

下面以經典的 Fibonacci 數列 $(a_n=a_{n-1}+a_{n-2},nge 3,a_1=1,a_2=1.)$ 為例求解一下。

特徵方程為 $x^2-x-1=0,$ 易求得兩個不相等的根
$x_1=frac{1-sqrt{5}}{2},x_2=frac{1+sqrt{5}}{2}.$

利用公式 $a_n =frac{x_2^{n-1} (a_2-x_1 a_1)-x_1^{n-1} (a_2-x_2 a_1)}{x_2-x_1},$
易知 $a_2-x_1a_1=frac{1+sqrt{5}}{2},a_2-x_2a_1=frac{1-sqrt{5}}{2}, x_2-x_1=sqrt{5}.$
代入上式即得
$a_n=frac{sqrt{5}}{5} left[ left( frac{1+sqrt{5}}{2} ight) ^n - left( frac{1-sqrt{5}}{2} ight) ^n ight].$

需要說明的是，上述兩種 $a_n$ 通項的表達式沒必要死記，知道利用特徵方程推導的過程也能很快求出結果，即便特徵方程也忘記了，只要知道構造等比數列的思想同樣可以得出結果。

嗯，就醬(^o^)/~

你說的是這個嗎

這個平時做題可能用得上，高考用不上吧，這個跟差分方程有關係吧，我也不清楚，反正平時做題碰到用這個很快，但也碰不到幾道題。我們老師當時講這種類型的題是列方程求出能使{an+xan-1}成等比數列然後解an的吧

求an的通項公式。

這是一個方法，做為以上其他答案的補充。