フィボナッチ数が現れる問題（7）の解答例を示します。
(７)の解
●n=5の場合
1または3が末尾に現れる数字列の長さは奇数、2または4が末尾に現れる数字列の長さは偶数であることがわかる。
そこで、
1で終わる長さ2m-1の文字列の個数をA(2m-1)
2で終わる長さ2mの文字列の個数をB(2m)
3で終わる長さ2m-1の文字列の個数をC(2m-1)
4で終わる長さ2mの文字列の個数をD(2m)
とすると、つぎの関係式が成り立つ。
1で終わる長さ2m-1の文字列の末尾から2番目の数字は2となることから
A(2m-1) = B(2m-2)
が導ける。
2で終わる長さ2mの文字列の末尾から2番目の数字は1または3となることから
B(2m) = A(2m-1) + C(2m-1)
が導ける。
3で終わる長さ2m-1の文字列の末尾から2番目の数字は2または4となることから
C(2m-1) = B(2m-2) + D(2m-2)
が導ける。
4で終わる長さ2mの文字列の末尾から2番目の数字は3となることから
D(2m) = C(2m-1)
が導ける。
奇数、偶数の長さでまとめると、つぎの関係式が成り立つ。
A(2m-1)+C(2m-1) = B(2m-2)+{B(2m-2)+D(2m-2)}
= {A(2m-3)+C(2m-3)}+{B(2m-2)+D(2m-2)}
B(2m)+D(2m) = {A(2m-1)+C(2m-1)}+C(2m-1)
={A(2m-1)+C(2m-1)}+{B(2m-2)+D(2m-2)}
そこで、
g(2m-1) = A(2m-1) + C(2m-1)
g(2m) = B(2m) + D(2m)
と定義すると、
g(2m-1) = g(2m-3) + g(2m-2) (m≧2)
g(2m) = g(2m-1) + g(2m-2) (m≧2)
g(1)=1, g(2)=1
が導ける。整理すると、
g(n) = g(n-1) + g(n-2) (n≧3)
g(1)=1, g(2)=1
となる。
