For all $n \in \mathbb{N}$, we denote $u_{n}$ as the number of ways to tile a grid of size $2 \times n$ using dominoes of size $2 \times 1$. Provide a formula for $u_{n}$.
For small values, we calculate:

| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $u_{n}$ | 1 | 1 | 2 | 3 | 5 | 18 | 13 | 21 | 34 | 55 | 89 |

This reminds us of the Fibonacci sequence... We even conjecture that $u_{n}=F_{n+1}$, for all $n \in \mathbb{N}$. It remains to find a recurrence relation for $u_{n}$: if it is the same recurrence relation as the Fibonacci sequence, we are done! (we then show by double induction that the two sequences are equal, thanks to their common recurrence relation)

Consider the domino that covers the top-left corner of the grid: it is either horizontal or vertical.

- If it is vertical, then it paves the first column of the grid; thus, paving a grid of size $2 \times n$ is equivalent to paving a grid of size $2 \times (n-1)$: this gives $u_{n-1}$ possibilities.
- If it is horizontal, then the bottom-left corner of the grid must also be paved by a horizontal domino; thus, the first two columns of the grid are paved, and paving a grid of size $2 \times n$ is equivalent to paving a grid of size $2 \times (n-2)$: this gives $u_{n-2}$ possibilities.

Therefore, there are $u_{n-1}+u_{n-2}$ possibilities for paving a grid of size $2 \times n$, that is, $u_{n}=u_{n-1}+u_{n-2}$ for all $n \geq 2$: this is the famous recurrence relation we were looking for!

Strong induction. To show that a property $\mathcal{P}_{n}$ is true for all $n$, when we cannot systematically deduce the property at a given rank from a certain number $k$ of previous properties (fixed in advance like the order of a hypothetical recurrence), we can proceed as follows:

$\triangleright$ Initialization: we verify that the property $\mathcal{P}_{0}$ is true.

$\triangleright$ Induction step: we assume that there exists a natural number $n$ such that the properties $\mathcal{P}_{0}, \mathcal{P}_{1}, \ldots, \mathcal{P}_{n}$ are all true. We show that then the property $\mathcal{P}_{n+1}$ is also true.

Introduce the following exercise: in everyday life, we write numbers in base 10: we use the digits from 0 to 9, and the position of the digit corresponds to the power of 10 by which it must be multiplied to determine its contribution to the number. For example, 42 in base ten is $4 \times 10^{1}+2 \times 1$. In this base, two numbers written differently are necessarily different: we say that there is uniqueness of decomposition in this base.

Similarly, every number can be written uniquely in base 2: for example, since $42=1 \times$ $2^{5}+0 \times 2^{4}+1 \times 2^{3}+0 \times 2^{2}+1 \times 2+0 \times 1,42$ in base 10 is 101010 in base 2.

We similarly define the Fibonacci base, where the allowed digits are 0 and 1, and where the position of a digit corresponds to the rank, in the Fibonacci sequence, of the Fibonacci number by which it is multiplied. In this base, there is no uniqueness of decomposition: for example, 011 and 100 in the Fibonacci base both equal 3 in base 10. More generally, we can always replace two consecutive 1s with two 0s by adding 1 in the next column (since $\left.F_{n+2}=F_{n+1}+F_{n}\right)$.

We say that a decomposition in the Fibonacci base is valid if it does not contain two consecutive 1s.