## Fibonacci数列の美しさ

$F_{n+2}=F_{n+1}+F_{n},\ F_0=1,F_1=1$によって定まる数列をFibonacci数列と呼ぶ．これは数学者であるFibonacciが示した問題から来ている．

この数列は非常に単純な構造をしているが，だからこそ美しい恒等式(identity)がたくさん隠れている．また，整数論の立場から見れば剰余に関する性質，表現の一意性に関する性質など豊かな性質が明らかになっている．ここでは深く立ち入らないが，もし興味のある方は「Zeckendorf表現」「Fibonacci数列の剰余の循環」などと調べてみるといいかもしれない．

さて，今回はFibonacci数列の行列表現を用いて摩訶不思議な恒等式を考えたいと思う．一般に次の恒等式が成り立つ．

$$\pmatrix{
3&6&-3&-1\\
1&0&0&0\\
0&1&0&0\\
0&0&1&0
}^n\pmatrix{
2197&512&125&27\\
512&125&27&8\\
125&27&8&1\\
27&8&1&1
}=\pmatrix{
F_{n+7}^3&F_{n+6}^3&F_{n+5}^3&F_{n+4}^3\\
F_{n+6}^3&F_{n+5}^3&F_{n+4}^3&F_{n+3}^3\\
F_{n+5}^3&F_{n+4}^3&F_{n+3}^3&F_{n+2}^3\\
F_{n+4}^3&F_{n+3}^3&F_{n+2}^3&F_{n+1}^3\\
}
$$

面白いのは$1,8,27,125,512,2197$はそれぞれ$1^3,2^3,3^3,5^3,8^3,13^3$（つまりFibonacci数の3乗！）になっており，また右辺はFibonacci数列の三乗が与えられていることに注意したい．勘のいい方は，初期項$(n=0)$になっていることに気づくかもしれない．

これでは何がなんだかわからないので，もっと簡単なところから始めよう．

一般に次が成り立つ．
$$
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^n =
\begin{pmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1} \\
\end{pmatrix}\cdots(1)
$$
左の行列の由来は，厳密な話はおいておいて，次のように考えると直感的だと思う．

$$
\begin{pmatrix}
F_{n+1} \\
F_{n} \\
\end{pmatrix}
=\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
F_{n} \\
F_{n-1} \\
\end{pmatrix}
$$
これは天下り的に見つけているのではなく，表現行列を求めているに過ぎない．より具体的に言えば，Fibonacci型の漸化式によって定まる部分数列空間において線形シフト写像の表現行列を求めているに他ならない（はず）．
ここで式$(1)$の両辺に$\det$を取れば
$$
(-1)^n=F_{n+1}F_{n-1}-F_n^2
$$
が導かれる．また式$(1)$に$p,q,p+q$を代入することで
$$
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^p \begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^q =
\begin{pmatrix}
F_{p+1} & F_p \\
F_p & F_{p-1} \\
\end{pmatrix}\begin{pmatrix}
F_{q+1} & F_q \\
F_q & F_{q-1} \\
\end{pmatrix}\cdots(2)$$
$$
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^{p+q} =
\begin{pmatrix}
F_{p+q+1} & F_{p+q} \\
F_{p+q} & F_{p+q-1} \\
\end{pmatrix}\cdots(3)
$$
左辺が等しいことから右辺を計算して，比較すればCassiniの恒等式が得られる．
$$F_{p+q-1} = F_p F_q + F_{p-1} F_{q-1}$$

さて，本題の恒等式に移る．以上から得られた知見は行列をうまく扱うことで富んだ恒等式が得られるということだった．ここから先は別の手法を扱う．といっても鮮やかというよりも愚直なものである．

左辺の行列の第一行目を観察すると，次の漸化式が見えてくる．
$$F_{n+4}^3=3F_{n+3}^3+6F_{n+2}^3-3F_{n+1}^3-F_n^3$$

一般にBinetの公式と呼ばれるFibonacci数列の一般項(closed form)を用意する．
$$ F_n = \frac{\phi^n-(-\phi^{-1})^n)}{\sqrt 5} $$
そして，その三乗から
$$F_n^3=\frac{(\phi^3)^n-3(-\phi)^n+3(\phi^{-1})^n-(-\phi^{-3})^n}{5\sqrt5}$$
が得られる．そして，式$(1)$の固有方程式の解を$\phi, \bar{\phi}$とおく．（$\bar{\phi}=\phi^{-1}$が知られている）
天下り的に実験すれば，
$$(x−\phi^3)(x+\phi)(x−\phi^{-1})(x+\phi^{-3})=x^4−3x^3−6x^2+3x+1$$
そして，この恒等式を利用すれば所与の漸化式の係数と一致していることがただちにわかる．ここからは手を動かすことになるが，両辺に$\phi^3,-\phi,\phi^{-1},-\phi^{-3}$を代入すれば，次数下げの道具が手に入るので，あとは指数法則に従って$F_{n+4}^3$などを計算して両辺が一致することを確かめれば十分である．

同様の手法からさらにいくつかの行列表現を得ることができる．しかし，これは線形な関係式の場合にのみ有効な手法で，非線形な関係式を得ることはできない．おそらく，線形代数の言葉を使えば，より精緻に定式化できそうだが，実力不足のため略す．

また別の方法でさらにたくさんの恒等式を示すことができる．Fibonacci数列やまたそれの類似のLucas数列，Chebishev多項式などは母関数，あるいは形式的冪級数(FPS:Formal Power Series)とその閉じた形（closed form）を解析することで結果を得られる．あるいは超幾何級数を用いる方法もある．組み合わせ論と組み合わせても面白い．例えば，一段または二段で階段を上がる回数はFibonacci数と一致することが知られており，これをコンビネーションを用いて表すことで恒等式が得られることも知られている．（この結果は例えばお茶の水女子大学などの入試問題にも採用されているwell-known factである）