どなたかこの問題を教えてください。おねがいしますm()m

■問題1

・ 0と1からなる、長さがnの系列で、0が連続していないものの数をa^nとする。
<例>01101011010

これの漸化式は、 a^n ＝ a^n-1 + a^n-2 である。
何故こうなるのかを求めよ。

[ヒント]一番最後が０、１の数を数えてみると見えてくる？

■問題2

・あるグラフがあるとする。
　そのグラフがハミルトングラフでないことを「次数が2の頂点」という言葉を用いて、説明せよ。