Question: 2017 Fall Midterm - 14

Author: Michiel Smid

Let $n \geq 1$ be an integer and consider a $2 \times n$ board $B_n$ consisting of a total of $2n$ square cells. The top part of the figure below shows $B_{13}$.

A brick is a horizontal or vertical board consisting of 2 square cells; see the bottom part of the figure above. A tiling of the board $B_n$ is a placement of bricks on the board such that

the bricks exactly cover $B_n$ and
no two bricks overlap.

The figure below shows a tiling of $B_{13}$.

Let $T_n$ be the number of different tilings of the board $B_n$. Which of the following is true for any $n \geq 3$?

(a)

$T_n = T_{n + 1} + T_{n + 2}$

(b)

$T_n = T_{n - 1} + 2 \cdot T_{n - 2}$

(c)

$T_n = T_{n - 1} + T_{n - 2}$

(d)

$T_n = 2 \cdot T_{n - 1} + T_{n - 2}$