递推关系式

递推关系（英语：Recurrence relation），是一种递推地定义一个序列的方程式：序列的每一项目是定义为前若干项的函数。

像斐波那契数即为递推关系

$x_{n+2}=x_{n+1}+x_{n}$

某些简单定义的递推关系式可能会表现出非常复杂的（混沌的）性质，他们属于数学中的非线性分析领域。

所谓解一个递推关系式，也就是求其解析解，即关于$n$的非递归函数。

递推关系式的例子

等差数列

$x_{0}=1,x_{n+1}=x_{n}+2$为等差数列$1,3,5,7,.....$

一般地，$x_{0}=a,\ x_{n+1}=x_{n}+d$为等差数列，其中$a$为首项，$d$为公差。

等比数列

$x_{0}=1,x_{n+1}=2x_{n}$为等比数列$1,2,4,8,.....$

一般地，$a\neq 0$且$r\neq 0$，$x_{0}=a,\ x_{n+1}=rx_{n}$为等比数列，其中$a$为首项，$r$为公比。

阶乘

$0!=1$

$n!=n\times (n-1)!$

因此最小的几个阶乘为$1,1,2,6,24,120,720,5040,.....$、

倒数和

设$x_{k}=x^{k}+x^{-k}$,$x_{1}=x_{1}$，则：

$x_{2}=(x_{1})^{2}-2$

$x_{3}=x_{1}\cdot x_{2}-x_{1}$

$x_{4}=(x_{2})^{2}-2$

$x_{5}=x_{2}\cdot x_{3}-x_{1}$

$x_{6}=(x_{3})^{2}-2$

$x_{7}=x_{3}\cdot x_{4}-x_{1}$

$\cdots \cdots$

$x_{2k}=(x_{k})^{2}-2$

$x_{2k+1}=x_{k}\cdot x_{k+1}-x_{1}$

常系数线性齐次递推关系式

线性（英语：Linear）的意思是序列的每一项目是被定义为前一项的一种线性函数。系数和常数可能视$n$而定，甚至是非线性地。

一种特别的情况是当系数并不依照$n$而定。

齐次（英语：Homogenous）的意思为关系的常数项为零。

为了要得到线性递归唯一的解，必须有一些起始条件，就是序列的第一个数字无法依照该序列的其他数字而定时，且必须设定为某些数值。

解线性递推关系式

线性递推关系式的解通常是由系统的方法中找出来，通常借由使用生成函数（形式幂级数）或借由观察$r^{n}$是一种对$r$的特定数值之解的事实。且因关系式为线性方程，另一种方法是以矩阵表示此一递推关系式，并透过矩阵对角化等技巧求出关系式的通项。

二阶递推关系式的形式：

$a_{n}=Aa_{n-1}+Ba_{n-2}\,$

其解为$r^{n}$：

$r^{n}=Ar^{n-1}+Br^{n-2}\,$

两边除以$r^{n-2}$可以得到：

$r^{2}=Ar+B\,$

$r^{2}-Ar-B=0\,$

这就是递推关系式的特征方程。解出$r$可获得两个根（英语：Roots）$\lambda _{1},\lambda _{2}$，且如果两个根是不同的，可得到解为

$a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}\,$

而如果两个根是相同的（当$A^{2}+4B=0$），得到

$a_{n}=C\lambda ^{n}+Dn\lambda ^{n}\,$

$C$和$D$都是常数。以上结果皆可由直接代入得证，或以矩阵对角化的技巧推导出。

换句话说，将这种$a_{n}=Aa_{n-1}+Ba_{n-2}$形式的方程式，用$2$代入$n$后，就得到上述的$r^{2}=Ar+B$。常数$C$和$D$可以从"边界条件（side conditions）"中得到，通常会像是“已知$a_{0}=c_{1}$, $a_{1}=c_{2}$”。

范例：斐波那契数

斐波那契数是使用一种线性递推关系式来定义：

$F_{0}=0\,$

$F_{1}=1\,$

$F_{n}=F_{n-1}+F_{n-2}\,$

设若：$F_{n}/F_{n-1}\,$当n趋于无限大之极限值存在，则其值为$1+{\sqrt {5}} \over 2\,$ $=\Phi$恰为黄金分割值$1.618....$，另一值则为$0.618....$，两值互为倒数，也就是说${\frac {1}{1.618....}}=0.618....$，反之亦然。

$F_{n}={\Phi ^{n} \over {\sqrt {5}}}-{(1-\Phi )^{n} \over {\sqrt {5}}}$

起始条件为：

$F_{0}=0\,$

$F_{1}=1\,$

因此，斐波那契数的序列为：

$0,1,1,2,3,5,8,13,21,34,55,89...$

常系数非齐次线性递推关系

对于常系数非齐次线性递推关系，我们可以用待定系数法来求出它的一个特解，而它的通解就是这个特解与对应的齐次递推关系的通解的和。也可以使用迭代法求解，但只能得到确切的数值解，不能直接以解析式作答，该方法可利用计算机求解。

时域经典法求解

一般情况下，常系数线性差分方程可以写作：

$\sum _{k=0}^{N}a_{k}y(n-k)=\sum _{r=0}^{M}b_{r}x(n-r)$

则对应的齐次方程形式为：

$\sum _{k=0}^{N}a_{k}y(n-k)=0$

则特征方程为：

$\sum _{k=0}^{N}a_{k}\alpha ^{N-k}=0$

当特征根非重根时，齐次解为：

$y_{h}(n)=\sum _{i=1}^{N}C_{i}\alpha _{i}^{n}$

当特征根为重根时，若$\alpha _{1}$为特征方程的$K$重根，齐次解为：

$y_{h}(n)=\sum _{i=1}^{K}n^{K-i}\alpha _{1}^{n}$

特解$y_{p}(n)=D(n)$的形式由激励函数$x(n)$的形式决定。

一般情况，当激励函数$x(n)$代入方程。

方程右方出现$n^{k}$的形式，则特解选择

$y_{p}(n)=A_{0}n^{k}+A_{1}n^{k-1}+\cdots +A_{k}$

当方程右方出现$a^{n}$的形式，则特解选择

当$a$不是特征根时

$y_{p}(n)=Aa^{n}$

当$a$是特征根时

$y_{p}(n)=(A_{1}n+A_{0})a^{n}$

当$a$为$r$重根时

$y_{p}(n)=(A_{r}n^{r}+A_{r-1}n^{r-1}+\cdots +A_{1}n+A_{0})a^{n}$

将特解带入原方程，求出待定系数。根据边界条件，可求出齐次节待定系数。

例子

我们用待定系数法来解以下的常系数非齐次线性递推关系：

$a_{n+1}=2a_{n}+3^{n}+5n\,$

对应的齐次递推关系

$b_{n+1}=2b_{n}\,$

的齐次解是：

$b_{n}=c_{1}2^{n}\,$

我们猜测特解的形式为：

$a_{n}=c_{2}3^{n}+c_{3}n+c_{4}\,$

代入原递推关系中，我们便得到：

$c_{2}3^{n+1}+c_{3}(n+1)+c_{4}=2(c_{2}3^{n}+c_{3}n+c_{4})+3^{n}+5n\,$

比较等式两端的$3^{n}$项的系数，可得：

$3c_{2}=2c_{2}+1\,$

$c_{2}=1\,$

比较等式两端的$n$项的系数，可得：

$c_{3}=2c_{3}+5\,$

$c_{3}=-5\,$

比较等式两端的常数项，可得：

$c_{3}+c_{4}=2c_{4}\,$

$c_{4}=c_{3}=-5\,$

因此原递推关系的通解为：

$a_{n}=c_{1}2^{n}+3^{n}-5n-5\,$

与微分方程的关系

数值求解常微分方程时，经常会遇到递归关系。例如，求解如下初值问题时

$y'(t)=f(t,y(t)),\qquad y(t_{0})=y_{0},\qquad \qquad$

如采用欧拉法和步长h，可以通过如下递归关系计算$y_{0}=y(t_{0})$, $y_{1}=y(t_{0}+h),$ $y_{2}=y(t_{0}+2h),...$

$y_{n+1}=y_{n}+hf(t_{n},y_{n})$

线性一阶微分方程组可以用离散化条目中介绍的方法解析地精确离散化。

参考

• 递归
• 差分
• 主定理——分析算法复杂度的方法，从递归式得出通项的大小估计
• 圆点段证明（英语：Circle points segments proof）
• 母函数——形式幂级数，其系数隐含某数列的信息

外部链接

• Difference and Functional Equations: Exact Solutions （页面存档备份，存于互联网档案馆） at EqWorld - The World of Mathematical Equations.
• Difference and Functional Equations: Methods （页面存档备份，存于互联网档案馆） at EqWorld - The World of Mathematical Equations.