Évariste has to climb a staircase of $n \geqslant 1$ steps. To avoid tiring himself out too much, he decides at each step to climb one or two steps at a time, no more. In how many different ways can he climb the staircase?

The following exercises are not necessarily related to a specific section of the course.
We denote $u_{n}$ as the number of different ways to climb an $n$-step staircase. If $n \geqslant 3$, for the first step, either we climb it alone, which leaves $u_{n-1}$ possibilities, or we climb 2 steps at once, which leaves $u_{n-2}$ other possibilities. The recurrence relation obtained is therefore

$$
u_{n+2}-u_{n+1}-u_{n}=0
$$

for all $n \in \mathbb{N}^{*}$. The characteristic equation associated with it, $X^{2}-X-1=0$, has solutions $\Phi=\frac{1+\sqrt{5}}{2}$ and $\varphi=\frac{1-\sqrt{5}}{2}$, so for $n \in \mathbb{N}^{*}$,

$$
u_{n}=A \Phi^{n}+B \varphi^{n}
$$

With $\mathfrak{u}_{1}=1$ and $\mathfrak{u}_{2}=2$, we find: $A=\frac{1+\sqrt{5}}{2 \sqrt{5}}$ and $B=\frac{\sqrt{5}-1}{2 \sqrt{5}}$.