階段を1回に1段か2段しか登れない。
5段の階段を登る登り方は何通りあるか。
【解】
n段の階段の登り方がP[n]通りあるとする。
P[1]=1, P[2]=2
n+2段の階段を登る。
①最初に1段登る→残りn+1段→P[n+1]
②最初に2段登る→残りn段→P[n]
よって、
P[n+2]=P[n+1]+P[n]
P[1]=1
P[2]=2
P[3]=P[2]+P[1]=2+1=3
P[4]=P[3]+P[2]=3+2=5
P[5]=P[4]+P[3]=5+3=8
【フィボナッチ数】
1202年に、イタリアの数学者レオナルド・フィボナッチが発行した『算盤の書』(Liber Abaci) に記載されたことで「フィボナッチ数」と呼ばれている。
F[0]=0, F[1]=1
n≧0で、F[n+2]=F[n+1]+F[n]
で定義される数列{F[n]}を「フィボナッチ数列」といい、出てくる数をフィボナッチ数という。
第0～20項の値は次の通りである：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
※ P[n]=F[n+1]である。
レオナルド・フィボナッチは次の問題を考案した。
*************************************
1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
兎が死ぬことはない。
この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか？
************************************
【今回の問題】
階段を1回に1段か2段か3段しか登れない。
7段の階段を登る登り方は何通りあるか。
