4 連立漸化式

次に、連立の定数係数線形漸化式について考えてみる。

例えば、フィボナッチ数列の 2 つの解

$$b^{(0)}_n=\lambda_0^n=\left(\frac{1+\sqrt{5}}{2}\right)^n,\h... ...1zw} b^{(1)}_n=\lambda_1^n=\left(\frac{1-\sqrt{5}}{2}\right)^n$$

には、$\sqrt{5}$ が含まれているが、 これらを展開すればいずれも有理数と $\sqrt{5}$ の有理数倍の和で書ける。 実際、二項定理により

$$b^{(0)}_n = x_n+y_n\sqrt{5},\hspace{1zw} b^{(1)}_n = x_n-y_n\sqrt{5}$$ (13)

($x_n$, $y_n$ は有理数) の形になることが容易にわかる。 この $x_n$, $y_n$ の満たす漸化式を考えてみよう。

$$b^{(0)}_{n+1} = \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} = b^{(0)}_n\left(\frac{1+\sqrt{5}}{2}\right)$$

であるから、

$$x_{n+1}+y_{n+1}\sqrt{5} = (x_n+y_n\sqrt{5})\left(\frac{1+\sqrt{5}}{2}\right) = \frac{x_n+5y_n}{2}+\frac{x_n+y_n}{2}\sqrt{5}$$

となる。よって、

$$x_{n+1} =\frac{x_n+5y_n}{2},\hspace{1zw} y_{n+1} =\frac{x_n+y_n}{2}$$ (14)

となることがわかる。 これに $x_0$, $y_0$ を与えることで、 順次 $x_1$, $y_1$, $x_2$, $y_2$,...と数列の値が決まっていくことになる。

一般に、$N$ 次元列ベクトルの列

$$X_n=\left[\begin{array}{c}x^{(0)}_n\\ x^{(1)}_n\\ \vdots\\ x^{(N-1)}_n\end{array}\right]\hspace{1zw}(n=0,1,2,\ldots)$$

と、成分が定数である $n\times n$ 行列 $A$ に対して、

$$X_{n+1}=AX_n\hspace{1zw}(n=0,1,2,\ldots)$$ (15)

を 定数係数連立線形同次漸化式 と呼ぶ。(14) は、

$$A=\left[\begin{array}{cc}1/2 & 5/2\\ 1/2 & 1/2\end{array}\r... ...ace{1zw} X_n=\left[\begin{array}{c}x_n\\ y_n\end{array}\right]$$ (16)

の場合になっている。

(15) より、$X_n$ は、

$$X_1=AX_0,\hspace{1zw}X_2=AX_1=A^2X_0,\hspace{1zw}X_3=AX_2=A^3X_0,\hspace{1zw}\ldots$$

のようになるから、一般に

$$X_n=A^nX_0$$ (17)

と書けることがわかる。 よって、 この行列の $n$ 乗の $A^n$ を行列の対角化などを使って求めれば、 (17) によって一般項 $X_n$ が求まることになるが、 それは少し難しい。 一方で、(15) を 2, 3 節で 考察した単独の (連立でない) 線形同次漸化式に帰着させる方法もある。 ここではそちらの方を説明する。

行列 $A$ の固有方程式を

$$F(\lambda)=\vert\lambda E-A\vert = 0$$

とすると、$F(\lambda)$ は $\lambda^N$ の係数が 1 の $N$ 次式になる。 この $F(\lambda)$ を

$$F(\lambda)=\sum_{j=0}^Nq_j\lambda^j$$ (18)

と書く ($q_N=1$) と、良く知られているようにケーリー・ハミルトンの関係式

$$F(A) = \sum_{j=0}^Nq_jA^j = O$$ (19)

(ただし、$A^0=E$) が成り立つ。 この両辺を右から $A^nX_0$ 倍すると

$$\sum_{j=0}^Nq_jA^{n+j}X_0 = O$$

となるが、(17) よりこれは

$$\sum_{j=0}^Nq_jX_{n+j} = O$$

と書ける。そしてこれは、 $X_{n}$ の成分 $\{x^{(j)}_n\}$ すべてが、同じ線形同次漸化式

$$\sum_{j=0}^Nq_jx_{n+j} = x_{n+N}+q_{N-1}x_{n+N-1}+\cdots+q_0x_n=0$$ (20)

を満たすことを意味している。

なお、この $q_0$ は、$F(\lambda)$ の定数項であるから、

$$q_0=F(0)=\vert-A\vert = (-1)^N\vert A\vert$$

となっている。 よってこれが条件 (4) を満たすことは $\vert A\vert\neq 0$、 すなわち $A$ が正則であることと同値となる。 以下、$A$ は正則であるとして考える。

この場合は、3 節で見たように特性方程式により解が求まる。 (20) の特性方程式は、 (18) より固有方程式 $F(\lambda)=0$ 自体であるから、 つまり $A$ の固有方程式の解である固有値によって (20) の解が求まることになる。

それによる (20) の $N$ 個の一次独立な解を

$$\{\alpha^{(0)}_n\},\ \{\alpha^{(1)}_n\},\ \ldots,\ \{\alpha^{(N-1)}_n\}$$

とし、

$$Y_n=\left[\begin{array}{c}\alpha^{(0)}_n\\ \alpha^{(1)}_n\\ \vdots\\ \alpha^{(N-1)}_n\end{array}\right]$$

とすると、次が言える。

補題 3

$\{\alpha^{(j)}_n\}$ ( $j=0,1,\ldots,N-1$) が一次独立なら $n$ 次元列ベクトル $Y_0$, $Y_1$, ...$Y_{N-1}$ も一次独立。

証明

$Y_0$, $Y_1$, ...$Y_{N-1}$ が一次独立でないとすれば、 $n\times n$ 行列

$$[Y_0\ Y_1\ \cdots\ Y_{N-1}]$$

の行列式の値は 0 となる。よって、この行列の行ベクトル $Z_0$, $Z_1$, ..., $Z_{N-1}$ も一次独立ではないことになる。 ここで、

$$Z_j=[\alpha^{(j)}_0\ \alpha^{(j)}_1\ \cdots \ \alpha^{(j)}_{N-1}]$$

であるから、これらが一次従属ならば、

$$(d_0,d_1,\ldots,d_{N-1})\neq (0,0,\ldots,0)$$ (21)

である定数 $d_j$ に対して、

$$d_0Z_0+d_1Z_1+\cdots+d_{N-1}Z_{N-1}=O$$

と書けることになる。成分で見ればこれは、

$$\sum_{j=0}^{N-1}d_j \alpha^{(j)}_k =d_0\alpha^{(0)}_k+d_1\alpha^{(1)}_k+\cdots+d_{N-1}\alpha^{(N-1)}_k =0$$ (22)

が $k=0,1,\ldots N-1$ に対して成り立つことを意味する。 (20) を考えれば、この (22) は $k\geq N$ に対しても成り立つことになる。 例えば $k=N$ に対しては、

$$\sum_{j=0}^{N-1}d_j a^{(j)}_N = \sum_{j=0}^{N-1}d_j \left... ...m=0}^{N-1}q_m\left(\sum_{j=0}^{N-1}d_j a^{(j)}_m\right) = 0$$

が (22) から言える。以下同様である。 そして (21) と (22) は、 $\{\alpha^{(j)}_n\}$ ( $j=0,1,\ldots,N-1$) が一次従属であることを意味する。

$\{\alpha^{(j)}_n\}$ ( $j=0,1,\ldots,N-1$) は、 (20) の $N$ 個の一次独立な解であるから、 命題 1 によって $X_{n}$ の成分 $\{x^{(k)}_n\}$ はそれらの 一次結合で表される。よって、

$$x^{(k)}_n = \sum_{j=0}^{N-1}c_{k,j}\alpha^{(j)}_n$$

のようになるので、 これにより $X_n$ はこの係数による行列 $C=[c_{k,j}]$ と $Y_n$ により

$$X_n=CY_n\hspace{1zw}(C=[c_{k,j}])$$ (23)

と書けることになる。後は、この係数行列 $C$ を初期値から決めればよい。 すなわち、$C$ を $X_0$ と $A$ を用いて表せばよいことになる。 (23) の $n=0,1,\ldots,N-1$ の式を行列にまとめて書けば、

$$[X_0\ X_1\ \cdots\ X_{N-1}]=C[Y_0\ Y_1\ \cdots\ Y_{N-1}]$$

となるが、補題 3 より 行列 $[Y_0\ Y_1\ \cdots\ Y_{N-1}]$ は正則であり、 また (17) を用いて左辺を書き直せば、結局 $C$ は

$$C=[X_0\ AX_0\ \cdots\ A^{N-1}X_0][Y_0\ Y_1\ \cdots\ Y_{N-1}]^{-1}$$ (24)

と書けることになる。 この (23) と (24) により、 行列 $A$ の $n$ 乗の計算をせずに連立漸化式の解が求められることになる。

例として、今の方法を (14) に適用してみる。 初期値は、題意より $x_0=1$, $y_0=0$ とする。 この場合、$A$ は (16) より、固有方程式は

$$\vert\lambda A-E\vert =\left\vert\begin{array}{cc}\lambda-1/... ...array}\right\vert =(\lambda-1/2)^2-5/4 =\lambda^2-\lambda-1 =0$$

となって、結局フィボナッチ数列の特性方程式と同じになる。 よって、一次独立な二つの解は

$$\lambda_0^n=\left(\frac{1+\sqrt{5}}{2}\right)^n,\hspace{1zw} \lambda_1^n=\left(\frac{1-\sqrt{5}}{2}\right)^n$$

であり、よって

$$x_n=a\lambda_0^n+b\lambda_1^n,\hspace{1zw} y_n=c\lambda_0^n+d\lambda_1^n$$

つまり、

$$\left[\begin{array}{c}x_n\\ y_n\end{array}\right]=\left[\beg... ...ft[\begin{array}{c}\lambda_0^n\\ \lambda_1^n\end{array}\right]$$

と書ける。この係数行列を求めるには、$n=0$, $n=1$ を考えれば、

$$\left[\begin{array}{c}x_0\\ y_0\end{array}\right]=\left[\beg... ...rray}\right]=\left[\begin{array}{c}1/2\\ 1/2\end{array}\right]$$

より、

$$\left[\begin{array}{cc}1&1/2\\ 0&1/2\end{array}\right] =\lef... ...t[\begin{array}{cc}1&\lambda_0\\ 1&\lambda_1\end{array}\right]$$

となるので、

$$\begin{eqnarray*}\left[\begin{array}{cc}a&b\\ c&d\end{array}\right] &=& \left... ...\left[\begin{array}{cc}\sqrt{5}&\sqrt{5}\\ 1&-1\end{array}\right]\end{eqnarray*}$$

より、結局、

$$\left[\begin{array}{c}x_n\\ y_n\end{array}\right] = \frac{1}... ...le \frac{\lambda_0^n-\lambda_1^n}{2\sqrt{5}}\end{array}\right]$$

となる。

$x_n$ は、$x_0=1$, $x_1=1/2$ に対するフィボナッチ数列の解、 $y_n$ は $y_0=0$, $y_1=1/2$ に対するフィボナッチ数列の解となっていて、 これらは 2 節の最後の $a^{(0)}_n$, $a^{(1)}_n$ を用いれば、

$$x_n = a^{(0)}_n+\frac{1}{2}a^{(1)}_n,\hspace{1zw} y_n = \frac{1}{2}a^{(1)}_n$$

と書けることもわかる。

なお、この最後の $y_n$ と $a^{(1)}_n$ ($=$ 元々のフィボナッチ数列 $a_n$) との関係は、(13) からもわかる。すなわち、 (2) および (13) より、

$$a_n = a^{(1)}_n = \frac{1}{\sqrt{5}}(b^{(0)}_n-b^{(1)}_n) = \frac{1}{\sqrt{5}}2y_n\sqrt{5} =2y_n$$

だからである。つまり、元のフィボナッチ数列の値は、 $\lambda_0^n$ の $\sqrt{5}$ の係数である有理数の 2 倍であることになる。

さらに、(9) より、 $a^{(0)}_n=a_{n-1}$ であるから、

$$x_n=a_{n-1}+\frac{1}{2}a_n,\hspace{1zw}y_n=\frac{1}{2}a_n$$

となり、そして $\lambda_0^n = x_n+y_n\sqrt{5}$ は フィボナッチ数列 $a_n$ を用いて

$$\lambda_0^n =\left(\frac{1+\sqrt{5}}{2}\right)^n =\left(a_{n... ...5} =\left(a_{n+1}-\frac{1}{2}a_n\right)+\frac{1}{2}a_n\sqrt{5}$$

と書けることになる。