質問＜２７３８＞２００５／１１／３０
from=西湖
「数列（2005年度入試問題）」

先頭車両から順に１からｎまでの番号のついたｎ両編成の列車がある。
ただし、ｎ≧２とする。
各車両を赤色、青色、黄色のいずれか1色で塗るとき、隣り合った車両の
少なくとも一方が赤色となるような色の塗り方は何通りか。

という問題なのですが、
数列で解くようなのですがどう考えてよいのか全く分かりませんでした。
よろしければ教えてください。

★希望★完全解答★

お便り２００５／１２／５
from=けんさん

漸化式を作って解くのがポピュラーかと思います。
n輌目が赤のときと赤でないときに場合分けするのがポイントでしょう。

n輌目まで「隣り合った車輌の少なくとも一方が赤色となるような色の塗り方」
をa_n通りとすると

（あ）ｎ輌目が赤の場合
　n-1輌目は何色でも良い。即ちn-1輌目まで「隣り合った車輌の少なくとも一方が
赤色となるような色の塗り方」をしていればよいからa_n-1×１（ｎ輌目が赤）通り

（い）n輌目が青か黄色の場合
　n-2輌目まで「隣り合った車輌の少なくとも一方が赤色となるような色の塗り方」
をして、n-1輌目を赤にしなければなりませんからa_n-2×１×２
（ｎ輌目が青か黄なので×２）

（あ）（い）より
a_n=a_n-1+2a_n-2という３項間の漸化式が成り立ちます。
ここでa_2=5（赤赤、赤青、赤黄、黄赤、青赤）、a_３＝１１（赤赤赤、赤赤黄、など）
ですから、この漸化式を解いて
a_n=(2＾(n+2）+(－1)＾n)／３
となります。
計算間違っていたらゴメン↓