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

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

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

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

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