漸化式の応用４　3項間

2016年9月21日2016年9月22日

漸化式の応用です。3項間漸化式を立てて解く問題をいくつか。

１．(京都大)
先頭車両から順に1から $n$ までの番号のついた $n$ 両編成の列車がある．ただし $n \geqq 2$ とする．各車両を赤色，青色，黄色のいずれか1色で塗るとき，隣り合った車両の少なくとも一方が赤色となるような色の塗り方は何通りか．

２．(東京大)
二辺の長さが1と2の長方形と一辺の長さが2の正方形の2種類のタイルがある．縦2，横 $n$ の長方形の部屋をこれらのタイルで過不足なく敷きつめることを考える．そのような並べ方の総数を $A_n$ で表す．ただし， $n$ は正の整数である．たとえば $A_1=1,~A_2=3,~A_3=5$ である．このとき，
(1) $n \geqq 3$ のとき， $A_n$ を $A_{n-1},~A_{n-2}$ を用いて表せ．
(2) $A_n$ を $n$ で表せ．