https://spherical-harmonics.hateblo.jp/entry/Todai/1995/Rika

2024.01.13記

[3] 二辺の長さが $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$ で表せ．

2024.01.13記

[解答]
(1) 縦 $2$ ，横 $n$ の敷きつめにおいて，
(a) 左端が $2\times2$ となるのは $A_{n-2}$ 通り，
(b) 左端が $1\times2$ が2段となるのは $A_{n-2}$ 通り
(c) 左端が $2\times1$ となるのは $A_{n-1}$ 通り
であるから， $A_n=A_{n-1}+2A_{n-2}$ が成立する．

(2) $A_n+A_{n-1}=2(A_{n-1}+A_{n-2})=2^{n-2}(A_2+A_1)=2^n$ （ $n\geqq 2$ ），
$A_n-2A_{n-1}=-(A_{n-1}-2A_{n-2})=(-1)^{n-2}(A_2-2A_1)=(-1)^{n-2}=(-1)^n$ （ $n\geqq 2$ ）
であるから，これらから $A_{n}$ を消去して
$A_{n-1}=\dfrac{2^n-(-1)^n}{3}$ （ $n\geqq 2$ ）
となる．よって添字を1つずらして
$A_{n}=\dfrac{2^{n+1}-(-1)^{n+1}}{3}$ （ $n\geqq 1$ ）
となる．

第3問がこんなに簡単だと恐いよね。