3項間漸化式の一般項を線形代数で求める（対角化まで勉強した人向け）

Introduction

裳華房から出版されている 「手を動かしてまなぶシリーズ」 が人気を集めているようです。今年の秋頃、私も 藤岡敦「手を動かしてまなぶ 線形代数」 を読みました。

挫折しにくい工夫がなされていて、高校～大学の良い架け橋になっている本だと感じました。初めて線形代数を学ぶ方におすすめです。

そこで今回は、主に「手を動かしてまなぶ 線形代数」を読んでいる人や、線形代数を学び始めている人に向けた記事を書いてみたいと思います。

内容としては「3項間漸化式の一般項を線形代数で求める」という、定番すぎるものです。しかし、高校～大学の架け橋となる上、線形代数の練習になる良いトピックだと思ったので、取り上げてみたくなりました。

線形代数を使うことで、小高い丘から見下ろすような感じで3項間漸化式を眺められるのではないかと思います。

また、対角化まで勉強していなくとも「これから線形代数を学ぼうと思っている人」も読んでくださったら、うれしいです。本論は飛ばして「さいごに」だけでも良いので……。

※本記事では、一般論だけでなく具体例を進んで扱うスタンスを大事にしています。「もういいよ」と言われそうなほど、しつこく具体的な計算をしていきます。

＜前提知識＞
高校数学～線形代数の対角化くらいまで。「手を動かしてまなぶ 線形代数」の7章までに該当。

3項間漸化式

数列$\{x_n\}$に対して

$$ x_{n+2} = px_{n+1}+qx_{n} $$

のように、前の2項から、次の項を定める関係式が与えられているとします（このような式は「3項間漸化式」と呼ばれています）。

例えば、$x_1=0,x_2=2$で

$$ x_{n+2} = 5x_{n+1}-6x_{n} $$

が与えられた場合

$$ x_3 = 5x_2-6x_1 = 5 \times 2 - 6 \times 0 =10 $$

$$ x_4 = 5x_3-6x_2 = 5 \times 10 - 6 \times 2 =38 $$

$$ x_5 = 5x_4-6x_3 = 5 \times 38 - 6 \times 10 =130 $$

のように、$x_n$の値を次々に定めることができます。

一方で、$x_n$は$n$の式

$$ x_n = -2^n+2\cdot 3^{n-1} $$

と表すこともできます（このような式は「一般項」と呼ばれています）。

高校で学ぶ数学Bでは「3項間漸化式が与えられた上で、一般項を求める」といった問題が定番となっています。

その際、特性方程式

$$ x^2-px-qx=0 $$

の解を求めて、そこから一般項を求めていくという方法がよく知られています。

$$ x_{n+2} = 5x_{n+1}-6x_{n} $$

が与えられた場合、特性方程式の解は

$$ x^2-5x+6=(x-2)(x-3)=0 $$

より、$x=2,3$です。

これを元に

$$ x_{n+2}-3x_{n+1} = 2(x_{n+1}-3x_n) $$

$$ x_{n+2}-2x_{n+1} = 3(x_{n+1}-2x_n) $$

と立式して、$\{x_{n+1}-3x_{n}\}$が公比$2$の等比数列となっていることと、$\{x_{n+1}-2x_{n}\}$が公比$3$の等比数列となっていることから、一般項を求めていく方法です。

本記事では、線形代数を使って、一般項を求めていきましょう。

3項間漸化式を行列で表してみよう

数列$\{x_n\}$の3項間漸化式

$$ x_{n+2} = px_{n+1}+qx_{n} \quad (p,q \in \mathbb{C}) $$

が与えられているとする。

このとき

$$ A= \begin{pmatrix} 0 & 1 \\ q & p \end{pmatrix},\ \boldsymbol{x}_n = \begin{pmatrix} x_n \\ x_{n+1} \end{pmatrix} $$

とすると

$$ \boldsymbol{x}_{n+1} = A \boldsymbol{x}_n $$

が成り立つ。よって

$$ \boldsymbol{x}_n = A\boldsymbol{x}_{n-1}=A^2\boldsymbol{x}_{n-2}=\cdots = A^{n-1}\boldsymbol{x}_1 $$

となり

$$ \boldsymbol{x}_n = A^{n-1}\boldsymbol{x}_1 $$

となることがわかる。ただし、$A^0=E$とする（$E$は単位行列）。

したがって、$\boldsymbol{x}_1= \begin{pmatrix} x_1 \\ x_{2} \end{pmatrix}$が与えられているとき、$A^{n-1}$を求めれば、$\boldsymbol{x}_n$を求めることができるので、数列$\{x_n\}$の一般項がわかる。つまり、$A^{n-1}$を求めることを目標に考えていけばよい。

もしも、$A$が対角化可能ならば、ある正則行列$P \in M_2(\mathbb{C})$が存在して

$$ P^{-1}AP = \begin{pmatrix} \alpha & 0 \\ 0 & \beta \end{pmatrix} \quad (\alpha,\beta \in \mathbb{C}) $$

を満たす。

$$ (P^{-1}AP)^{n-1} = (P^{-1}AP)(P^{-1}AP)\cdots (P^{-1}AP)=P^{-1}A^{n-1}P $$

となることと

$$ \begin{pmatrix} \alpha & 0 \\ 0 & \beta \end{pmatrix} ^{n-1} = \begin{pmatrix} \alpha^{n-1} & 0 \\ 0 & \beta^{n-1} \end{pmatrix} $$

であることから

$$ A^{n-1} = P\begin{pmatrix} \alpha^{n-1} & 0 \\ 0 & \beta^{n-1} \end{pmatrix} P^{-1} $$

となることがわかる。

$A$の固有方程式、固有空間の次元

※このことから、数学Bで漸化式を解く際に使っていた特性方程式は$\Phi_{A}(\lambda)$だったことが確認できます。

※参考になる箇所：藤岡敦「手を動かしてまなぶ 線形代数」pp.194-196

$A$が相異なる2つの固有値を持つ場合

$n$次の（複素）正方行列が互いに異なる$n$個の固有値を持つならば、その正方行列は対角化可能であることが知られています（※参考になる箇所：藤岡敦「手を動かしてまなぶ 線形代数」p.214）。

今回は、$A$に限定して、その事実を確認してみます。

具体的に$P$を求めてみよう。

命題1の証明より、固有値$\alpha,\beta$に対する$A$の固有ベクトル$\boldsymbol{p}_1,\boldsymbol{p}_2$をそれぞれ

$$ \boldsymbol{p}_1 = \begin{pmatrix} 1\\ \alpha \end{pmatrix},\ \boldsymbol{p}_2 = \begin{pmatrix} 1\\ \beta \end{pmatrix} $$

として

$$ P = \begin{pmatrix} \boldsymbol{p}_1 & \boldsymbol{p}_2 \end{pmatrix} = \begin{pmatrix} 1 & 1\\ \alpha & \beta \end{pmatrix} $$

とすればよい。

よって

$$ P^{-1} = \frac{1}{\beta-\alpha} \begin{pmatrix} \beta & -1\\ -\alpha & 1 \end{pmatrix} $$

となる。

また

$$ \Phi_A(\lambda) = \lambda^2-p\lambda-q = (\lambda-\alpha)(\lambda-\beta) = \lambda^2-(\alpha+\beta)\lambda+\alpha\beta $$

より

$$ p = \alpha + \beta,\ q = -\alpha\beta $$

である。

よって

$ \displaystyle{ \begin{align} P^{-1}AP &= \frac{1}{\beta-\alpha} \begin{pmatrix} \beta & -1\\ -\alpha & 1 \end{pmatrix} \begin{pmatrix} 0 & 1\\ q & p \end{pmatrix} \begin{pmatrix} 1 & 1\\ \alpha & \beta \end{pmatrix}\\ &= \frac{1}{\beta-\alpha} \begin{pmatrix} -q & \beta-p\\ q & -\alpha+p \end{pmatrix} \begin{pmatrix} 1 & 1\\ \alpha & \beta \end{pmatrix}\\ &= \frac{1}{\beta-\alpha} \begin{pmatrix} -q+\alpha\beta-p\alpha & -q+\beta^2-p\beta\\ q-\alpha^2+p\alpha & q-\alpha\beta+p\beta \end{pmatrix}\\ &= \frac{1}{\beta-\alpha} \begin{pmatrix} \alpha(\beta-\alpha) & \Phi_A(\beta)\\ -\Phi_A(\alpha) & \beta(\beta-\alpha) \end{pmatrix}\\ &= \begin{pmatrix} \alpha & 0\\ 0 & \beta \end{pmatrix} \end{align} }$

となることが確認できる。

$A$の固有値が1つの場合（固有方程式が重解を持つ場合）

$A$の固有方程式が重解を持つとき、$A$の固有値を$\alpha$、$\alpha$の固有空間を$W(\alpha)$、$W(\alpha)$の次元を$\mathrm{dim}(W(\alpha))$とすると、命題1より

$$ \mathrm{dim}(W(\alpha)) < 2 $$

となるため、$A$は対角化ができません（※参考になる箇所：藤岡敦「手を動かしてまなぶ 線形代数」p.214）。

しかし、任意の複素正方行列は、ジョルダン標準形と呼ばれる行列に相似であることが知られています。対角化はできなくとも、対角行列に近い形まで持っていくことが可能です。

今回は、$A$に限定して、その事実を確認してみます。

具体的に$P$を求めてみよう。

命題1の証明から、固有値$\alpha$に対する$A$の固有ベクトル$\boldsymbol{p}_1$を

$$ \boldsymbol{p}_1 = \begin{pmatrix} 1\\ \alpha \end{pmatrix} $$

とする。

また、$A$の固有方程式$\Phi_A(\lambda)$は重解を持つとき

$$ \lambda^2-p\lambda-q=(\lambda-\alpha)^2=\lambda^2-2\alpha\lambda + \alpha^2 $$

なので

$$ p = 2\alpha,\ q = -\alpha^2 $$

であることがわかる。

$$ (A-\alpha E) \begin{pmatrix} x_1\\ x_2 \end{pmatrix} = \boldsymbol{p}_1 = \begin{pmatrix} 1\\ \alpha \end{pmatrix} $$

とすると

$$ (A-\alpha E \ |\ \boldsymbol{p}_1)= \Biggl( \begin{array}{cc|c} -\alpha& 1 & 1\\ q & p-\alpha & \alpha \end{array}\Biggr) = \Biggl( \begin{array}{cc|c} -\alpha& 1 & 1\\ -\alpha^2 & \alpha & \alpha \end{array}\Biggr) $$

となる。

行基本変形により

$$ (A-\alpha E \ |\ \boldsymbol{p}_1) \longrightarrow \Biggl( \begin{array}{cc|c} -\alpha& 1 & 1\\ 0 & 0 & 0 \end{array}\Biggr) $$

となるので

$$ -\alpha x_1 + x_2 = 1 $$

を満たす。

$x_1=0,x_2=1$とすれば

$$ (A-\alpha E) \begin{pmatrix} 0\\ 1 \end{pmatrix} = \begin{pmatrix} 1\\ \alpha \end{pmatrix} $$

を満たす。

よって

$$ P = \begin{pmatrix} 1 & 0\\ \alpha & 1 \end{pmatrix} $$

とすればよい。

また

$$ P^{-1} = \begin{pmatrix} 1 & 0\\ -\alpha & 1 \end{pmatrix} $$

であり

$ \displaystyle{ \begin{align} P^{-1}AP &= \begin{pmatrix} 1 & 0\\ -\alpha & 1 \end{pmatrix} \begin{pmatrix} 0 & 1\\ q & p \end{pmatrix} \begin{pmatrix} 1 & 0\\ \alpha & 1 \end{pmatrix}\\ &= \begin{pmatrix} 0 & 1\\ q & -\alpha+p \end{pmatrix} \begin{pmatrix} 1 & 0\\ \alpha & 1 \end{pmatrix}\\ &= \begin{pmatrix} \alpha & 1\\ -\Phi_A(\alpha) & -\alpha+p \end{pmatrix}\\ &= \begin{pmatrix} \alpha & 1\\ 0 & \alpha \end{pmatrix} \end{align} }$

となることが確認できる。

4項間漸化式

線形代数を使った方法の良いところの1つとして、$n$項間漸化式へと一般化できる点があります。

4項間漸化式について、その様子を少し見てみましょう。

数列$\{x_n\}$の4項間漸化式

$$ x_{n+3} = px_{n+2}+qx_{n+1}+rx_{n} \quad (p,q,r \in \mathbb{C}) $$

が与えられているとします。

このとき

$$ A= \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1\\ r & q & p \end{pmatrix},\ \boldsymbol{x}_n = \begin{pmatrix} x_n \\ x_{n+1}\\ x_{n+2} \end{pmatrix} $$

とすると

$$ \boldsymbol{x}_{n+1} = A \boldsymbol{x}_n $$

が成り立つので

$$ \boldsymbol{x}_n = A^{n-1}\boldsymbol{x}_1 $$

となります。

したがって、3項間漸化式の場合のように、$A^{n-1}$を求めれば、一般項が求められることがわかります。

$A$が相異なる3つの固有値$\alpha,\beta,\gamma$を持つ場合は、$A$は対角化可能です。

よって、ある正則行列$P \in M_3(\mathbb(C))$が存在して

$$ \boldsymbol{x}_n = \Biggl(P \begin{pmatrix} \alpha^{n-1} & 0 & 0 \\ 0 & \beta^{n-1} & 0\\ 0 & 0 & \gamma^{n-1} \end{pmatrix} P^{-1}\Biggr)\boldsymbol{x}_1 $$

を満たします。

したがって、ある複素数$s,t,u$が存在して、$\{x_n\}$の一般項は

$$ x_n = s\alpha^{n-1}+t\beta^{n-1}+u\gamma^{n-1} $$

と表せることがわかります。

$\Phi_A(\lambda)$が重解を持つ場合は、ジョルダン標準形を考えていくことになりますが、本記事では省略します。

また、$\Phi_A(\lambda)$は

$$ \Phi_A(\lambda) = \begin{vmatrix} \lambda & -1 & 0 \\ 0 & \lambda & -1\\ -r & -q & \lambda-p \end{vmatrix} =\lambda^3-p\lambda^2-q\lambda-r $$

となっています。

さいごに

$n$項間漸化式やジョルダン標準形については、 藤岡敦「手を動かしてまなぶ 続・線形代数」 で詳しく解説されています。

「手を動かしてまなぶ 線形代数」を読み終わったら、ぜひ続編である「手を動かしてまなぶ 続・線形代数」も手にとってみてください。「手を動かしてまなぶ 線形代数」の伏線が回収されていて、楽しいです。

なにかと「役に立つ」と言われている線形代数ですが、1966年に初版が出版された斎藤正彦「線型代数入門」のあとがき（1996年に書かれたもの）には、こんな記述がありました。

この本が出てすぐのころ, ある人から何を目標にして書いたのか, と聞かれたことがある. 若かった私は「十年後の日本の技術水準を上げるためだ」と答えたのを覚えている. 結果的にそのとおりになったのは喜ばしい.
（斎藤正彦「線型代数入門」p.257）

私は線形代数の工学分野への応用などにはくわしくないのですが、この言葉を読むと、線形代数の力を思い知らされます。

現在、「手を動かしてまなぶ 線形代数」はじめ、わかりやすい線形代数の本や解説サイトが存在していて、良い時代になりましたね。