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

具体例

隣接二項間漸化式（$k=1$）

$k=1$ の場合，$a_{n+1}=p_0a_n$ という漸化式です。この特性方程式は $\lambda-p_0=0$ となり，解は $\lambda=p_0$ です。一般項は $a_n=Cp_0^n$ と表せます（ただの等比数列）。

隣接三項間漸化式（$k=2$）

$k=2$ の場合，$a_{n+2}=p_1a_{n+1}+p_0a_n$ という漸化式です。この特性方程式は $\lambda^2-p_1\lambda-p_0=0$ となり，この解を $\lambda_1,\lambda_2$ とおくと（$\lambda_1\neq \lambda_2$ の場合），一般項は $a_n=C_1\lambda_1^n+C_2\lambda_2^n$ と表せます。 →三項間漸化式の3通りの解き方

なお，この記事で扱う漸化式は定数項が $0$ のもののみです。 $a_{n+1}=pa_n+q$ など，定数項が $0$ でない場合は（多くの場合）平行移動することで定数項が $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$ を計算すればよいことが分かります。

冒頭の定理の証明

注： $k=3$ の場合，

$\det \begin{pmatrix}\lambda-p_2&-p_1&-p_0\\-1&\lambda&0\\0&-1&\lambda\end{pmatrix}=\lambda^3-p_2\lambda^2-p_1\lambda-p_0$

は簡単に確認できます。一般の場合も同様です。