漸化式を用いた場合の数

赤、青、黄の３色を用いて、横一列のｎ個のマスを隣り合うマスは異なる色になるようにする。使わない色があってもよい。両端が同じ色の場合の数をａｎとし、両端の色がことなるときをｂｎとする。
ａｎ、ｂｎをｎで表せ。

漸化式を作って、それから一般項を求めるのだということは、わかるが、いざ漸化式を作るとなるとどう考えたらよいのか、分かりません。
よろしくお願いします。

No.2 ベストアンサー 回答者： Kules 回答日時： 2010/04/19 12:51

漸化式を自分で作る場合は、

「如何にしてa_(n+1)をa_nで表わすか(無理ならa_(n-1)も使う)」
ということになります。
a_n,b_nは条件を満たすように並んでるマスなので、
a_(n+1),b_(n+1)をa_n,b_nでどうにか表してやればいいということになります。
a_n,b_nからa_(n+1),b_(n+1)を作るには、さらに１マス足すだけです。
例えばb_nにもう１マス足した時、a_(n+1)になるか？b_(n+1)になるか？
などを考えていけば答えは出ると思います。

ヒントとしては、
「a_nからa_(n+1)は作れない」
といったところでしょうか。

以上、参考になれば幸いです。

No.1 回答者： Tacosan 回答日時： 2010/04/19 12:19

「漸化式を作る」ということなら, 多くの場合「より小さい場合を考え, それに何かを追加する」という方針でいけるはず.

今の場合だと「n個のマスを塗る」んだけど, 「より小さい場合」として何が適当だと思いますか?