問題
，， によって定義される数列をフィボナッチ数列といい，その一般項は
で与えられる。必要ならばこの事実を用いて，次の問いに答えよ。
各桁の数字が0か1であるような自然数の列 を次の規則により定める。
(i)
(ii) のある桁の数字が0ならばを1で置き換え，が1ならばを'10'で置き換える。の各桁ごとにこのような置き換えを行って得られる自然数をとする。
たとえば，，，，，，となる。
(1) の桁数を求めよ。
(2) の中に'01'という数字の配列が現れる回数を求めよ。
方針
置換規則をそのまま追うと， という連結関係が得られる。これにより桁数 はフィボナッチ型の漸化式を満たす。(2)では，0は1から作られ，この列には が現れないことを使う。0の個数を とすると であり，末尾が0である偶数番だけ を作らない0が1つある。別解として，連結 の境目で が増えるかを調べる漸化式でも求められる。
解答
(1)
置換規則から が成り立つ。実際， は の各桁を置換して得られ，さらにその各桁を置換すると，前半に ，後半に が続く形になる。
したがって桁数 は を満たす。また である。フィボナッチ数列 と比べると である。
(2)
まず に含まれる0の個数を とする。置換で0が生じるのは，もとの桁が1のときだけである。したがって， に含まれる0の個数は に含まれる1の個数に等しいので である。初めの値を調べると ， であり，また と から が成り立つ。
次に，この列には が現れないことを確認する。置換規則では は に変わり， は に変わるので，置換の内部で は生じない。また連結関係 の境目でも，末尾と先頭を見れば は生じない。
したがって， 内の0は，末尾にある場合を除いて，必ず直後に1を伴い， を1回作る。さらに の末尾は， が偶数のとき0， が奇数のとき1である。実際，末尾は の末尾と交互に変わる。
よって であり， について
である。
別解。連結関係から直接 の漸化式を作ってもよい。 なので， は 内部のもの， 内部のもの，そして境目でできるものに分かれる。境目で ができるのは， の末尾が0で の先頭が1のとき，すなわち が偶数のときである。よって
となる。初期値 から計算しても，上の式と同じ結果が得られる。