2015/11/24

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

分野: 線形代数  レベル: 大学数学

定数係数の隣接 $k+1$ 項間漸化式:
$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$
について,$k$ 次方程式
$\phi(\lambda)=\lambda^k-p_{k-1}\lambda^{k-1}-p_{k-2}\lambda^{k-2}-\cdots -p_1\lambda-p_0=0$
を特性方程式と言う。特性方程式の解 $\lambda_1,\cdots, \lambda_k$ が全て異なるとき,数列 $a_n$ の一般項は $a_n=C_1\lambda_1^n+C_2\lambda_2^n+\cdots +C_k\lambda_k^n$
と表せる($C_1,\cdots,C_k$ は初期条件によって決まる定数)。

具体例

隣接二項間漸化式($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$ を計算すればよいことが分かります。

冒頭の定理の証明

証明

行列 $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$ の線形結合で表せる。

注:$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$
は簡単に確認できます。一般の場合も同様です。

高校生にも理解して欲しい定理ですが,線形代数の知識がガッツリ必要なのが残念です。
分野: 線形代数  レベル: 大学数学