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

## 基礎知識

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

### 2階的齊次情形

${\displaystyle F_{0}=F_{1}=1,F_{n+2}=F_{n+1}+F_{n}\quad (n\geq 2,n\in \mathbb {N} )}$

${\displaystyle L_{0}=2,L_{2}=1,L_{n+2}=L_{n+1}+L_{n}\quad (n\geq 2,n\in \mathbb {N} )}$

${\displaystyle 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})}$

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})\quad (n\in \mathbb {N} ^{+})}$

### n階的齊次情形

${\displaystyle x^{k}+c_{1}x^{k-1}+c_{2}x^{k-2}+...+c_{k}=0}$

${\displaystyle 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}}$

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

### 非齊次情形

${\displaystyle a_{n}=b_{n}+c_{n}}$

## 計算機求解

### 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项的值 *)


#### 通過內置命令求特定項

Fibonacci[100];


LucasL[100];


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

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


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


#### 通過內置命令求通項

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

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


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];


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

RSolve[{a[n + 2] == a[n + 1] + 2 a[n] + 3, a[1] == 1, a[2] == 1}, a[n], n]

## 參考資料

1. 盧開澄; 盧華明. 第2章「遞推關係與母函數」第2.6小節「線性常係數齊次遞推關係」. (編) 張民 (責任編輯); 王冰飛 (責任編輯). 組合數學. 計算機科學組合學叢書. 白蕾 (責任校對) 4. 中國北京清華大學學研大廈A座: 清華大學出版社. 2006: 54–60. ISBN 7-302-13961-X （中文（中國大陸））.
2. （英文）Arash Farahmand（2016年）．Section 8.2 notes: Solving Linear Recurrence Relations（pdf）．University of California, Berkeley
3. 盧開澄; 盧華明. 第2章「遞推關係與母函數」第2.7小節「關於線性常係數非齊次遞推關係」. (編) 張民 (責任編輯); 王冰飛 (責任編輯). 組合數學. 計算機科學組合學叢書. 白蕾 (責任校對) 4. 中國北京清華大學學研大廈A座: 清華大學出版社. 2006: 61–67. ISBN 7-302-13961-X （中文（中國大陸））.
4. （英文）Weisstein, Eric W.．Rabbit Sequence.．MathWorld--A Wolfram Web Resource．
5. （英文）Ron Knott（2018年3月8日）．The Golden String of 0s and 1sUniversity of Surrey
6. （簡體中文）直接獲得差分方程解的表達式——Mathematica 10的新功能．Wolfram Alpha官方（2020年）．
7. （簡體中文）Fibonacci——Wolfram語言與系統 參考資料中心．Wolfram語言與系統 參考資料中心．
8. （簡體中文）LucasL——Wolfram語言與系統 參考資料中心．Wolfram語言與系統 參考資料中心．
9. （簡體中文）RecurrenceTable——Wolfram語言與系統 參考資料中心．Wolfram語言與系統 參考資料中心．
10. （簡體中文）RSolve——Wolfram語言參考資料．Wolfram語言與系統 參考資料中心．