【漸化式】例題で学ぶ：3項間漸化式の解法（行列／特性方程式）

　高校数学では、３項間漸化式の問題は特性方程式を用いて解く（2章参照）。ここでは、別解として行列の対角化を用いた解法を紹介する。以下の例題を解いてみる。

例題

以下の漸化式を満たす数列 $\{a_n\}$ の一般解を求めよ。

$\begin{eqnarray*} a_{n+1}=3a_n + 4a_{n-1} \end{eqnarray*}$

ここで $n$ は2以上の整数で、 $a_1$ と $a_2$ は与えられているものとする。

1. 行列で漸化式を解く
2. 特性方程式で解く（高校数学レベル）
3. まとめ

1. 行列で漸化式を解く

1.1 行列で表現

　例題の漸化式と等価な式を考える。以下のように考える。

$\begin{eqnarray*} \begin{cases} a_{n+1}=3a_n + 4a_{n-1} \\ a_n = 1\cdot a_n + 0\cdot a_{n-1} \end{cases} \end{eqnarray*}$

そうすると、この連立方程式は行列 $A$

$\begin{eqnarray*} A=\left(\begin{array}{cc} 3& 4 \\ 1 & 0 \end{array}\right) \end{eqnarray*}$

を用いて、

$\begin{eqnarray*} \left(\begin{array}{c} a_{n+1} \\ a_{n} \end{array}\right)= A \left(\begin{array}{c} a_n \\ a_{n-1} \end{array}\right) \end{eqnarray*}$

と表すことができる。

　ここで、「一般項 $a_n$ を求める問題」は、「 $A^{n-1}$ を求める問題」に置き換わった。実際、漸化式を繰り返し使うと、

$\begin{eqnarray*} \left(\begin{array}{c} a_{n+1} \\ a_{n} \end{array}\right)&=& A \left(\begin{array}{c} a_n \\ a_{n-1} \end{array}\right) \\ \\ &=&A^2 \left(\begin{array}{c} a_{n-1} \\ a_{n-2} \end{array}\right) \\ \\ &=& \cdots \\ \\ &=&A^{n-1} \left(\begin{array}{c} a_2 \\ a_{1} \end{array}\right) \end{eqnarray*}$

となる。結局、 $A^{n-1}$ が計算できれば $a_n$ は求めることができる。以下では固有値と固有関数を用いて対角化した後に、 $A^{n-1}$ を計算する。

1.2 固有値・固有関数

　 $A$ の固有値・固有関数を求めよう。 $E$ は２次の単位行列である。

$\begin{eqnarray*} &&\left|A-\lambda E\right|=\left|\begin{array}{cc} 3-\lambda& 4 \\ 1 & -\lambda \end{array}\right|=0 \\ \\ \Leftrightarrow && \lambda^2 -3\lambda -4 = 0 \\ \\ && \therefore \lambda = -1,\,4 \end{eqnarray*}$

それぞれの固有値に対して、固有関数を求める。

(i) $\lambda=-1$ のとき：

$\begin{eqnarray*} \left(\begin{array}{cc} 3-(-1)& 4 \\ 1 & -(-1) \end{array}\right)\\ \\ \therefore \quad \left(\begin{array}{c} x\\ y \end{array}\right)= \left(\begin{array}{c} 1\\ -1 \end{array}\right) \quad \blacksquare \end{eqnarray*}$

(ii) $\lambda=4$ のとき：

$\begin{eqnarray*} \left(\begin{array}{cc} 3-4& 4 \\ 1 & -4 \end{array}\right)\\ \\ \therefore \quad \left(\begin{array}{c} x\\ y \end{array}\right)= \left(\begin{array}{c} 4\\ 1 \end{array}\right) \quad \blacksquare \end{eqnarray*}$

1.3 対角化／行列のn-1乗

　上で求めた固有関数を使って対角化する。

$\begin{eqnarray*} P\equiv\left(\begin{array}{cc} 1& 4 \\ -1 & 1 \end{array}\right) \end{eqnarray*}$

と定義すると、 $P$ の逆行列は、

$\begin{eqnarray*} P^{-1}=\frac{1}{5} \left(\begin{array}{cc} 1& -4 \\ 1 & 1 \end{array}\right) \end{eqnarray*}$

である。この $P$ と $P^{-1}$ により $A$ を対角化する。（念の為計算して対角化されていることを確認した。）

$\begin{eqnarray*} P^{-1}AP &=& \frac{1}{5} \left(\begin{array}{cc} 1& -4 \\ 1 & 1 \end{array}\right) \left(\begin{array}{cc} 3& 4 \\ 1 & 0 \end{array}\right) \left(\begin{array}{cc} 1& 4 \\ -1 & 1 \end{array}\right) \\ \\ &=& \frac{1}{5} \left(\begin{array}{cc} 1& -4 \\ 1 & 1 \end{array}\right) \left(\begin{array}{cc} -1& 16 \\ 1 & 4 \end{array}\right) \\ \\ &=& \left(\begin{array}{cc} -1& 0 \\ 0 & 4 \end{array}\right) \quad \blacksquare \end{eqnarray*}$

　固有関数を並べた順番に、左上から固有値が並ぶように対角化される。最後の対角化行列を $D$ と置く。

$\begin{eqnarray*} P^{-1}AP =\left(\begin{array}{cc} -1& 0 \\ 0 & 4 \end{array}\right) \equiv D \quad \cdots (*) \end{eqnarray*}$

　このとき、

　 $A^{n-1}$ を求めるため、(*) 式の両辺を $n-1$ 乗する。

左辺：

$\begin{eqnarray*} \left(P^{-1}AP\right)^{n-1} &=&P^{-1}AP \cdot P^{-1}AP \cdot \cdots \cdot P^{-1}AP \\ &=&P^{-1}A (PP^{-1}) A (PP^{-1})\cdot \cdots \cdot (PP^{-1}) AP\\ &=&P^{-1}A^{n-1}P\\ && (\because \, PP^{-1}=E) \end{eqnarray*}$

右辺：

$\begin{eqnarray*} D^{n-1}=\left(\begin{array}{cc} (-1)^{n-1}& 0 \\ 0 & 4^{n-1} \end{array}\right) \end{eqnarray*}$

これより $A^{n-1}$ が計算できる。

$\begin{eqnarray*} P^{-1}A^{n-1}P &=& D^{n-1} \\ \\ \Leftrightarrow A^{n-1}&=& PD^{n-1}P \\ \\ &=& \left(\begin{array}{cc} 1& 4 \\ -1 & 1 \end{array}\right) \left(\begin{array}{cc} (-1)^{n-1}& 0 \\ 0 & 4^{n-1} \end{array}\right)\, \frac{1}{5} \left(\begin{array}{cc} 1& -4 \\ 1 & 1 \end{array}\right) \\ \\ &=& \frac{1}{5} \left(\begin{array}{cc} (-1)^{n-1}& 4^{n}\\ (-1)^n & 4^{n-1} \end{array}\right) \left(\begin{array}{cc} 1& -4 \\ 1 & 1 \end{array}\right) \\ \\ &=& \frac{1}{5} \left(\begin{array}{cc} (-1)^{n-1} + 4^{n} & -4 (-1)^{n-1} + 4^{n}\\ (-1)^{n} + 4^{n-1}& -4 (-1)^n + 4^{n-1} \end{array}\right) \; \blacksquare \\ \\ &\equiv& \left(\begin{array}{cc} A^{n-1}_{11}& A^{n-1}_{12} \\ \textcolor{red}{A^{n-1}_{21}} & \textcolor{red}{A^{n-1}_{22}} \end{array}\right) \end{eqnarray*}$

　最終的に使うのは $A$ の要素のうち $A^{n-1}_{21}$ と $A^{n-1}_{22}$ である。

$\begin{eqnarray*} A^{n-1}_{21}&=&\frac{1}{5}\left\{(-1)^{n} + 4^{n-1}\right\}\\ \\ A^{n-1}_{22}&=&\frac{1}{5}\left\{ -4 (-1)^n + 4^{n-1}\right\} \end{eqnarray*}$

1.4 一般解

　 $A^{n-1}$ がわかったので、 $a_n$ と $a_2,a_1$ をつなげることができる。

$\begin{eqnarray*} \left(\begin{array}{c} a_{n+1} \\ a_{n} \end{array}\right)&=& \left(\begin{array}{cc} A^{n-1}_{11}& A^{n-1}_{12} \\A^{n-1}_{21} & A^{n-1}_{22} \end{array}\right) \left(\begin{array}{c} a_2 \\ a_{1} \end{array}\right) \end{eqnarray*}$

であるため、

$\begin{eqnarray*} a_n &=& A^{n-1}_{11}a_2 + A^{n-1}_{11}a_1 \\ \\ &=& \frac{1}{5}\left[\quad\;(-1)^{n} + 4^{n-1}\right]a_2 \\ &+& \frac{1}{5}\left[ -4 (-1)^n + 4^{n-1}\right]a_1 \\ \\ &=& \frac{1}{5}\left\{(a_2-4a_1)\cdot(-1)^{n} + (a_2+a_1)\cdot4^{n-1}\right\} \quad \blacksquare \end{eqnarray*}$

　念の為、 $n=1,2$ を代入して正しいかどうか確認しておくのがよい。

2. 特性方程式で解く（高校数学レベル）

　以下では、漸化式の特性方程式で解いた解法のうちの１つを示す。

【解答】

　特性方程式は $x^2-3x-4=0 \Leftrightarrow x=-1,4$ であるため、

$\begin{eqnarray*} \begin{cases} a_{n+1}-4a_n = -(a_n -4a_{n-1}) \\ a_{n+1}+a_n = 4(a_n+a_{n-1}) \end{cases} \end{eqnarray*}$

　の２通りに変形できる。下の式を使う。これは公比4の等比数列であるため、

$\begin{eqnarray*} a_{n+1}+a_n&=&4(a_n+a_{n-1})\\ &=& 4^2(a_{n-1}+a_{n-2}) \\ \\ &=&\cdots \\ \\ &=& 4^{n-1}(a_2+a_1) \\ \\ \therefore \frac{a_{n+1}+a_n}{4^{n-1}}&=&a_2+a_1 \\ \\ \frac{a_{n+1}}{4^{n-1}}+\frac{1}{4}\cdot\frac{a_n}{4^{n-2}}&=&a_2+a_1 \\ \\ b_{n+1}+\frac{1}{4}b_n &=& a_2+a_1\\ (\,b_n &\equiv& \frac{a_n}{4^{n-2}}\,) \end{eqnarray*}$

　最後の行では、新たな数列 $b_n$ を定義した。 $b_n$ について以下のように変形する。

$\begin{eqnarray*} b_n-\frac{4}{5}(a_2+a_1) &=&-\frac{1}{4}\left(b_{n-1}-\frac{4}{5}(a_2+a_1)\right)\\ \\ &=& \left(-\frac{1}{4}\right)^2 \left(b_{n-2}-\frac{4}{5}(a_2+a_1)\right)\\ \\ &=& \cdots \\ \\ &=& \left(-\frac{1}{4}\right)^{n-1} \left(b_1-\frac{4}{5}(a_2+a_1)\right)\\ \\ &=& \left(-\frac{1}{4}\right)^{n-1} \cdot\frac{16a_1 -4a_2}{5} \\ &&(\because\quad b_1=\frac{a_1}{4^{-1}}=4a_1 ) \end{eqnarray*}$

$\begin{eqnarray*} \therefore\quad b_n=\left(-\frac{1}{4}\right)^{n-1} \cdot\frac{16a_1-4a_2}{5}\right +\frac{4}{5}(a_2+a_1) \end{eqnarray*}$

となる。 $b_n \rightarrow a_n$ と直して、

$\begin{eqnarray*} a_n &=& 4^{n-2} b_n \\ \\ &=& 4^{n-2}\cdot\left\{ \left(-\frac{1}{4}\right)^{n-1} \cdot\frac{16a_1-4a_2}{5} +\frac{4}{5}(a_2+a_1)\right\} \\ \\ &=& (-1)^{n-1}\cdot \frac{1}{4}\cdot \frac{16a_1-4a_2}{5} +\frac{4^{n-1}}{5}(a_2+a_1) \\ \\ &=& \frac{1}{5} \left\{ (-1)^{n-1}(4a_1-a_2) + 4^{n-1}(a_2+a_1) \right\} \\ \\ &=& \frac{1}{5}\left\{(a_2-4a_1)\cdot(-1)^{n} + (a_2+a_1)\cdot4^{n-1}\right\} \quad \blacksquare \end{eqnarray*}$

　1.4 の最後にでてきた答えと一致する。どちらの方法が簡単かはわからない。

3. まとめ

　行列の対角化を使って３項間漸化式を解いてきた。行列の固有値・固有関数を求めて対角化する練習問題にちょうどいい。