フィボナッチ数列(Fibonacci numbers)の行列表現と一般項

フィボナッチ数列(Fibonacci numbers)の行列表現

フィボナッチ数列 $$\begin{array}{r}{a}_{n+1}=a_n+a_{n-1}\cdots \mathrm{た}\mathrm{だ}\mathrm{し}{a}_1=1,a_2=1\end{array}$$ これを行列で表現すると以下となる． $$\begin{array}{rcl}\left(\begin{array}{c}{a}_{n+1}\\ a_n\end{array}\right)& =& \left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left(\begin{array}{c}{a}_n\\ a_{n-1}\end{array}\right)\\ {\overrightarrow{a}}_{(n+1),n}& =& \mathrm{A}{\overrightarrow{a}}_{n,(n-1)}\end{array}$$

フィボナッチ数列の一般項

${\overrightarrow{a}}_{n,(n-1)}$を$\mathrm{A}$の固有ベクトル${\overrightarrow{x}}_{1,2}$を用い表せれば， 上式は対応する固有値${\lambda }_{1,2}$を用いて以下のように表すことができる． $$\begin{array}{rcl}{\overrightarrow{a}}_{(n+1),n}& =& \mathrm{A}{\overrightarrow{a}}_{n,(n-1)}\\ & =& \mathrm{A}(C_1{\overrightarrow{x}}_1+C_2{\overrightarrow{x}}_2)\cdots C_1,C_2\mathrm{は}\mathrm{定}\mathrm{数}\\ & =& C_1\mathrm{A}{\overrightarrow{x}}_1+C_2\mathrm{A}{\overrightarrow{x}}_2\\ & =& C_1{\lambda }_1{\overrightarrow{x}}_1+C_2{\lambda }_2{\overrightarrow{x}}_2\cdots \mathrm{A}\overrightarrow{x}=\lambda \overrightarrow{x}\cdots \mathrm{固}\mathrm{有}\mathrm{値}\mathrm{・}\mathrm{固}\mathrm{有}\mathrm{ベ}\mathrm{ク}\mathrm{ト}\mathrm{ル}\mathrm{の}\mathrm{定}\mathrm{義}\end{array}$$ またこれを繰り返すことで一般項として以下のように表せることになる． $$\begin{array}{rcl}{\overrightarrow{a}}_{(n+1),n}& =& {\mathrm{A}}^n{\overrightarrow{a}}_{init}\cdots {\overrightarrow{a}}_{init}\mathrm{は}\mathrm{固}\mathrm{有}\mathrm{ベ}\mathrm{ク}\mathrm{ト}\mathrm{ル}\mathrm{の}\mathrm{和}\mathrm{で}\mathrm{表}\mathrm{さ}\mathrm{れ}\mathrm{た}\mathrm{初}\mathrm{期}\mathrm{条}\mathrm{件}\mathrm{を}\mathrm{満}\mathrm{た}\mathrm{す}\mathrm{定}\mathrm{数}{C}_1,C_2\mathrm{を}\mathrm{含}\mathrm{む}\mathrm{ベ}\mathrm{ク}\mathrm{ト}\mathrm{ル}\\ & =& {\mathrm{A}}^n(C_{{\overrightarrow{a}}_{init}1}{\overrightarrow{x}}_1+C_{{\overrightarrow{a}}_{init}2}{\overrightarrow{x}}_2)\\ & =& C_{{\overrightarrow{a}}_{init}1}{\mathrm{A}}^n{\overrightarrow{x}}_1+C_{{\overrightarrow{a}}_{init}2}{\mathrm{A}}^n{\overrightarrow{x}}_2\\ & =& C_{{\overrightarrow{a}}_{init}1}{\lambda }_1^n{\overrightarrow{x}}_1+C_{{\overrightarrow{a}}_{init}2}{\lambda }_2^n{\overrightarrow{x}}_2\end{array}$$ そこでまず$\mathrm{A}$の固有値を求める． $$\begin{array}{rcl}|\mathrm{A}-\lambda \mathrm{E}|& =& 0\\ |\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]-\lambda \left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]|& =& \\ \left|\begin{array}{cc}1-\lambda & 1\\ 1& -\lambda \end{array}\right|& =& \\ (1-\lambda )(-\lambda )-1& =& \\ {\lambda }^2-\lambda -1& =& \\ \lambda & =& \frac{-(-1)\pm \sqrt{(-1{)}^2-4(1)(-1)}}{2(1)}\\ & =& \frac{1\pm \sqrt{5}}{2}\\ {\lambda }_1,{\lambda }_2& =& \frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}\cdots \mathrm{こ}\mathrm{こ}\mathrm{で}\mathrm{は}{\lambda }_1>{\lambda }_2\mathrm{と}\mathrm{す}\mathrm{る}．\end{array}$$ ${\lambda }_1$に対応する固有値ベクトル$\overrightarrow{x_1}$を求める． $$\begin{array}{rcl}(\mathrm{A}-{\lambda }_1\mathrm{E})\overrightarrow{x_1}& =& \overrightarrow{0}\\ \left[\begin{array}{cc}1-{\lambda }_1& 1\\ 1& -{\lambda }_1\end{array}\right]\left(\begin{array}{c}{x}_{11}\\ x_{12}\end{array}\right)& =& \left(\begin{array}{c}0\\ 0\end{array}\right)\\ \left[\begin{array}{cc}1-\frac{1+\sqrt{5}}{2}& 1\\ 1& -\frac{1+\sqrt{5}}{2}\end{array}\right]\left(\begin{array}{c}{x}_{11}\\ x_{12}\end{array}\right)& =& \left(\begin{array}{c}0\\ 0\end{array}\right)\\ \left[\begin{array}{cc}\frac{1-\sqrt{5}}{2}& 1\\ 1& -\frac{1+\sqrt{5}}{2}\end{array}\right]\left(\begin{array}{c}{x}_{11}\\ x_{12}\end{array}\right)& =& \left(\begin{array}{c}0\\ 0\end{array}\right)\end{array}$$ $$\{\begin{array}{rlr}\frac{1-\sqrt{5}}{2}{x}_{11}+x_{12}& =& 0\\ x_{11}-\frac{1+\sqrt{5}}{2}{x}_{12}& =& 0\end{array}$$ $$\begin{array}{rcl}{x}_{11}& =& \frac{1+\sqrt{5}}{2}{x}_{12}\\ {\overrightarrow{x}}_1& =& t\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\ 1\end{array}\right)\cdots t:\mathrm{任}\mathrm{意}\mathrm{の}\mathrm{実}\mathrm{数}\end{array}$$ 同様に${\lambda }_2$に対応する固有値ベクトル$\overrightarrow{x_2}$を求める． $$\begin{array}{rcl}(\mathrm{A}-{\lambda }_2\mathrm{E})\overrightarrow{x_2}& =& \overrightarrow{0}\\ \left[\begin{array}{cc}1-{\lambda }_2& 1\\ 1& -{\lambda }_2\end{array}\right]\left(\begin{array}{c}{x}_{21}\\ x_{22}\end{array}\right)& =& \left(\begin{array}{c}0\\ 0\end{array}\right)\\ \left[\begin{array}{cc}1-\frac{1-\sqrt{5}}{2}& 1\\ 1& -\frac{1-\sqrt{5}}{2}\end{array}\right]\left(\begin{array}{c}{x}_{21}\\ x_{22}\end{array}\right)& =& \left(\begin{array}{c}0\\ 0\end{array}\right)\\ \left[\begin{array}{cc}\frac{1+\sqrt{5}}{2}& 1\\ 1& -\frac{1-\sqrt{5}}{2}\end{array}\right]\left(\begin{array}{c}{x}_{21}\\ x_{22}\end{array}\right)& =& \left(\begin{array}{c}0\\ 0\end{array}\right)\end{array}$$ $$\{\begin{array}{rlr}\frac{1+\sqrt{5}}{2}{x}_{21}+x_{22}& =& 0\\ x_{21}-\frac{1-\sqrt{5}}{2}{x}_{22}& =& 0\end{array}$$ $$\begin{array}{rcl}{x}_{21}& =& \frac{1-\sqrt{5}}{2}{x}_{22}\\ {\overrightarrow{x}}_2& =& t\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\ 1\end{array}\right)\cdots t:\mathrm{任}\mathrm{意}\mathrm{の}\mathrm{実}\mathrm{数}\end{array}$$ よって前述の表現は以下のように書き換えられる． $$\begin{array}{rcl}\left(\begin{array}{c}{a}_{n+1}\\ a_n\end{array}\right)& =& C_{{\overrightarrow{a}}_{init}1}{\lambda }_1^n{\overrightarrow{x}}_1+C_{{\overrightarrow{a}}_{init}2}{\lambda }_2^n{\overrightarrow{x}}_2\\ & =& C_{{\overrightarrow{a}}_{init}1}{\left(\frac{1+\sqrt{5}}{2}\right)}^n\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\ 1\end{array}\right)+C_{{\overrightarrow{a}}_{init}2}{\left(\frac{1-\sqrt{5}}{2}\right)}^n\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\ 1\end{array}\right)\end{array}$$ $n=1$の時，$a_n=a_1=1,a_{n+1}=a_{1+1}=a_2=1$なので，ここから$C_{{\overrightarrow{a}}_{init}1},C_{{\overrightarrow{a}}_{init}2}$を求める． $$\begin{array}{rcl}{C}_{{\overrightarrow{a}}_{init}1}{\left(\frac{1+\sqrt{5}}{2}\right)}^1\left(\begin{array}{c}\frac{1+\sqrt{5}}{2}\\ 1\end{array}\right)+C_{{\overrightarrow{a}}_{init}2}{\left(\frac{1-\sqrt{5}}{2}\right)}^1\left(\begin{array}{c}\frac{1-\sqrt{5}}{2}\\ 1\end{array}\right)& =& \left(\begin{array}{c}1\\ 1\end{array}\right)\end{array}$$ 簡単のために以下のようにひとまず置き直す． $$\begin{array}{rcl}{C}_1& :& C_{{\overrightarrow{a}}_{init}1}\\ C_2& :& C_{{\overrightarrow{a}}_{init}2}\\ {\alpha }_1& :& \frac{1+\sqrt{5}}{2}\\ {\alpha }_2& :& \frac{1-\sqrt{5}}{2}\end{array}$$ 上記で書き直す． $$\begin{array}{r}{C}_1{\left({\lambda }_1\right)}^1\left(\begin{array}{c}{\alpha }_1\\ 1\end{array}\right)+C_2{\left({\lambda }_2\right)}^1\left(\begin{array}{c}{\alpha }_2\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 1\end{array}\right)\end{array}$$ 行ごとに書き出すと以下のような連立方程式となる． $$\{\begin{array}{rlr}{C}_1{\lambda }_1{\alpha }_1+C_2{\lambda }_2{\alpha }_2& =& 1\\ C_1{\lambda }_1+C_2{\lambda }_2& =& 1\end{array}$$ $C_1$について解く． $$\begin{array}{rcl}{C}_1{\lambda }_1{\alpha }_2+C_2{\lambda }_2{\alpha }_2& =& {\alpha }_2\cdots \mathrm{連}\mathrm{立}\mathrm{方}\mathrm{程}\mathrm{式}\mathrm{の}\mathrm{二}\mathrm{つ}\mathrm{目}\mathrm{の}\mathrm{式}\mathrm{に}{\alpha }_2\mathrm{を}\mathrm{掛}\mathrm{け}\mathrm{る}\\ (C_1{\lambda }_1{\alpha }_1+C_2{\lambda }_2{\alpha }_2)-(C_1{\lambda }_1{\alpha }_2+C_2{\lambda }_2{\alpha }_2)& =& \left(1\right)-\left({\alpha }_2\right)\cdots \mathrm{連}\mathrm{立}\mathrm{方}\mathrm{程}\mathrm{式}\mathrm{の}\mathrm{一}\mathrm{つ}\mathrm{目}\mathrm{の}\mathrm{式}\mathrm{よ}\mathrm{り}\mathrm{上}\mathrm{式}\mathrm{を}\mathrm{引}\mathrm{く}\\ C_1{\lambda }_1{\alpha }_1-C_1{\lambda }_1{\alpha }_2& =& 1-{\alpha }_2\\ C_1{\lambda }_1({\alpha }_1-{\alpha }_2)& =& 1-{\alpha }_2\\ C_1{\lambda }_1({\alpha }_1-{\alpha }_2)& =& {\alpha }_1\cdots 1-{\alpha }_2=1-\frac{1-\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}={\alpha }_1\\ C_1& =& \frac{{\alpha }_1}{{\lambda }_1({\alpha }_1-{\alpha }_2)}=\frac{\frac{1+\sqrt{5}}{2}}{\frac{1+\sqrt{5}}{2}(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2})}\\ & =& \frac{1}{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}=\frac{1}{\frac{2\sqrt{5}}{2}}=\frac{1}{\sqrt{5}}\end{array}$$ $C_2$について解く． $$\begin{array}{rcl}{C}_1{\lambda }_1{\alpha }_1+C_2{\lambda }_2{\alpha }_1& =& {\alpha }_1\cdots \mathrm{連}\mathrm{立}\mathrm{方}\mathrm{程}\mathrm{式}\mathrm{の}\mathrm{二}\mathrm{つ}\mathrm{目}\mathrm{の}\mathrm{式}\mathrm{に}{\alpha }_1\mathrm{を}\mathrm{掛}\mathrm{け}\mathrm{る}\\ (C_1{\lambda }_1{\alpha }_1+C_2{\lambda }_2{\alpha }_2)-(C_1{\lambda }_1{\alpha }_1+C_2{\lambda }_2{\alpha }_1)& =& \left(1\right)-\left({\alpha }_1\right)\cdots \mathrm{連}\mathrm{立}\mathrm{方}\mathrm{程}\mathrm{式}\mathrm{の}\mathrm{一}\mathrm{つ}\mathrm{目}\mathrm{の}\mathrm{式}\mathrm{よ}\mathrm{り}\mathrm{上}\mathrm{式}\mathrm{を}\mathrm{引}\mathrm{く}\\ C_2{\lambda }_2{\alpha }_2-C_2{\lambda }_2{\alpha }_1& =& 1-{\alpha }_1\\ C_2{\lambda }_2({\alpha }_2-{\alpha }_1)& =& 1-{\alpha }_1\\ C_2{\lambda }_2({\alpha }_2-{\alpha }_1)& =& {\alpha }_2\cdots 1-{\alpha }_1=1-\frac{1+\sqrt{5}}{2}=\frac{1-\sqrt{5}}{2}={\alpha }_2\\ C_2& =& \frac{{\alpha }_2}{{\lambda }_2({\alpha }_2-{\alpha }_1)}=\frac{\frac{1-\sqrt{5}}{2}}{\frac{1-\sqrt{5}}{2}(\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2})}\\ & =& \frac{1}{\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}}=\frac{1}{-\frac{2\sqrt{5}}{2}}=-\frac{1}{\sqrt{5}}\end{array}$$ 以上よりフィボナッチ数列の一般項$a_n$は以下のように表すことができた． $$\begin{array}{rcl}{a}_n& =& C_1{\lambda }_1^n+C_2{\lambda }_2^n\\ & =& \frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^n\end{array}$$ $a_{n+1}$側の式は以下のようになり, $n+1$を改めて$n$と置き直せば上式と同じになる． $$\begin{array}{rcl}{a}_{n+1}& =& C_1{\lambda }_1^n{\alpha }_1+C_2{\lambda }_2^n{\alpha }_2\\ & =& \frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n\frac{1+\sqrt{5}}{2}-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^n\frac{1-\sqrt{5}}{2}\\ & =& \frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+1}\end{array}$$