漸化式
一階の漸化式については特段の理論を要しない。漸化式
a n = r a n − 1 {\displaystyle a_{n}=ra_{n-1}}
は明らかに初期値 a0 = 1 に対して an = r を解にもち、一般に a0 = k とすれば一般解 an = kr が得られる。この漸化式の特性多項式を 0 に等しいとおいて得られる特性方程式(固有方程式)は、単に t − r = 0 で与えられることに注意。
高階の漸化式の解は、しばしば an = r がちょうど t = r が特性多項式の根となるような漸化式の解となるという事実を用いて、機械的に求めることができる。方法としては直接、あるいは母函数(形式冪級数)、行列などを用いる。
たとえば
a n = A a n − 1 + B a n − 2 {\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}}
という形の漸化式を考えよう。この漸化式が an = r と同じ形の解の一般形をもつのはどのようなときだろうか。実際に代入してみれば
r n = A r n − 1 + B r n − 2 {\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}
が任意の n(> 1) について成り立たなければならないことがわかる。両辺を r で割れば、意味はそのままに方程式 r − Ar − B = 0 に簡約することができる。これがこの漸化式の特性方程式である。
もう少し詳しく言えば、この線型漸化式は各 n(> d − 1) に対する無限本の線型方程式に関する連立方程式であり、この形の漸化式を満たす列は線形回帰数列 (linear recursive sequence) と呼ばれ、あるいは短く "LRS" とも呼ばれる。d-階の線型再帰列は初期値 a0, ..., ad−1 を任意に選ぶ分だけの自由度 d を持ち、それら初期値に対して一意に決定される。
この形の線型漸化式と同じ係数を持つ、漸化式の固有多項式または特性多項式 (characteristic polynomial) あるいは補助多項式 (auxiliary polynomial) と呼ばれる多項式
p ( t ) := t d − c 1 t d − 1 − c 2 t d − 2 − ⋯ − c d {\displaystyle p(t):=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}
は、その d 個の根が漸化式を満たす数列を求め、理解するのにきわめて重要な役割を果たす。
定数係数の d-階斉次線型漸化式は、一般に
a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c d a n − d {\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d}}
の形に表される式で、d 個の係数 ci はすべての i について定数となるものである。
一般にd-階斉次線型漸化式の解は、異なる公比をもつ d-個の幾何数列の和として表される。例外は、それらの幾何数列の公比を与える方程式の根が重根を持つ場合である。このように幾何数列の和として書かれた式をビネーの公式 (Binet's formula) という(ただし「ビネーの公式」という名称は、フィボナッチ数列の一般項を二つの冪数列の和として表す式の意味で用いられることのほうが多い)。
線型漸化式 Tn = cd−1T + cd−2T + ... + c0Tn−d が与えられたとき、その特性多項式のコンパニオン行列の転置
( 0 1 0 ⋯ 0 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ 1 − c 0 − c 1 − c 2 ⋯ − c d − 1 ) {\displaystyle {\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\-c_{0}&-c_{1}&-c_{2}&\cdots &-c_{d-1}\end{pmatrix}}}
を C とすると、明らかに
( a n ⋮ a n + ( d − 1 ) ) = C n ( a 0 ⋮ a d − 1 ) {\displaystyle {\begin{pmatrix}a_{n}\\\vdots \\a_{n+(d-1)}\end{pmatrix}}=C^{n}{\begin{pmatrix}a_{0}\\\vdots \\a_{d-1}\end{pmatrix}}}
が成り立つ。固有値 λ1, ..., λd に対応する固有基底 v1, ..., vd を決めれば、線型再帰列の初期値を固有ベクトルの線型結合
( a 0 ⋮ a d − 1 ) = b 1 v 1 + ⋯ + b d v d {\displaystyle {\begin{pmatrix}a_{0}\\\vdots \\a_{d-1}\end{pmatrix}}=b_{1}v_{1}+\cdots +b_{d}v_{d}}