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

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

(５)の解

　明らかに、e(1)=2，e(2)=3である。求める部分集合は、要素nを含むものと、含まないものに分類できる。前者の方法がe(n-2)通り、後者の方法がe(n-1)通りである。

したがって、

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

が成り立つ。