There is a rectangular plot of size $1 \times n$. This has to be covered by three types of tiles - red, blue and black. The red tiles are of size $1 \times 1$, the blue tiles are of size $1 \times 1$ and the black tiles are of size $1 \times 2$. Let $t _ { n }$ denote the number of ways this can be done. For example, clearly $t _ { 1 } = 2$ because we can have either a red or a blue tile. Also, $t _ { 2 } = 5$ since we could have tiled the plot as: two red tiles, two blue tiles, a red tile on the left and a blue tile on the right, a blue tile on the left and a red tile on the right, or a single black tile.
(a) Prove that $t _ { 2 n + 1 } = t _ { n } \left( t _ { n - 1 } + t _ { n + 1 } \right)$ for all $n > 1$.
(b) Prove that $t _ { n } = \sum _ { d \geq 0 } \binom { n - d } { d } 2 ^ { n - 2 d }$ for all $n > 0$.
Here,
$$\binom { m } { r } = \begin{cases} \frac { m ! } { r ! ( m - r ) ! } , & \text { if } 0 \leq r \leq m , \\ 0 , & \text { otherwise } , \end{cases}$$
for integers $m , r$.