For $n \in \mathbb{N}^{*}$, we denote $a_{n}$ as the number of ways to cover a rectangle of size $2 \times n$ with pieces of size $1 \times 2$. Find a recurrence relation between the $a_{n}$.
Let $a_{0}=0$. We clearly have $a_{1}=1$. For $n \geqslant 2$, let's look at what can happen at the far left of the rectangle. Either we place a vertical domino,

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-429.jpg?height=191&width=554&top_left_y=1598&top_left_x=591)

and then there remains a rectangle of size $2 \times(n-1)$ which can be covered in $a_{n-1}$ different ways; or, we place two horizontal dominoes,

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-429.jpg?height=191&width=554&top_left_y=1943&top_left_x=591)

in which case there remains a rectangle of size $2 \times(n-2)$ which can be covered in $a_{n-2}$ different ways. Conclusion, we have the relation:

$$
a_{n}=a_{n-1}+a_{n-2}
$$