小学6　算数の問題です。

フィボナッチ数列じゃないですか。小学校の問題じゃないでしょ。

と思ったら、「ネタ・ジョーク」でしたね。


とはいえ、ネタにマジレス。

詳しくは、n枚の場合にa(n)通り（普通は(n)と書かずに添字にする）とすると、

n(≧2)のときは、最後の葉っぱに着地する場合とジャンプする場合があり、前者については最初の(n-1)枚を着地するかジャンプするかを考えればよいのでa(n-1)通りで、後者の場合はその1つ前の葉っぱに着地せざるを得ないので、残りの(n-2)枚について考えればいいのでa(n-2)通りとなり、合わせると
a(n)=a(n-1)+a(n-2)

なおa(0)はまっすぐ飛び越えるだけなのでa(0)=1
a(1)は1枚の葉っぱに着地すると飛び越えるかなのでa(1)=2


以上より、n=0から順次
1, 2, 3, 5 (n=3), 8, 13, 21, 34, 55 (n=8), …, 17711 (n=20), …
となる。

強いてnの式で書くなら
φ=(1+√5)/2
として
a(n)={φ^(n+1)-(-φ)^(-n-1)}/√5
となる。

ジャンプというのをｊとしていますが、パス（上を飛び越える）意味でｐのほうがわかりやすいですね。
ついでに、葉っぱは一列に並んでおり、戻ることはない（ルートは１本しかない）ようですね。
１２３２３２３２というような進み方はしないわけだ。

それなら、葉っぱに、１、２とそれぞれ名前をつけずとも、着地のｔですみます。
３枚の葉っぱ問題は
ｔｔｔ　（着地・着地・着地）
ｐｔｔ　（とびこえ・着地・着地）
ｔｐｔ
ｔｔｐ
ｐｔｐ
の５通りに書き換えられます。
　
　
これを８枚にしたなら、

ｔｔｔｔｔｔｔｔ　このタイプをｐゼロ個ルートと名付けます
ｐｔｔｔｔｔｔｔ　このタイプのをｐ１個ルートとなづけ、８種類あります。
ｐｔｐｔｔｔｔｔ　このタイプのをｐ２個ルートとなづけます。
　
というようにｐの数が４になるまでいちいちかぞえてみましょう。
ｐが５になるとどこかでｐが二つ並んで連続飛び越えになるのでアウトです。

ｐ２個ルートの場合は、28通り（高校生なら8c2といえばわかる）
このうちpが2回連続になる場合は７通り　あるのでさしひいて２１通り
そういった形で簡略化できます。
　
ｐが３個になったら、全とおりのとびこえから、ｐ２個連続と、ｐ３個連続を差し引きます。
　

ｐが２個いじょうあるルートの簡単な計算方法をみつけたら、あとはいくつ増えてもおなじことです。
８枚なら時間は少々かかりますがコンピューターでやるほど難しくはありません。
小学生が大きな紙にかきこみながらやれば１５分くらいで出来ます。
２０枚なら確率統計（ｃというのはコンビネーション）を習った高校生ならわりと速くできます。
小学生にはよほどがんばりのある子でないと、２０枚は無理かもしれません。答えはざっと考えても２００ルートを越えます。４０００枚以上のはっぱ（ｐやｔ）を全部まちがえずに描くのは大変ですからね。

途中まで来て、次の葉っぱに移るときを考えます。

今、葉っぱを踏んでいるのであれば、次の葉っぱは、飛び越えても、踏んでも良い。
なので、今、葉っぱを踏んでいる状態になる組み合わせの数を Ｎo としたら、次に進む組み合わせは、Ｎo×2 通りあります。

今、葉っぱを飛び越えているのであれば、次の葉っぱは、踏むしかない。
そこまでの組み合わせの数を Ｎj としたら、次に進む組み合わせは、Ｎj 通りです。

ここまでの組み合わせは、今踏んでるか、飛び越えているかの合計で、Ｎo＋Ｎj です。
次の葉っぱまで行く、つまり、もう一枚増えた場合には、2 Ｎo ＋ Ｎj 通りです。

これを、表に整理してみます。



漸化式という言葉は使っていませんが、考え方を理解、もしくは思いつくことができないと厳しい感じですね。