漸化式の特性方程式の意味とうまくいく理由

$$a_n=C_1\lambda_1^n+C_2\lambda_2^n+\cdots +C_k\lambda_k^n$$ が $$a_{n+k}=p_{k-1}a_{n+k-1}+p_{k-2}a_{n+k-2}+\cdots +p_1a_{n+1}+p_0a_n$$ を満たすこと(※)は簡単に確認できる。実際，各 $\lambda_i$ は特性方程式の解なので $$\lambda_i^{n+k}=p_{k-1}\lambda_i^{n+k-1}+p_{k-2}\lambda_i^{n+k-2}+\cdots+p_1\lambda_i^{n+1}+p_0\lambda_i^n$$ である。これを $C_i$ 倍して $i=1$ から $k$ まで加えると(※)を得る。あとは，どんな初期条件 $a_0,a_1,...,a_{k-1}$ であっても，うまいこと $C_1,...,C_k$ を選べば初期条件を満たせることを示す必要がある。これは，$\lambda_1,...,\lambda_k$ が異なるときに $\lambda_1,...,\lambda_k$ からなるヴァンデルモンド行列の行列式が $0$ でないことからわかる。→ヴァンデルモンド行列式の証明と応用例

（一般の場合も同様なので）表記簡略化のために $k=3$，つまり四項間漸化式の場合で説明する。

漸化式は行列とベクトルを用いて， $\begin{pmatrix}a_{n+3}\\a_{n+2}\\a_{n+1}\end{pmatrix}= \begin{pmatrix}p_2&p_1&p_0\\1&0&0\\0&1&0\end{pmatrix} \begin{pmatrix}a_{n+2}\\a_{n+1}\\a_{n}\end{pmatrix}$

と表現できる。左辺のベクトルを $\overrightarrow{x}_{n+1}$，右辺の行列を $A$ とおくと，$\overrightarrow{x}_{n+1}=A\overrightarrow{x}_{n}$ と書ける。

よって，これを繰り返し用いると $\overrightarrow{x}_n=A^{n}\overrightarrow{x}_{0}$ となる。

$\overrightarrow{x}_{0}$ は初期条件から計算できるので，一般項を求めるためには $A^n$ を計算すればよい。

行列 $A$ の特性方程式 $\det (\lambda I-A)=0$ と定理の主張内で定義した特性方程式 $\phi(\lambda)$ は一致する（これは行列式を実際に計算すると分かる→注）。よって，$\phi(\lambda)=0$ の解 $\lambda_1,\cdots,\lambda_k$ は $A$ の固有値である。→固有値，固有ベクトルの定義と具体的な計算方法

$A$ の固有値が全て異なるとき，ある正則行列 $P$ を用いて $A=PDP^{-1}$ と対角化できる。ただし，$D$ は $\lambda_1,\cdots,\lambda_k$ を対角成分に持つ対角行列。→行列の対角化の意味と具体的な計算方法

よって，$A^n=PD^nP^{-1}$ の各成分は $\lambda_1^n,\cdots,\lambda_k^n$ の線形結合で表せる。よって，$\overrightarrow{x}_n$ の各成分も $\lambda_1^n,\cdots,\lambda_k^n$ の線形結合で表せる。