# 高中数学/不等式与数列/常系数线性递推数列

## 基础知识

“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语言与系统 参考资料中心．