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

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

(３)の解

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

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

が成り立つ。