We have a domino of width 1 and length $n$. We denote $A_{n}$ as the number of possible colorings of this domino, that is, the number of different ways to blacken or not blacken the cells. We denote $F_{n}$ as the number of ways to color this domino such that there are never two adjacent blackened cells.

1. Calculate $A_{n}$.
2. Calculate $F_{1}, F_{2}, F_{3}$ and $F_{4}$.
3. Find a recurrence relation between the $F_{n}$.
4. Show that $\forall n \in \mathbb{N}^{*}, \forall p \in \mathbb{N}^{*}, F_{n+p+1}=F_{n} F_{p}+F_{n-1} F_{p-1}$.
1. For each cell, we can choose to color it or not (2 choices). Therefore, we have $A_{n}=2^{n}$.
2. We easily find $F_{1}=2, F_{2}=3, F_{3}=5, F_{4}=8$.
3. Let $n \geqslant 3$ and distinguish two cases. If the first cell is colored, the second one must not be.

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-430.jpg?height=100&width=548&top_left_y=567&top_left_x=774)

There remains a domino of length $n-2$ that can be colored without any particular constraint ($F_{n-2}$ choices). If the first cell is not colored, there is no constraint on the second one, and there remains a domino of length $n-1$ to be colored ($F_{n-1}$ choices).

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-430.jpg?height=103&width=534&top_left_y=965&top_left_x=778)

Conclusion, for $n \geqslant 3$, we have the relation:

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

4. Let $n \geqslant 1$ and $p \geqslant 1$. We consider a domino of length $n+p+1$ and look at the $(n+1)$-th cell. If we choose not to color this cell, there is then a domino of length $n$ on the left and a domino of length $p$ on the right that can be colored without any particular constraint. This gives a total of $F_{n} F_{p}$ choices.

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-430.jpg?height=103&width=831&top_left_y=1650&top_left_x=630)

If we choose to color it, its neighbors must remain white, and we then have dominos of length $n-1$ and $p-1$ to be colored without any particular constraint on the left and right, respectively. This gives $F_{n-1} F_{p-1}$ choices.

![](https://cdn.mathpix.com/cropped/2024_05_10_8c44cd8b5c585c15e58bg-430.jpg?height=94&width=834&top_left_y=1986&top_left_x=631)

Conclusion, we have:

$$
F_{n+p+1}=F_{n} F_{p}+F_{n-1} F_{p-1}
$$