Exercise 5. There are 2 ways to place two identical $1 \times 2$ dominoes to cover a $2 \times 2$ chessboard: either by placing both horizontally, or by placing both vertically.

In how many ways can a $2 \times 11$ chessboard be covered with 11 identical $1 \times 2$ dominoes?
Solution to Exercise 5 Let $a_{n}$ be the number of ways to cover a 2-row, $n$-column chessboard with $n$ identical $1 \times 2$ dominoes. We have $a_{1}=1$ and $a_{2}=2$.

If the top-left square is covered by a vertical domino, there remains a $2 \times (n-1)$ chessboard to cover, which gives $a_{n-1}$ possibilities.

If the top-left square is covered by a horizontal domino, then the bottom-left square must also be covered by a horizontal domino, and there remains a $2 \times (n-2)$ chessboard to cover, which gives $a_{n-2}$ possibilities.

We deduce that $a_{n}=a_{n-1}+a_{n-2}$ for all $n$. We then calculate step by step: $a_{3}=3, a_{4}=5, a_{5}=8, a_{6}=13, a_{7}=21, a_{8}=34, a_{9}=55, a_{10}=89$, $a_{11}=144$.