Little Abel received as a gift a $2 \times n$ board and $n$ tiles of size $2 \times 1$. For example, the following figure shows the case where $n=10$, that is, when Abel has a $2 \times 10$ board and 10 tiles of size $2 \times 1$.
![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-15.jpg?height=404&width=996&top_left_y=553&top_left_x=630)

He plays by filling the board using the $n$ tiles. For example, for $n=10$ Abel could fill it in the ways illustrated below:
![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-15.jpg?height=580&width=1042&top_left_y=1144&top_left_x=608)

However, observe that there are many other ways in which Abel can fill his board.

a) Calculate the total number of ways in which Abel can fill his board in the cases where $n=1, n=2$, and $n=3$, that is, in the cases where the boards have dimensions $2 \times 1, 2 \times 2$, and $2 \times 3$.

b) Let $a_{n}$ be the number of ways in which Abel can fill a $2 \times n$ board using $n$ tiles of size $2 \times 1$. Show that $a_{10}=a_{9}+a_{8}$.

c) Calculate the total number of ways in which Abel can fill his board when $n=10$.
Solution

a) We can easily count the first few cases and observe that $a_{1}=1, a_{2}=2 \text{ and } a_{3}=3$, as shown in the figure below.
![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-41.jpg?height=368&width=758&top_left_y=1846&top_left_x=750)

b) When starting to fill his $2 \times 10$ board, Abel can proceed in two distinct ways:

- Abel can start by placing a tile vertically in the first column of the board:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-41.jpg?height=124&width=526&top_left_y=2574&top_left_x=865)

- Otherwise, he must start by placing two horizontal tiles in the first two cells of the first two rows of the board:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-42.jpg?height=126&width=528&top_left_y=391&top_left_x=661)

In the first case, Abel will need to use the remaining nine tiles to fill the rest of the board, which coincides with a $2 \times 9$ board. He can do this in $a_{9}$ ways.

In the second case, Abel will need to use the remaining eight tiles to fill the rest of the board, which coincides with a $2 \times 8$ board. He can do this in $a_{8}$ ways.

Thus, we conclude that the total number of ways Abel can complete the filling of his board is equal to $a_{9} + a_{8}$. Therefore, we conclude that:

$$
a_{10} = a_{9} + a_{8}
$$

c) Repeating the same argument used in the previous item, we have that, more generally, the ways in which we can fill a $2 \times n$ board are divided into two groups. The first group, in which one starts by positioning a vertical tile on the left side of the board:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-42.jpg?height=122&width=514&top_left_y=1521&top_left_x=677)

And the other group in which one starts by positioning two horizontal tiles on the left side of the board:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-42.jpg?height=120&width=532&top_left_y=1842&top_left_x=662)

For the first group, the number of ways to continue the filling coincides with $a_{n-1}$, while for the second group, this number of ways coincides with $a_{n-2}$. We conclude that

$$
a_{n} = a_{n-1} + a_{n-2}, \quad \text{for all } n \geq 3
$$

Indeed, from item a), we have that $a_{1} = 1$ and $a_{2} = 2$. Now we can use (14) to obtain the next values of $a_{n}$. Indeed, we have that $a_{3} = a_{2} + a_{1} = 3$ (as we had already determined in item a)). Similarly, we have that $a_{4} = a_{3} + a_{2} = 3 + 2 = 5$. Continuing with the same reasoning, we obtain that:

$$
a_{5} = 8, \quad a_{6} = 13, \quad a_{7} = 21, \quad a_{8} = 34, \quad a_{9} = 55 \quad \text{and} \quad a_{10} = 89
$$

Therefore, there are 89 ways in which little Abel can fill the $2 \times 10$ board.