バイナリ列に現れるフィボナッチ数
フィボナッチ数を以下で定義する．
\begin{align}
F_0&\triangleq 0,\ F_1\triangleq 1,\\
F_n&\triangleq F_{n-1}+F_{n-2}\qquad(n\geq 2).
\end{align}
フィボナッチ数は小さい方から順に
$(F_0,F_1,F_2,\ldots)=(0,1,1,2,3,5,8,13,21,\ldots)$
である．
バイナリ列にはフィボナッチ数が隠れている．
例えば，長さ$n$のバイナリ列$w\in\{0,1\}^n$のうち，$1$が連続しないものの数はフィボナッチ数$F_{n+2}$であることが知られている [1]．
ここでは，これとは別の方法でバイナリ列を数えるとフィボナッチ数が現れることを紹介する．
連続する$1$の長さを並べる写像$f$
バイナリ列$w$の中で$1$が連続する部分を，$1$のクラスターと呼ぶ．$1$のクラスターの大きさを順番に並べた列を作る写像を定義する．
バイナリ列$w$を
\begin{align}
w=0^{a_1}1^{b_1}0^{a_2}1^{b_2}\cdots 0^{a_r}1^{b_r}
\end{align}
と書いたとする．但し$a_1,b_r$は非負整数，それ以外の$a_i,b_i$は正の整数とする．
このとき，$b_r>0$ならば
$f(w)\triangleq(b_1,\ldots,b_r)$，
$b_r=0$ならば
$f(w)\triangleq(b_1,\ldots,b_{r-1})$
と定義する．
$f(0010111011001)=(1,3,2,1),$
$f(111010)=(3,1)$,
$f(111)=(3)$,
$f(0000)=()$
最後の右辺は空列である．
集合$\mathcal{F}_n$を$\mathcal{F}_n\triangleq f(\{0,1\}^{n-2})=\{f(w)\mid w\in\{0,1\}^{n-2}\}$と定義する．
つまり，$\mathcal{F}_n$は，長さ$n-2$のバイナリ列の中で連続する$1$がとりうる並び方の集合である．
$f(000)=(),f(001)=(1),f(010)=(1),f(100)=(1),$
$f(011)=(2),f(101)=(1,1),f(110)=(2),f(111)=(3)$
なので，
$\mathcal{F}_5=\{(),(1),(2),(1,1),(3)\}$
主張
以下が成り立つ．
$|\mathcal{F}_n|=F_n$.
長さ$n-2$のバイナリ列の集合は，以下の三つに分割される．
場合1. バイナリ列に$1$のクラスターがあるならば，最初の$1$のクラスターの大きさが$2$以上であるもの．（ここには$0^{n-2}$も含まれる．）
場合2. バイナリ列が$10$で始まるもの．
場合3. それ以外のもの．つまり，バイナリ列が$0$で始まり，かつ，$1$のクラスターがあり，かつ，最初の$1$のクラスターの大きさが$1$であるもの．
そのようなものの集合をそれぞれ，$S_1,S_2,S_3$としておく．
するとまず，
\begin{align}
|f(S_1)|=|\mathcal{F}_{n-1}|,\\
|f(S_2)|=|\mathcal{F}_{n-2}|,\\
f(S_1)\cap f(S_2)=\emptyset
\end{align}
である．
なぜならば，$S_1$の元は，長さ$n-3$のバイナリ列の最初の$1$のクラスターをひとつ大きくすることで得られ，$S_2$の元は長さ$n-4$のバイナリ列の先頭に$10$をつけることで得られるからである．
そして次に
$f(S_3)\subseteq f(S_2)$
である．
なぜならば，$S_3$に属するバイナリ列は
$w=0^{a_1}10^{a_2}\cdots\qquad (a_1,a_2>0)$
という形をしているが，それを
$w'=10^{a_1+a_2}\cdots$
に変えれば，$w'\in S_2, f(w)=f(w')$となるからである．
以上から，
\begin{align}
|\mathcal{F}_n|&=|f(S_1)\cup f(S_2)\cup f(S_3)|\\
&=|f(S_1)|+|f(S_2)|\\
&=|\mathcal{F}_{n-1}|+|\mathcal{F}_{n-2}|.
\end{align}