フィボナッチ数
Wikiより
兎の問題
レオナルド・フィボナッチは次の問題を考案した
1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
兎が死ぬことはない。
この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか？
これでなぜフィボナッチ数が導かれるのかがどうも良く分からない
ネットから
nか月目のフィボナッチをF_n とする。
0か月目
ひとつがいの兎が生まれた ◯で表す
F_0=1
◯
1か月目
ひとつがいが生き続けるが子どもを産む力はない◯で表す
F_1=1
◯
として
F_(n+2)=F_(n+1)+F_n
という漸化式を導いてみよう
２か月目
0か月目に生まれたひとつがいが子どもを産む力を持って(●で表す)
ひとつがいを生む
●+◯ つがい数は2 だから F_2=2
３か月目
２か月目のつがいは生き続ける (●+◯)
このうち●が◯を新たに産むから
(●+◯)+◯ となって、つがいは3 だから F_3=3
したがって
F _3=2+1=F_2+F_1
が成り立つ
※ここあとで訂正するかも？
４か月目
３か月目の(●◯)◯は生き残っていて
このうちの２か月目の(●◯)は子どもが産めるから
３か月目の(●◯)◯は(●●)◯になった
(●●)は子どもを産むので
４か月目のつがいは◯◯だけ増えて
(●●)◯+◯◯
したがって
F_4=3＋2=F_3+F_2
----------------------------
こうしてnか月目のつがいは
子どもを産めるつがいとそうでないつがいが混じっている
nか月めのつがい(●●●----●◯◯----◯)
この数はF_n である (黒白合わせて)
(n+1)か月目のつがいはnか月目のつがいがそっくり生き残っていて、
新しく生まれたつがいの分だけ増えている
(●●●----●◯◯----◯)+◯◯--◯
nか月め 新しく増えた
(n+2)か月目には上の◯で表されているつがいは子どもを産む力がつくので
F_n の数だけ子どもを産むので◯は●で表され
(●●●----●◯◯----◯)は(●●●----●●●----●)となる
すなわち(n+1)か月めのつがい
(●●●----●◯◯----◯)◯◯--◯ は
これが●になる
(●●●----●●●----●)◯◯--◯ と表される
したがって(n+2)か月めは
(n+1)か月めのつがい(●と◯が混じっている) に
新たに
F_nのつがいたち(●●●----●●●----●)が産んだつがい(◯◯◯----◯◯◯----◯)が加わる
(●●●----●●●----●)◯◯--◯ + (◯◯◯----◯◯◯----◯)
F_(n+2)=F_(n+1)+(新しく生まれたつがい)
ここで「新しく生まれたつがい」はF_(n+1)の中の
子どもを産めるつがいが産んだつがいでその数は
２か月前から生き続けたつがいたちである
以上から
F_(n+2)=F_(n+1)+F_n
もう少し簡潔な説明が出来そう
※訂正の必要がありそう...
終わり
