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

---

条件を満たし n 番目が赤である塗り方を an 通りとし 　条件を満たし n 番目が赤でない塗り方を bn 通りとする 　求めるのは an + bn である。 n = 2 のときは 　a2 = 3　　(一両目は何色でもよく、二両目が赤色なので) 　b2 = 2　　(一両目は赤のはずで、二両目が赤色以外なので) である。 　n ≥ 3 のとき 　an = an-1 + bn-1 　　(n-1 両目までは条件を満たし、n 両目は赤なので) 　bn = 2an-1 　　(n両目は赤以外、n-1両目までは条件を満たし、n-1 両目は赤なので) よって 　a3 = 5 で 　b3 = 6 である

.

n ≥ 4 のとき 　an = an-1 + 2an-2 これより an - 2an-1 = -(an-1 - 2an-2) = (-1)n-3(a3 - 2a2) = (-1)n an + an-1 = 2(an-1 + an-2) = 2n-3(a3 + a2) = 2n よって an = (2n+1 + (-1)n)/3 を得る。上の式は n = 2, 3 の時も成り立っている。 　n ≥ 3 のとき bn = 2an-1 = (2n+1 - 2(-1)n)/3 この式も n = 2 の時も成り立っている。 n ≥ 2 なる全ての n に対して an + bn = (2n+2 - (-1)n)/3 答え (2n+2 - (-1)n)/3

---

　　もどる

---