$$
p_{k-1}a_{n+(k-1)}
+p_{k-2}a_{n+(k-2)}
+\cdots
+p_{1}a_{n+1}
+p_{0}a_{n}
=0
$$
で定まる数列\(\{a_n\}\)の一般項を考える.
特性方程式
$$
p_{k-1}x^{k-1}
+p_{k-2}x^{k-2}
+\cdots
+p_{1}x
+p_{0}
=0
$$
の解を\(\alpha_1,\alpha_2,\cdots,\alpha_{k-1}\)とし,
任意の\(i,j\)に対して,
\(\alpha_i\ne\alpha_j\)
を仮定する.
このとき,
数列\(\{a_n\}\)の一般項は,
$$
a_n=\sum_{j=1}^{k-1}\sum_{i=1}^{k-1}a_jv_{i,k-j}\alpha_i^{n-1}
$$
と表せる.
ここで,
\(v_{i,k-j}\)は,
ラグランジュ基底多項式
$$
\ell_i(x)
=\prod_{j=1,j\ne i}^{k-1}\frac{x-\alpha_j}{\alpha_i-\alpha_j}
$$
の
展開式における
\(j-1\)次の項の係数である.