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

更新日時 2021/03/07

定数係数の隣接 k+1k+1 項間漸化式:

an+k=pk1an+k1+pk2an+k2++p1an+1+p0ana_{n+k}=p_{k-1}a_{n+k-1}+p_{k-2}a_{n+k-2}+\cdots +p_1a_{n+1}+p_0a_n

について,kk 次方程式

ϕ(λ)=λkpk1λk1pk2λk2p1λp0=0\phi(\lambda)=\lambda^k-p_{k-1}\lambda^{k-1}-p_{k-2}\lambda^{k-2}-\cdots -p_1\lambda-p_0=0

を特性方程式と言う。特性方程式の解 λ1,,λk\lambda_1,\cdots, \lambda_k が全て異なるとき,数列 ana_n の一般項は an=C1λ1n+C2λ2n++Ckλkna_n=C_1\lambda_1^n+C_2\lambda_2^n+\cdots +C_k\lambda_k^n

と表せる(C1,,CkC_1,\cdots,C_k は初期条件によって決まる定数)。

目次
  • 具体例

  • 漸化式を行列で表現する

  • 冒頭の定理の証明

具体例

隣接二項間漸化式(k=1k=1

k=1k=1 の場合,an+1=p0ana_{n+1}=p_0a_n という漸化式です。この特性方程式は λp0=0\lambda-p_0=0 となり,解は λ=p0\lambda=p_0 です。一般項は an=Cp0na_n=Cp_0^n と表せます(ただの等比数列)。

隣接三項間漸化式(k=2k=2

k=2k=2 の場合,an+2=p1an+1+p0ana_{n+2}=p_1a_{n+1}+p_0a_n という漸化式です。この特性方程式は λ2p1λp0=0\lambda^2-p_1\lambda-p_0=0 となり,この解を λ1,λ2\lambda_1,\lambda_2 とおくと(λ1λ2\lambda_1\neq \lambda_2 の場合),一般項は an=C1λ1n+C2λ2na_n=C_1\lambda_1^n+C_2\lambda_2^n と表せます。 →三項間漸化式の3通りの解き方

なお,この記事で扱う漸化式は定数項が 00 のもののみです。 an+1=pan+qa_{n+1}=pa_n+q など,定数項が 00 でない場合は(多くの場合)平行移動することで定数項が 00 である場合に帰着できます。

漸化式を行列で表現する

冒頭の定理を理解するには行列の知識(高校数学範囲外)が必要です。(一般の場合も同様なので)表記簡略化のために k=3k=3 ,つまり四項間漸化式の場合で説明します。

漸化式は行列とベクトルを用いて,

(an+3an+2an+1)=(p2p1p0100010)(an+2an+1an)\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}

と表現できます。

左辺のベクトルを xundefinedn+1\overrightarrow{x}_{n+1} ,右辺の行列を AA とおくと,xundefinedn+1=Axundefinedn\overrightarrow{x}_{n+1}=A\overrightarrow{x}_{n} と書けます。

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

xundefined0\overrightarrow{x}_{0} は初期条件から計算できるので,一般項を求めるためには AnA^n を計算すればよいことが分かります。

冒頭の定理の証明

証明

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

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

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

注: k=3k=3 の場合,

det(λp2p1p01λ001λ)=λ3p2λ2p1λp0\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

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

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