4 数列の漸化式の解

数列の漸化式には色々あるが、線形写像によって決まる漸化式、 すなわち連立の 2 項間漸化式

  $$\mbox{\boldmath$x$}_{n+1}=A\mbox{\boldmath$x$}_n\hspace{1zw}\lef... ...}{r}x_{1,n}\\ \vdots\\ x_{m,n}\end{array}\right]\in\mbox{\boldmath$R$}^m\right)$$ (3)

もよく使われる。 例えば、複数の種の個体数の世代毎の変化、 固定回路の複数接続、推移確率など。

また、逆に多項間漸化式を、(3) の ような 2 項間の連立漸化式に直すこともできる。 例えば、フィボナッチ数列として知られる 3 項間の漸化式

$$a_{n+2} = a_{n+1}+a_n$$

は、$b_{n}=a_{n+1}$ とすれば、

$$b_{n+1} = a_{n+2} = a_{n+1}+a_n = a_n + b_n,\hspace{1zw}a_{n+1} = b_n$$

より、

$$\left[\begin{array}{r}a_{n+1}\\ b_{n+1}\end{array}\right] = \left... ...1\\ 1&1\end{array}\right]\left[\begin{array}{r}a_{n}\\ b_{n}\end{array}\right]$$

の連立の 2 項間漸化式になる。

連立の漸化式 (3) から一般項を求めるには、 $A$ が定数行列であれば、形式的には、

  $$\mbox{\boldmath$x$}_n = A^{n}\mbox{\boldmath$x$}_0$$ (4)

と求まるので、行列の $n$ 乗が計算できれば難しくはない。 その行列の $n$ 乗を求めるために、 通常は固有値、固有ベクトルを利用して対角化などを行うわけであるが、 ここでは、実質的には同じであるが、 対角化にはよらずに固有ベクトルを利用して一般項を求める方法を紹介する。

例えば、次のような連立漸化式を考える。

  $$\left\{\begin{array}{ll} a_{n+1} &= \displaystyle \frac{a_n}{2}... ...1zh] b_{n+1} &= \displaystyle \frac{a_n}{4}+\frac{3b_n}{4} \end{array}\right.$$ (5)

この一般項を求めるには、例えば $b_{n}$ を消去して $\{a_n\}$ に 関する 3 項漸化式から求める、という方法もあるが、 ここでは固有ベクトル (左固有ベクトル) を利用する。 (5) を行列化すると、

  $$\mbox{\boldmath$x$}_{n+1}=A\mbox{\boldmath$x$}_n, \hspace{1zw}\... ... [1zh] \displaystyle \frac{1}{4}& \displaystyle \frac{3}{4}\end{array}\right]$$ (6)

となる。$A$ の固有値は、

$$\phi_A(\lambda) = \left\vert\begin{array}{rr}\displaystyle \lamb... ...lambda^2-\frac{5\lambda}{4}+\frac{1}{4} = \frac{1}{4}(\lambda -1)(4\lambda -1)$$

より $\lambda_1 = 1/4$, $\lambda_2 =1$ となり、 $\lambda_1$ に対する左固有ベクトルは $\mbox{\boldmath$q$}_1=[1\ -1]$, $\lambda_2$ に対する左固有ベクトルは $\mbox{\boldmath$q$}_2=[1\ 2]$ が取れる。

この左固有ベクトル $\mbox{\boldmath$q$}_j$ を (6) の 左からかけると、

  $$\mbox{\boldmath$q$}_j\mbox{\boldmath$x$}_{n+1} = \mbox{\boldma... ...{\boldmath$x$}_n=a_n-b_n,\ \mbox{\boldmath$q$}_2\mbox{\boldmath$x$}_n=a_n+2b_n)$$ (7)

のように漸化式がスカラー化され、数列 $\mbox{\boldmath$q$}_j\mbox{\boldmath$x$}_{n}$ が $\lambda_j$ を公比とする等比数列になる。すなわち、

$$\mbox{\boldmath$q$}_1\mbox{\boldmath$x$}_{n} = \frac{1}{4^n}\mbox... ...math$q$}_2\mbox{\boldmath$x$}_{n} = \mbox{\boldmath$q$}_2\mbox{\boldmath$x$}_0$$

となるので、

$$\begin{eqnarray*}\left[\begin{array}{r}\mbox{\boldmath$q$}_1\\ \mbox{\boldmath$q... ...splaystyle \frac{1}{4^n}+2\end{array}\right]\mbox{\boldmath$x$}_0\end{eqnarray*}$$

のように求めることができる。

重要なのは、行列形の線形の漸化式 (6) を、 左固有ベクトルによりスカラーの漸化式 (7) に 変換する部分であり、このように行列をスカラーに変換する 固有ベクトルの使い方がひとつの典型的な利用法である。