漸化式
階数 d の定数係数斉次線型漸化式が与えられたとき、p(t) をその特性多項式
t d − c 1 t d − 1 − c 2 t d − 2 − ⋯ − c d {\displaystyle t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}
とし、λ を重複度 r の特性根とする(つまり (t − λ) が p(t) を割り切る)。このとき、
r 個の数列 λ, nλ, nλ, ..., nλ は与えられた漸化式をおのおの満たす。これを p(t) の相異なる全ての根 λ に亘って考えたものは、与えられた漸化式の任意の解を生成する。
この定理の帰結として、定数係数斉次線型漸化式は次の手順に従って解くことができる。
漸化式の特性多項式 p(t) を求める。
p(t) の根とその重複度を求める。
an を未定係数 bi を持つ(上で述べたように重複度を考慮した)全ての根の冪の線型結合 a n = ( b 1 λ 1 n + b 2 n λ 1 n + ⋯ + b r n r − 1 λ 1 n ) + ⋯ + ( b d − q + 1 λ ∗ n + b d − q + 2 n λ ∗ n + ⋯ + b d n q − 1 λ ∗ n ) {\displaystyle {\begin{aligned}a_{n}=&(b_{1}\lambda _{1}^{n}+b_{2}n\lambda _{1}^{n}+\cdots +b_{r}n^{r-1}\lambda _{1}^{n})\\&\quad +\cdots +(b_{d-q+1}\lambda _{*}^{n}+b_{d-q+2}n\lambda _{*}^{n}+\cdots +b_{d}n^{q-1}\lambda _{*}^{n})\end{aligned}}} として書く(q は λ* の重複度である)。
今考えている二階漸化式の場合、特性根に関するこの条件は |A| < 1 − B < 2 に同値であることが示せる。
上記の例は定数項の無い斉次の場合であった。定数項 K を加えて、非斉次の場合の漸化式
b n = A b n − 1 + B b n − 2 + K {\displaystyle b_{n}=Ab_{n-1}+Bb_{n-2}+K\,}
を考えよう。これは次のようにして斉次の場合に帰着することができる。不動点 b は bn = bn−1 = bn−2 = b* と置くことによって、
b ∗ = K 1 − A − B {\displaystyle b^{*}={\frac {K}{1-A-B}}}
と求められる。これにより、先ほどの非斉次漸化式は
[ b n − b ∗ ] = A [ b n − 1 − b ∗ ] + B [ b n − 2 − b ∗ ] {\displaystyle [b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}]}
なる形の斉次漸化式に書き直すことができる(これは上述のように解くことができる)。
二階の場合に特性根の言葉で述べた安定性条件は、一般の n-階でもやはり有効であることに注意。つまり漸化式の解が安定であるための必要十分条件は、漸化式の特性多項式の全ての根が 1 より小さい絶対値を持つことである。