フィボナッチ数列の問題の質問です

フィボナッチ数列の問題の解説をお願いします。問題集の問題なのですが、解答を読んでもさっぱりわかりません。

問題　階段を上るのに一段ずつでも二段ずつでもよいし、また、一段と二段をまぜてのぼってもよいものとする。ｎ段の階段をこのようにしてのぼる全ての方法の数をａn（ｎ≧３）とｐするとき、anをan-1とan-2で表せ。

また別の問題です。

問題　a1＝１,a2＝１,　an＝an-1＋an-2 （n=3,4,・・・・）で定義される数列｛an｝の一般項を求めよ。

という問題です。よろしくお願いします。

No.3 ベストアンサー 回答者： carvelo 回答日時： 2009/04/11 23:10

n段の階段を上る上り方には次の２通りが考えられます

(1)n-1段目まで上り（ここまででa_(n-1)通りの上り方がある）、それから更に１段上る
(2)n-2段目まで上り（ここまででa_(n-2)通りの上り方がある）、それから更に２段を１段抜かしで上る

(1)のように上る上り方は、１段ずつ上るしかないのでa_(n-1)通りです。(2)については、１段ずつと２段ずつがあり得るから…、と考えがちですが、そこから１段上ったら(1)の場合の一部になりますので、２段ずつ上る場合だけを考えます。従って、この場合の上り方はa_(n-2)通りです。
したがって、
a_n=a_(n-1)+a_(n-2)
となります。ちなみに、この場合a_1=1、a_2=2ですからフィボナッチではないですね

次の問題については、フィボナッチ数列の漸化式の解き方くらい調べればいろいろ出てくると思うので、解き方のもとになる考え方を
まず、何か数列{b_n}があって
b_n=rb_(n-1)
という形になれば、それは公比rの等比数列と判断でき、簡単に一般項が求まります。多くの場合、漸化式はこの形に持ち込むことになります。今回の場合、b_nとして
b_n=a_n-αa_(n-1)
の形を想定しましょう。すると、目標の形は
a_n-αa_(n-1)=β{a_(n-1)-αa_(n-2)}
です。これを整理すると
a_n-(α+β)a_(n-1)+αβa_(n-2)=0
さて、α、βを求めるのにはどうすれば良いかを考えるわけですが、ここで「二次方程式の解と係数の関係」にぴんと来れば簡単でしょう。

この回答へのお礼

よっくわかりました。
ありがとうございました＾＾

お礼日時：2009/04/12 19:33

No.2 回答者： osamuy 回答日時： 2009/04/11 23:02

n段の階段を昇るには、

1)n-1段から1歩1段で昇る。
2)n-2段から2段飛び1歩で昇る。

――ってのを式にすれば良いかと。
実際に数えてみると、こんな感じ：

[1][11 2][111 21 12][1111 211 121 112 22]

No.1 回答者： owata-www 回答日時： 2009/04/11 22:58

前半

n段目に行くためには
最後が１段→その前がn-1段目
最後が２段→その前がn-2段目
なので

後半
普通の三項間の漸化式の問題です
http://shibuya.cool.ne.jp/takaren/main/etc/math/ …