問題
二辺の長さが1と2の長方形と一辺の長さが2の正方形の2種類のタイルがある。縦2，横の長方形の部屋をこれらのタイルで過不足なく敷きつめることを考える。そのような並べ方の総数をで表す。ただしは正の整数である。たとえば，，である。このとき以下の問いに答えよ。
(1) のとき，を，を用いて表せ。
(2) をで表せ。
出典：東京大学 1995年度 前期日程 第2次学力試験 理系 第3問
方針
右端の敷き方に注目して漸化式を作る。最後の1列だけで完結する場合は縦向き長方形1枚，最後の2列をまとめて使う場合は横向き長方形2枚または正方形1枚の2通りである。得られた は， 型と 型の和になることを利用して一般項を決め，初期値で係数を確定する。
解答
(1)
縦2，横 の長方形の右端を見る。最後の1列だけを使って右端を敷くには，縦2，横1の長方形タイルを1枚置くしかない。この場合，残りは縦2，横 の長方形であるから 通りである。
最後の1列だけで完結しない場合，右端のマスを含むタイルは最後の2列にまたがる。この2列の敷き方は，上下に横向きの 長方形を2枚置く場合と，一辺2の正方形を1枚置く場合の2通りである。残りは縦2，横 の長方形なので 通りである。
以上より， で である。
(2)
初期値は である。漸化式 に対して， と はどちらも同じ関係式を満たす。そこで とおく。初期値を代入すると である。これを解いて を得る。したがって である。
この式は で初期値を満たし，さらに
より漸化式も満たすので，すべての正の整数 で正しい。