遞迴關係式

递推关系（英語：Recurrence relation），在數學上也就是差分方程（英語：Difference equation），是一種递推地定義一個序列的方程式：序列的每一項目是定義為前若干項的函數。

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

$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}$」。

範例：斐波那契数（英語：Fibonacci Number）

斐波那契数是使用一種線性遞迴關係式來定義：

$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.