17. Determine the number of ways of tiling a $4 \times 9$ rectangle by tiles of size $1 \times 2$.
17. Answer: 6336
Let $f_{n}$ be the number of ways of tiling a $4 \mathrm{x} n$ rectangle. Also, let $g_{n}$ be the number of ways of tiling a $4 \times n$ rectangle with the top or bottom two squares in the last column missing, and let $h_{n}$ be the number of ways of tiling a $4 \times n$ rectangle with the top and bottom squares in the last column missing. Set up a system of recurrence relations involving $f_{n}, g_{n}$ and $h_{n}$ by considering the ways to cover the $n$th column of a $4 \times n$ rectangle. If two vertical tiles are used, then there are $f_{e-1}$ ways. If one vertical tile and two adjacent horizontal tiles are used, then there are $2 g_{s-1}$ ways. If one vertical tile and two non-adjacent horizontal tiles are used, then there are $h_{n-1}$ ways. If four horizontal tiles are used, then there are $f_{n-2}$ ways. Similarly, one can establish the recurrence relations for $g_{n}$ and $h_{n}$. In conclusion, we obtain for $n \geq 2$,
$$
\begin{array}{llc}
f_{n}= & f_{n-1}+f_{n-2}+2 g_{n-1}+h_{n-1} \\
g_{n}= & g_{n-1}+f_{n-1} \\
h_{n}= & h_{n-2}+f_{n-1}
\end{array}
$$

With initial conditions $f_{0}=f_{1}=g_{1}=h_{1}=1$ and $h_{0}=0$. Solving $f_{n}$ recursively, we obtain $f_{9}=$ 6336.