漸化式
フィボナッチ数列は線型漸化式
F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}}
に初期値、 F 0 := 0 , F 1 := 1 {\displaystyle F_{0}:=0,\ F_{1}:=1} を与えて得られる。
この漸化式は、陽に書けば F 2 = F 1 + F 0 , F 3 = F 2 + F 1 , F 4 = F 3 + F 2 , ... {\displaystyle F_{2}=F_{1}+F_{0},\ F_{3}=F_{2}+F_{1},\ F_{4}=F_{3}+F_{2},\dots } といった無限個の式と同じである。
こうして得られるフィボナッチ数列のはじめのほうを書けば
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
となる。後述するような方法で漸化式を解けば、特性多項式(固有多項式) t - t - 1 の二つの根を用いた閉じた式(英語版)が得られる。フィボナッチ数列の母関数は
t 1 − t − t 2 {\displaystyle {\frac {t}{1-t-t^{2}}}}
という有理式である。
線型再帰列は、その母函数が有理函数となるような数列として特徴付けられる。母函数の分母は(適当な変換をうける違いを除いて)特性多項式であり、分子は初期値から決まる。
もっとも単純なものは、an = an−d なる周期数列 a0, a1, ..., ad−1, a0, a1, ... の場合であり、この列の母函数は幾何数列の和
a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 1 − x d = ( a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 ) + ( a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 ) x d + ( a 0 + a 1 x 1 + ⋯ + a d − 1 x d − 1 ) x 2 d + ⋯ {\displaystyle {\begin{aligned}&{\frac {a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}}{1-x^{d}}}\\[9pt]&=\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)\\&\qquad +\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{d}\\&\qquad +\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{2d}+\cdots \end{aligned}}}
有理差分方程式は
w t + 1 = a w t + b c w t + d {\displaystyle w_{t+1}={\frac {aw_{t}+b}{cw_{t}+d}}}
というような形をしている。このような方程式は wt を、それ自身は線型に増加する別の変数 xt の非線型変換として書くことで解くことができる。したがって、xt に関する線型差分方程式を解くのに、標準的な方法が使える。
状態ベクトル x, 遷移行列 A をもつ一階の行列係数差分方程式
[ x t − x ∗ ] = A [ x t − 1 − x ∗ ] {\displaystyle [x_{t}-x^{*}]=A[x_{t-1}-x^{*}]}
で、x が定常状態ベクトル x に漸近的に収斂するための必要十分条件は、遷移行列 A の全ての固有値が(それが実数か複素数かに関わらず)1 より小さい絶対値を持つことである。
これがもとの漸化式の一般解を与えるものとなる。
前段の一般解で n = 0, 1, ..., d として a0, a1, ..., ad をもとの漸化式における(初期値として与えられている)既知の a0, a1, ..., ad に一致させる。ただしここで、もとの漸化式の an の値として連続した番号のものでなくとも、どこでもいいから d 個わかってさえいればいいということには注意(つまり、考えている漸化式が三階であれば、たとえば a0, a1 と a4 を使うことができる)。これにより、d 個の未知数を含む d 本の連立一次方程式が得られる。これを一般解における未定係数 b1 , b2, ..., bd に対して解いて、一般解に代入してもとの漸化式の特殊解を得、それらがもとの漸化式の初期条件を満たす(したがって任意の a0, a1, a2, ... についてもとの漸化式からえられる値に一致する)ことを確かめる。
一変数(一元)漸化式は(一次元整格子点 (grid) の上で定義される函数としての)数列について記述するものである。多変数(n-元)漸化式は同様に n-次元整格子点 (n-grid) 上で定まる概念であると理解することができる。n-次元整格子点上で定義される函数(n-重数列)についても偏差分方程式 (partial difference equations) を考えることができる。