5. (10 points) How many ways are there to tile a $2 \times 12$ rectangle with non-overlapping $1 \times 2$ dominoes?

## Answer: 233
Solution. Let $d_{n}$ be the number of ways to tile a $2 \times n$ rectangle with non-overlapping $1 \times 2$ dominoes. If the first domino is placed vertically, the number of ways is $d_{n-1}$; if the first domino is placed horizontally, the number of ways is $d_{n-2}$. Then $d_{n}=d_{n-1}+d_{n-2}, d_{1}=1, d_{2}=2$.