東京大学 1995年度 前期日程 第2次学力試験理系数学 第3問

(1)
右端を縦向きの長方形1枚で敷く場合、残りは $2\times (n-1)$ なので $A_{n-1}$ 通りである。
右端の2列をまとめて敷く場合は、横向き長方形2枚または正方形1枚の2通りで、
残りは $2\times (n-2)$ である。よって$$A_n=A_{n-1}+2A_{n-2}(n\geqq 3)\mathrm{.}$$(2)
特性方程式$$r^2-r-2=0$$の根は $2,-1$ であるから$$A_n=C{2}^n+D(-1{)}^n$$とおける。$A_1=1$，$A_2=3$ を代入すると$$2C-D=1,4C+D=3.$$よって $C=2\mathrm{/}3$，$D=1\mathrm{/}3$ であり$$A_n={\displaystyle \frac{2^{n+1}+(-1{)}^n}{3}}\mathrm{.}$$右端の敷き方

空の敷き方を $A_0=1$ として漸化式を拡張する。
$B_n=A_n+A_{n-1}$ とおくと等比数列になり、交代和から一般項を得る。

(1)
右端が縦向き長方形なら $A_{n-1}$ 通り、右端2列を横向き長方形2枚または正方形で覆うなら
$2A_{n-2}$ 通りだから$$A_n=A_{n-1}+2A_{n-2}\mathrm{.}$$(2)
空の長方形の敷き方を1通りとして $A_0=1$ とおく。このとき上の漸化式は $n=2$ でも成り立つ。$$B_n=A_n+A_{n-1}$$とおけば$$B_n=(A_{n-1}+2A_{n-2})+A_{n-1}=2B_{n-1}\mathrm{.}$$$B_1=A_1+A_0=2$ より$$A_n+A_{n-1}=B_n=2^n\mathrm{.}$$したがって$$\begin{array}{rl}{\displaystyle A_n}& {\displaystyle =2^n-A_{n-1}}\\ {\displaystyle }& {\displaystyle =2^n-2^{n-1}+A_{n-2}}\\ {\displaystyle }& {\displaystyle \mathrm{⋮}}\\ {\displaystyle }& {\displaystyle =2^n-2^{n-1}+2^{n-2}-\cdots +(-1{)}^{n-1}2+(-1{)}^n\mathrm{.}}\end{array}$$これは初項 $2^n$、公比 $-1\mathrm{/}2$ の等比数列の和なので$$A_n={\displaystyle \frac{2^{n+1}+(-1{)}^n}{3}}\mathrm{.}$$