フィボナッチ数が現れる問題（４）の解

フィボナッチ数が現れる問題（４）の解答例を示します。

(４)の解

　明らかに、d(1)=2，d(2)=3である。求める方法は、最後が+となるものと最後が+-となるものに分類できる。前者の方法がd(n-1)通り、後者の方法 がd(n-2)通りである。

したがって、

　　d(n)= d(n-1)+ d(n-2)　 (n≧3)

が成り立つ。