高中數學/不等式與數列/常係數線性遞推數列

閱讀指南

在差分方程與微分方程理論中，若干考察量之間呈現線性比例關係是最簡單的情形，也是嚴格說來唯一存在普遍解法的情形。而對於更普遍的非線性關係式，往往也只能想辦法先轉換為人們更熟悉的線性關係後，才能變得易於求解。因此，分析清楚線性情形的求解變得格外重要。

本節主要講解一種二階的線性遞推式求解思路，並簡要介紹了更高階情形的一般結論。由於計算可能比較麻煩，我們更推薦在領會求解思路的基礎上，利用電腦程式或軟體解決它們。在後面的多元遞推數列章節中，我們還會將其拓展到多階多變量的情形。雖然多元遞推數列從數學角度來說一般是難以求出形式簡便的通解，但是原則上可以通過電腦程式自動遞推求解出任意特定項，在實際問題的數學建模（也就是應用題啦）中也更常見。

預備知識

本節大部分內容都要求讀者至少了解遞推數列的基本概念和一階遞推數列的常見解法，所以讀者應該先閱讀數列基礎概念和一階遞推數列章節，然後再根據需要選讀本節的內容。

考試要求

本節介紹的數列及其求解方法一般不被列入中學常規考試的考察範圍。但是其方法並不難學，可以適當了解。

後續課程聯繫

本節對線性關係式的求解只是整個線性系統研究的冰山一角，這種基於特徵方程的解法一般可以在有關「組合數學」或「差分方程」的大學課程中學習到。在其它後續的大學課程中，我們還將把研究線性系統的經驗進一步加深，然後應用到經典力學、經典電路學、微分方程、積分變換、信號處理和量子力學等學科中。

本節提及的Fibonacci數列是特別常見的例子，與黃金分割比例也存在密切聯繫，進而在優選法中的分數法和外匯技術分析中的斐波那契回調都能見到它的應用。

基礎知識

定義：k階常係數線性遞推關係（linear recurrence relation of degree k with constant coefficients）$\{a_{n}\}$的一般形式為： $a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k-1}a_{n-k}=b(n)$
其中各個$c_{i}$都是已知常數，而$b(n)$是關於n的已知表達式（可以記作數列$b_{n}$）。

特別地，當$b(n)=0$時，以上關係式又叫做（k階的）常係數齊次線性遞推關係（linear homogeneous recurrence relation of degree k with constant coefficients），否則叫做非齊次的常係數線性遞推關係，$b(n)$叫做非齊次項。

「k階」（degree k）是指關係式中出現的不同的$a_{i}$一共有k個；「常係數」（constant coefficients）是指式子中各個$c_{i}$都是與n的取值無關的常數；「線性」（linear）是指式子中各個$a_{i}$都是以一次冪單項式的形式出現的；「齊次」（homogeneou）是指式子中的每個單項式都是次數相同的，在這裡可以說是不含常數項的。

用線性遞推關係式描述的數列也叫做線性遞推數列。對於n階的常係數齊次線性遞推數列，一般給定n個初始值（或者叫邊界條件），即可確定所求的解。

線性遞推關係看似形式單一，但不意味著它過於簡單以至於缺乏實際應用。事實上，「在實際問題中常見」和「可以系統求解」這兩點都是人們關注它的主要原因。本節主要關注它的求解方法，在後面的應用問題的遞推關係建模章節中還會看到它的更多實例。

提示：齊次線性遞推關係是有通用方法求解的；而非齊次的情形僅當非齊次項的母函數形式易知時才容易求解。

注意：在線性代數學的術語中，非齊次的關係式並不被認為是一種線性映射。就像是「線性方程組」一詞中的「線性」與「線性映射」中的「線性」含義並不一樣。但是齊次情形下的解與非齊次情形下的解存在密切聯繫，只要我們找到了齊次情形下的解，那麼這個解也能為相關的非齊次情形下的解提供重要線索。當然在高中數學中，可以暫時不去糾結於這些概念細節。

2階的齊次情形

李奧納多·費波那契（Leonardo Fibonacci，1175年－1250年）在《計算之書》（Liber Abaci）中提到並求解了一個在理想假設條件下兔子成長率的經典問題。

數學家愛德華·盧卡斯（François Édouard Anatole Lucas，1842年－1891年）也是漢諾塔遊戲（巧妙地在3個柱子之間移動一串圓盤）的發明人。

此為數列研究雙煞，也就是參加數列章節考試前必須膜拜的2個人（除非您不怕在百分制的數學考試中獲得Fibonacci數列中前幾個數那樣的得分）。

最常見的2階齊次線性遞推式是由李奧納多·斐波那契給出的斐波那契數列（Fibonacci sequence）或者叫費氏數列$\{F_{n}\}$問題：
$F_{0}=F_{1}=1,F_{n+2}=F_{n+1}+F_{n}\quad (n\geq 2,n\in \mathbb {N} )$

提示：數列的編號具體是從0開始取還是從1開始取，並不影響這個問題的數學本質。

提示：有的人也將斐波那契數列叫做兔子序列。但是兔子序列更多的是用作斐波那契詞（Fibonacci word）的別名。它斐波那契詞只是模仿斐波那契數列構造的字符序列，但與之並不相同。為避免混淆，我們不推薦將斐波那契數列簡稱為兔子數列。

另一個常見的2階齊次線性遞推式是由愛德華·盧卡斯給出的盧卡斯數（Lucas number）$\{L_{n}\}$的遞推問題：
$L_{0}=2,L_{2}=1,L_{n+2}=L_{n+1}+L_{n}\quad (n\geq 2,n\in \mathbb {N} )$

這類2階遞推關係的一般形式$a_{n+2}=c_{1}a_{n+1}+c_{2}a_{n}\quad (n\geq 3,n\in \mathbb {N} ,c_{1}\in \mathbb {R} ,c_{2}\in \mathbb {R} )$也叫做盧卡斯數列（Lucas sequence）。

提示：盧卡斯數構成的數列和盧卡斯數列的概念並不一樣。盧卡斯數列包括了由盧卡斯數組成的數列和Fibonacci數列。

盧卡斯數列的遞推式可以通過待定係數法構造為以下形式的等比關係（其中$c_{1}$和$c_{2}$為非零的已知常數，p和q為待定係數）：
$L_{n+2}=c_{1}L_{n+1}+c_{2}L_{n}\quad \Leftrightarrow \quad L_{n+2}+qL_{n+1}=p(L_{n+1}+qL_{n})$
通過對比變形前後的各個對應項的係數即可求出p和q的值。然後把$L_{n+2}+qL_{n+1}$看成一個整體，易知數列$\{L_{n+2}+qL_{n+1}\}$滿足等比數列的定義，因而容易求出通項公式。知道$L_{n+2}+qL_{n+1}$的解析式後，再對其進行一次構造，即可得到$L_{n}$的解析式。

由上述分析可知，整個過程進行了2次遞推關係式的構造，每構造一次就會降低一次遞推式的階數。有時候滿足要求的待定係數會是比較複雜的分數，導致運算過程冗長且易錯。因此這種使用待定係數的構造方法可行，但是不太適合手工求解，我們推薦使用本節後面介紹的計算機編程的辦法求解。

為簡明起見，我們先直接給出Fibonacci數列的通項公式如下：
$F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})\quad (n\in \mathbb {N} ^{+})$
由於直接進行構造式的證明比較繁瑣，我們改為在數學歸納法章節中用新方法再對這個通項公式的正確性給予證明。

盧卡斯數列吸引數學家們注意的一個主要的特點就是它的通項公式中隱藏了數秘學中的黃金分割比例。事實上，我們在後面將會學到，Fibonacci數列的相鄰項比值${\frac {F_{n}}{F_{n+1}}}$的數列極限也是黃金分割比例。這也是後面在優選法中要介紹的分數法的由來基礎。

n階的齊次情形

先給出結論：

對於形式為$a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}=0$的齊次遞推式，可以定義特徵方程：
$x^{k}+c_{1}x^{k-1}+c_{2}x^{k-2}+...+c_{k}=0$
由代數學基本定理可知，k次代數方程一定存在k個解。假設此特徵方程有k個不同的解$x_{1},x_{2},x_{3},...,x_{k}$，則原遞推式的通解（即一般解）為：
$a_{n}=d_{1}x_{1}^{n}+d_{2}x_{2}^{n}+d_{3}x_{3}^{n}+...+d_{k-1}x_{k-1}^{n}+d_{k}x_{k}^{n}$
其中的各個$d_{i}$是由給定的具體初始條件而確定的待定係數。

事實上由於高次代數方程一般難於通過筆算求解，所以筆算3階及更高階的線性遞推式通解一般並不現實。

我們在此簡要說明一下上面給出的通項公式是滿足齊次遞推關係式的。
設滿足遞推式的通解具有形式$a_{n}=d_{1}x_{1}^{n}+d_{2}x_{2}^{n}+...+d_{k}x_{k}^{n}$，其中各$x_{i}$是原遞推式特徵方程的各個不同根。
既然要說明$a_{n}$滿足遞推關係式，就可以嘗試用倒退法，將$a_{n}$代入遞推關係式，看看使等式成立的條件是否足夠：
${\begin{array}{l}a_{n}+c_{1}a_{n-1}+...+c_{k}a_{n-k}=0\\\Leftrightarrow (d_{1}x_{1}^{n}+d_{2}x_{2}^{n}+...+d_{k}x_{k}^{n})+c_{1}(d_{1}x_{1}^{n-1}+d_{2}x_{2}^{n-1}+...+d_{k}x_{k}^{n-1})+...+c_{k}(d_{1}x_{1}^{n-k}+d_{2}x_{2}^{n-k}+...+d_{k}x_{k}^{n-k})=0\end{array}}$
交換求和順序可得：
${\begin{array}{l}\Leftrightarrow (d_{1}x_{1}^{n}+c_{1}d_{1}x_{1}^{n-1}+...+c_{k}d_{1}x_{1}^{n-k})+(d_{2}x_{2}^{n}+c_{1}d_{2}x_{2}^{n-1}+...+c_{k}d_{2}x_{2}^{n-k})+...+(d_{k}x_{k}^{n}+c_{1}d_{k}x_{k}^{n-1}+...+c_{k}d_{k}x_{k}^{n-k})=0\\\Leftrightarrow d_{1}x_{1}^{n-k}(x_{1}^{k}+c_{1}x_{1}^{k-1}+...+c_{k})+d_{2}x_{2}^{n-k}(x_{2}^{k}+c_{1}x_{2}^{k-1}+...+c_{k})+...+d_{k}x_{k}^{n-k}(x_{k}^{k}+c_{1}x_{k}^{k-1}+...+c_{k})=0\\\end{array}}$
由於各個特徵方程的根一定滿足特徵方程，進而得到：
${\begin{array}{l}d_{1}x_{1}^{n-k}\times 0+d_{2}x_{2}^{n-k}\times 0+...+d_{k}x_{k}^{n-k}\times 0=0\\\Leftrightarrow 0=0\end{array}}$
這說明$a_{n}$的確滿足原來的齊次遞推關係式。

提示：如果規定$c_{0}=1$，那麼上述過程可以用連加號及其運算規律簡化如下：
${\begin{array}{l}\sum _{i=0}^{k}\limits (c_{i}a_{n-i})=\sum _{i=0}^{k}\limits (c_{i}(\sum _{j=1}^{k}\limits d_{j}x_{j}^{n-i}))=\sum _{j=1}^{k}\limits (d_{j}\sum _{i=0}^{k}\limits (c_{i}x_{j}^{n-i}))=\sum _{j=1}^{k}\limits (d_{j}\times 0)=\sum _{j=1}^{k}\limits 0=0\end{array}}$

另一方面，要說明上述形式的通解涵蓋了一切初始值下的齊次遞推關係式的特解（即不會有漏掉的解），需要將k個初始條件分別代入假設成立的通項公式中，構成包含k個未知待定係數的k元線性方程組。判斷此方程組在「特徵根彼此不同」的條件下是否始終有解即可。由於其嚴格證明需要用到線性代數中的克萊姆法則和范德蒙矩陣公式，我們不再展開講解。粗略地說，由k個獨立的已知條件確定出k個未知係數基本上是足夠的。

非齊次情形

對於一個常係數非齊次線性遞推式，假設已求出其齊次形式的一個通解$b_{n}$（即先忽略掉常數項求解），如果能再求得原遞推式的一個特解$c_{n}$，則由線性系統的疊加原理可知，原非齊次遞推式的通解$a_{n}$一定滿足如下形式：
$a_{n}=b_{n}+c_{n}$
讀者可以仿照前面對於齊次情形的分析思路，檢驗此形式的通解滿足非齊次線性遞推式。

不過更大的難點在於非齊次項的形式可能很複雜，導致遞推式的特解不一定總是很好地求出來。實際上，只有少數母函數易知的情形容易得到特解。

計算機求解

在舊版Mathematica軟體中，可以通過RSolve命令求解常係數線性齊次遞推式的通項公式。在Mathematica 10中，還可以通過RSolveValue命令求解常係數線性遞推式的通項公式。

如果使用從邊界條件正向遞推的方法或從目標值倒推回溯的方法（在計算機算法理論中常簡稱為「遞歸法」），也可以用更一般的程式語言求解出數列中特定項的數值解。

提示：Fibonacci數列的計算也是計算機編程教程的常見案例。計算機從業者對它的興趣可能並非來源於畢達哥拉斯學派信仰的數學神秘主義，而只是想說明某一種計算機程式語言可以如何實現遞歸算法（從而不會比同樣可以實現遞歸算法的其它程式語言差勁）。

Mathematica

通過定義函數求特定項

最原始的方法是通過自定義遞推關係式。例如：

fib[n_] := fib[n] = fib[n - 1] + fib[n - 2]; (* 以递推的形式设置新的自定义函数fib(n) *)
fib::usage = "这个函数是通过Fibonacci数列的递推关系式定义的"; (* 对自定义函数的用法说明 *)
fib[1] = fib[2] = 1; (* 给定2个初始项的值 *)
fib[200]; (* 计算第200项的值 *)

提示：在Mathematica的Wolfram語言中，「=」表示賦值，「==」表示相等，「:=」表示符號的定義。

只要問題可解，按這種逐個遞推的笨方法總能夠推算出任意的特定項，即使所給的遞推式沒有明顯的通項公式求法。

通過內置命令求特定項

使用內置命令求解第100個Fibonacci數：

Fibonacci[100];

使用內置命令求解第100個盧卡斯數：

LucasL[100];

Mathematica在2008年推出的7.0版本中引入了可以按遞推關係式求出一連串項的「RecurrenceTable」命令，其語法格式為：

RecurrenceTable[eqns, expr, {n, nmax}]; (* 以求解递归方程 eqns 为基础，产生一组关于连续 n 的 expr 的值的列表 *)
RecurrenceTable[eqns, expr, nspec]; (* 在 nspec 指定的 n 值范围上，产生一组 expr 的值 *)
RecurrenceTable[eqns, expr, {n1, …}, {n2, …}, …]; (* 为连续的 n1，n2，… 产生 expr 的数组值 *)

根據遞推關係式求解前幾個Fibonacci數的示例：

RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a, {n, 10}];

提示：注意區分Wolfram語言中的賦值號「=」和相等號「==」。

提示：如果RSolve命令沒有輸入錯誤，但是執行後出現「RSolve::deqn: Equation or list of equations expected instead of True in the first argument True.」一類的報錯信息，一般是由於沒有清除同名標識符中的已有信息。如果是這種情況：(1)可以先在其它地方輸入獨立命令「ClearAll[a]」清除標識符a中的內容，然後重新執行RSolve命令；(2)也可以改用除a以外的其它未使用過的標識符來命名要求解的數列。

通過內置命令求通項

Mathematica在2003年推出的5.0版本中引入了可以求遞推關係式一般項表達式的「RSolve」命令，其語法格式為：

RSolve[eqn, a[n], n]; (* 求解递推方程 a[n] *)
RSolve[{eqn1, eqn2, …}, {a1[n], a2[n], …}, n]; (* 求解一个递推方程组 *)
RSolve[eqn, a[n1, n2, …], {n1, n2, …}]; (* 求解一个部分递推方程 *)

求解差分方程$a_{n+1}-2a_{n}=1$的示例：

RSolve[a[n+1] - 2 a[n] == 1, a[n], n];

包括邊界條件的求解示例：

RSolve[{a[n+1] - 2 a[n] == 1, a[0] == 1}, a[n], n];

相關例題1： 已知數列$\{a_{n}\}$滿足$a_{1}=1,a_{2}=3,a_{n+2}-2a_{n+1}-a_{n}=0$，使用Mathematica求它的通項公式。

解答：
在Mathematica軟體中輸入命令（因為只有一行命令，分號此時可以不寫）：
RSolve[{a[n + 2] - 2 a[n + 1] - a[n] == 0, a[1] == 1, a[2] == 3}, a[n], n];
然後按組合鍵Shift + Enter即可得到結果為：$a_{n}={\frac {1}{2}}((1-{\sqrt {2}})^{n}+(1+{\sqrt {2}})^{n})$。

答案：$a_{n}={\frac {1}{2}}((1-{\sqrt {2}})^{n}+(1+{\sqrt {2}})^{n})$。

相關例題2： 已知數列$\{a_{n}\}$滿足$a_{1}=1,a_{2}=1,a_{n+2}=a_{n+1}-2a_{n}+3$，使用Mathematica求它的通項公式。

解答：
在Mathematica軟體中輸入命令：
RSolve[{a[n + 2] == a[n + 1] + 2 a[n] + 3, a[1] == 1, a[2] == 1}, a[n], n]
然後按組合鍵Shift + Enter即可得到結果為：$a_{n}={\frac {5\times 2^{n}-5\times (-1)^{n}-9}{6}}$。

答案：$a_{n}={\frac {5\times 2^{n}-5\times (-1)^{n}-9}{6}}$。

補充習題