遞迴關係式

维基百科，自由的百科全书

zh-cn:递推关系;zh-tw:遞迴關係式在數學上，zh-cn:递推关系;zh-tw:遞迴關係式（recurrence relation），也就是差分方程（difference equation），是一種zh-cn:递推;zh-tw:遞迴地定義一個序列的方程式：序列的每一項目是定義為前一項的函數。

舉個例子（邏輯映射(logistic map)）：

$x_{n+1} = r x_n (1 - x_n) \,$

某些簡單定義的遞迴關係式可能擁有非常複雜的（混亂的）行為，且有時候在數學的領域稱為非線性分析中被物理學家和數學家所研究。

解一個遞迴關係式的意思，就是得到一種n的非遞迴函數。

[编辑] 常係數線性齊次遞迴關係式

（Linear homogeneous recurrence relations with constant coefficients）

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

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

齊次意思為zh-cn:关系;zh-tw:關係式的常數項為零。

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

[编辑] 解線性遞迴關係式

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

二階遞迴關係式的形式：

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

我們擁有解為rⁿ：

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

兩邊除以 $r n - 2$ 我們可以得到：

$r^2=Ar+B \,$

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

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

$a_n = C\lambda_1^n+D\lambda_2^n \,$

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

$a_n = C\lambda^n+Dn\lambda^n \,$

C 和 D 都是常數。

額外地，如果這種 $a n = A a n - 1 + B$ 形式的方程式你可以把 "n" 用 2 來替代，且得到如上的 $r 2 = A r + B$ 。常數 "C" 和 "D" 可以從 "附屬的條件（side conditions）" 中得到，通常是已知 $a 0 = a$ , $a 1 = b$ 。

Different solutions are obtained depending on the nature of the roots of the characteristic equation.

If the recurrence is inhomogeneous, a particular solution can be found by the method of undetermined coefficients and the solution is the sum of the solution of the homogeneous and the particular solutions.

Interestingly, the method for solving linear differential equations is similar to the method above — the "intelligent guess" for linear differential equations is e^x.

This is not a coincidence. If you consider the Taylor series of the solution to a linear differential equation:

$\sum_{n=0}^{\infin} \frac{f^{(n)}(a)}{n!} (x-a)^{n}$

you see that the coefficients of the series are given by the n-th derivative of f(x) evaluated at the point a. The differential equation provides a linear difference equation relating these coefficients.

This equivalence can be used to quickly solve for the recurrence relationship for the coefficients in the power series solution of a linear differential equation.

The rule of thumb (for equations in which the polynomial multiplying the first term is non-zero at zero) is that:

y [k] - > f [n + k]

and more generally

x m * y [k] - > n (n - 1)(n - m + 1) f [n + k - m]

EXAMPLE: The recurrence relationship for the Taylor series coefficients of the equation:

(x 2 + 3 x - 4) y [3] - (3 x + 1) y [2] + 2 y = 0

is given by

n (n - 1) f [n + 1] + 3 n f [n + 2] - 4 f [n + 3] - 3 n f [n + 1] - f [n + 2] + 2 f [n] = 0

- 4 f [n + 3] + 2 n f [n + 2] + n (n - 4) f [n + 1] + 2 f [n] = 0

This example shows how problems generally solved using the power series solution method taught in normal differential equation classes can be solved in a much easier way.

EXAMPLE: The differential equation ay" + by' +cy = 0 has solution