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

漸化式の特性方程式の意味と,特性方程式を使った解き方・うまくいく理由を解説します。

  1. 定数項つきの二項間漸化式
  2. 三項間漸化式
  3. NN 項間漸化式

の順に解説します。

定数項つきの二項間漸化式

  • an+1=pan+qa_{n+1}=pa_n+q という漸化式に対して,α\alpha についての方程式 α=pα+q\alpha=p\alpha+q のことを特性方程式と呼ぶことがあります。
  • 漸化式の an+1a_{n+1}ana_n を同じ変数 α\alpha で置き換えたものなので覚えやすいです。

an+1=2an3a_{n+1}=2a_n-3 という漸化式について,特性方程式は α=2α3\alpha=2\alpha-3 です。これを解くと α=3\alpha=3 です。

  • 特性方程式の解 α\alpha をもとに,漸化式が解けます。具体的には,an+1α=p(anα)a_{n+1}-\alpha=p(a_n-\alpha) と変形します。

a1=6,an+1=2an3a_1=6,a_{n+1}=2a_n-3 という漸化式を解きましょう。

さきほど計算したように α=3\alpha=3 でした。

よって an+13=2(an3)a_{n+1}-3=2(a_n-3) と変形できます。

これは,数列 {an3}\{a_n-3\} が公比 22 の等比数列であることを表しています。また,初項は a13=3a_1-3=3 です。よって, an3=3×2n1a_n-3=3\times 2^{n-1} つまり an=3×2n1+3a_n=3\times 2^{n-1}+3 が答えになります。

なぜうまくいくのか

an+1=pan+qa_{n+1}=pa_n+q という漸化式を, an+1α=p(anα)a_{n+1}-\alpha=p(a_n-\alpha) と変形できれば {anα}\{a_n-\alpha\} が等比数列であることを使って漸化式が解けます。そのような α\alpha を探したいです。そこで,紫文字の式を漸化式を使って変形すると, an+1α=panpα=(an+1q)pαa_{n+1}-\alpha=pa_n-p\alpha=(a_{n+1}-q)-p\alpha となります。移項すると,結局 α\alphaα=pα+q\alpha=p\alpha+q を満たせば紫文字の式が成立することがわかります。このような嬉しい α\alpha を探すための式が特性方程式です。たまたまもとの漸化式で an+1=an=αa_{n+1}=a_n=\alpha と置いた式と一致するので覚えやすいです。

三項間漸化式

  • an+2=pan+1+qana_{n+2}=pa_{n+1}+qa_n という三項間漸化式に対して,λ\lambda についての方程式 λ2=pλ+q\lambda^2=p\lambda+q のことを特性方程式と呼びます。
  • 例えば,an+2=5an+16ana_{n+2}=5a_{n+1}-6a_n の特性方程式は λ2=5λ6\lambda^2=5\lambda-6 です。
  • 三項間漸化式は,特性方程式を使って解くことができます。実際,特性方程式の解を λ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通りの解き方 を参照してください。
  • なぜ特性方程式でうまくいくのかは,後述の「k+1k+1 項間漸化式」で紹介します。

k+1項間漸化式

定数係数の隣接 k+1k+1 項間漸化式を考えます。k=2k=2 の場合がさきほどの三項間漸化式です。

定理

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 は初期条件によって決まる定数)。

特性方程式が解ければ漸化式が構成できるというわけです!

この定理を理解するには行列の知識(高校数学範囲外)が必要です。証明を2つ紹介します。

定理の証明1

an=C1λ1n+C2λ2n++Ckλkna_n=C_1\lambda_1^n+C_2\lambda_2^n+\cdots +C_k\lambda_k^nan+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 を満たすこと(※)は簡単に確認できる。実際,各 λi\lambda_i は特性方程式の解なので λin+k=pk1λin+k1+pk2λin+k2++p1λin+1+p0λin\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 である。これを CiC_i 倍して i=1i=1 から kk まで加えると(※)を得る。あとは,どんな初期条件 a0,a1,...,ak1a_0,a_1,...,a_{k-1} であっても,うまいこと C1,...,CkC_1,...,C_k を選べば初期条件を満たせることを示す必要がある。これは,λ1,...,λk\lambda_1,...,\lambda_k が異なるときに λ1,...,λk\lambda_1,...,\lambda_k からなるヴァンデルモンド行列の行列式が 00 でないことからわかる。→ヴァンデルモンド行列式の証明と応用例

定理の証明2

(一般の場合も同様なので)表記簡略化のために 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

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

特性方程式という用語について

  1. 定数項つきの二項間漸化式
  2. 三項間漸化式
  3. NN 項間漸化式

を紹介しました。

  • 2と3における「漸化式の特性方程式」は,3の証明2で見たように,行列の特性方程式に由来しています。つまり,由緒正しい「特性方程式」と言えます。英語でも Characteristic Equation と言います。
  • 一方,1における「漸化式の特性方程式」は単なる平行移動の定数をうまく決めるための方程式です。そのため「特性方程式」と呼ぶのは不適切な気もします。実際,英語で漸化式の Characteristic Equation が1の意味で使われるのは見たことがないです。なお,1次分数型の漸化式でも「平行移動の定数をうまく決めるための方程式」が活躍します。→一次分数型の漸化式の解法と例題

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