遞迴關係式

遞推關係（recurrence relation），也就是差分方程（difference equation），是一種遞推地定義一個序列的方程式：序列的每一項目是定義為前一項的函數。

舉個例子（户口調查映射(logistic map)）：

某些簡單定義的遞推關係式可能會表現出非常複雜的（混沌的）性質，他們屬於數學中的非線性分析領域。

所謂解一個遞推關係式，也就是求其解析解，即關於n的非遞歸函數。 ^[1] 

線性字眼的意思是序列的每一項目是被定義為前一項的一種線性函數。係數和常數可能視n而定，甚至是非線性地。

一種特別的情況是當係數並不依照n而定。

齊次意思為關係的常數項為零。

為了要得到線性遞歸唯一的解，必須有一些起始條件，就是序列的第一個數字無法依照該序列的其他數字而定時，且必須設定為某些數值。 ^[2] 

線性字眼的意思是序列的每一項目是被定義為前一項的一種線性函數。係數和常數可能視 n 而定，甚至是非線性地。

一種特別的情況是當係數並不依照 n 而定。

齊次意思為關係的常數項為零。

為了要得到線性遞歸唯一的解，必須有一些起始條件，就是序列的第一個數字無法依照該序列的其他數字而定時，且必須設定為某些數值。

遞推關係式的解通常是由系統的方法中找出來，通常藉由使用生成函數（形式冪級數）或藉由觀察r是一種對r的特定數值之解的事實。

二階遞推關係式的形式：

我們擁有解為r：

兩邊除以我們可以得到：

這就是遞推關係式的特徵方程。解出r可獲得兩個根（roots），且如果兩個根是不同的，我們可得到解為

而如果兩個根是相同的（當A+4B=0），我們得到

C和D都是常數。

換句話説，將這種形式的方程式，用 2 代入 n 後，就得到上述的。常數 "C" 和 "D" 可以從 "邊界條件（side conditions）" 中得到，通常會像是“已知,”。

（2）常係數線性齊次遞推關係式

對於常係數非齊次線性遞推關係，我們可以用待定係數法來求出它的一個特解，而它的通解就是這個特解與對應的齊次遞推關係的通解的和。也可以使用迭代法求解，但只能得到確切的數值解，不能直接以解析式作答，該方法可利用計算機求解。

一般情況下，常係數線性差分方程可以寫作：

則對應的齊次方程形式為：

則特徵方程為：

當特徵根非重根時，齊次解為：

當特徵根為重根時，若為特徵方程的重根，齊次解為：

特解的形式由激勵函數的形式決定。

一般情況,當激勵函數x(n)代入方程。

方程右方出現的形式，則特解選擇

當方程右方出現的形式，則特解選擇

當a不是特徵根時

當a是特徵根時

當a為r重根時

將特解帶入原方程，求出待定係數。根據邊界條件，可求出齊次節待定係數。

（3）與差分方程的關係

數值求解常微分方程時，經常會遇到遞歸關係。例如，求解如下初值問題時

如採用歐拉法和步長h，可以通過如下遞歸關係計算,

線性一階微分方程組可以用離散化條目中介紹的方法解析地精確離散化。 ^[2] 

解線性遞推關係式範例

斐波那契數(Fibonacci Number)

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

設若:當n趨於無限大之極限值存在，則其值為恰為黃金分割值，1.618....，另一值則為0.618....，兩值互為倒數，也就是説1.618....分之1=0.618....，反之亦然。

起始條件為：

因此，斐波那契數的序列為：