フィボナッチ数列の一般項から線形代数の固有値へ

この数列は、$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ \cdots$ と、前の2つを足して次を作るフィボナッチ数列です。数学Bの3項間漸化式の代表的な問題ですが、その解き方の中には、大学で学ぶ線形代数の考え方が隠れています。

まずは高校の方法で解く

漸化式 $a_{n+2}=a_{n+1}+a_n$ の $a_{n+2},\ a_{n+1},\ a_n$ を $x^2,\ x,\ 1$ に置きかえた方程式

を特性方程式といいます。解は

で、解と係数の関係から $\alpha+\beta=1,\ \alpha\beta=-1$ です。

1. 等比数列の形を2つ作る

$\alpha+\beta=1,\ \alpha\beta=-1$ を使うと、漸化式は

と書きかえられます（右辺を展開すると $\beta a_{n+1}-\alpha\beta a_n=\beta a_{n+1}+a_n$、左辺に移すと $a_{n+2}=(\alpha+\beta)a_{n+1}+a_n$ で、もとの漸化式になります）。数列 $\{a_{n+1}-\alpha a_n\}$ は公比 $\beta$ の等比数列で、初項は $a_2-\alpha a_1=1-\alpha=\beta$ なので

$\alpha$ と $\beta$ を入れかえた同じ計算で

2. 2式を引いて $a_{n+1}$ を消す

$\alpha-\beta=\sqrt{5}$ なので

すべての項が整数なのに、一般項には $\sqrt{5}$ が入っています。たとえば $n=3$ を代入すると、$\sqrt{5}$ が打ち消し合って $a_3=2$ になります。

漸化式を行列で書く

ここからが大学数学へのつながりです。隣り合う2項を縦に並べたベクトル $\vec{v}_n=\begin{pmatrix}a_{n+1}\\ a_n\end{pmatrix}$ を考えると、漸化式は

と、1つの行列 $M=\begin{pmatrix}1&1\\ 1&0\end{pmatrix}$ を掛ける形で書けます（上の行が $a_{n+2}=a_{n+1}+a_n$、下の行が $a_{n+1}=a_{n+1}$）。したがって

で、一般項を求めることは「$M$ を何回も掛けた結果を求めること」になります。

特性方程式は「固有値」の方程式

行列 $M$ を掛けても向きが変わらず、長さだけが $\lambda$ 倍になるベクトル $\vec{p}\ (\neq\vec{0})$ を、$M$ の固有ベクトル、その倍率 $\lambda$ を固有値といいます。

$\vec{p}=\begin{pmatrix}x\\ y\end{pmatrix}$ として成分で書くと、$x+y=\lambda x,\ x=\lambda y$ です。2つ目を1つ目に代入すると $\lambda y+y=\lambda^2y$ です。$y=0$ だと $x=\lambda y=0$ となって $\vec{p}=\vec{0}$ になってしまうので $y\neq 0$ で、両辺を $y$ で割ると

となり、固有値の方程式は、高校の特性方程式 $x^2-x-1=0$ とまったく同じ です。固有値は $\alpha,\ \beta$、固有ベクトルはそれぞれ $\begin{pmatrix}\alpha\\ 1\end{pmatrix},\ \begin{pmatrix}\beta\\ 1\end{pmatrix}$ です。

固有ベクトルの方向では、$M$ を $n$ 回掛けても $\alpha^n$ 倍・$\beta^n$ 倍になるだけです。初めのベクトル $\vec{v}_1=\begin{pmatrix}1\\ 1\end{pmatrix}$ を2つの固有ベクトルの和に分けておけば、$M^{n-1}$ を掛けた結果は $\alpha$ の累乗と $\beta$ の累乗の組み合わせになります。高校の一般項に $\alpha^n$ と $\beta^n$ が出てくるのは、このためです。

隣どうしの比は α に近づく

$|\beta|=0.618\cdots<1$ なので、$n$ が大きくなると $\beta^n$ は $0$ に近づきます。したがって $a_n$ はほぼ $\dfrac{\alpha^n}{\sqrt{5}}$ となり、隣どうしの比は

に近づきます。この値は黄金比と呼ばれる数です。

線形代数では、何回も掛けたときにいちばん効いてくるのは、絶対値が最大の固有値 だと考えます。フィボナッチ数列では、それが $\alpha$ です。