Exercice 23

1. On calcule de proche en proche : $$\boxed{1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55}$$

2. Notons $p_{n}$ le nombre de pavages d'un rectangle $2 \times n$. Dans un pavage, la première colonne est couverte soit par un domino vertical, et le reste est un pavage d'un rectangle $2 \times (n - 1)$ ; soit par deux dominos horizontaux superposés, qui couvrent les deux premières colonnes, et le reste est un pavage d'un rectangle $2 \times (n - 2)$. Ces deux cas s'excluent, d'où $p_{n} = p_{n-1} + p_{n-2}$ pour $n \geqslant 3$. Comme $p_{1} = 1 = F_{2}$ et $p_{2} = 2 = F_{3}$ (deux dominos verticaux, ou deux horizontaux), une récurrence double donne $$\boxed{p_{n} = F_{n+1} \text{ pour tout } n \geqslant 1.}$$

3. Fixons $n \geqslant 2$ et raisonnons par récurrence double sur $m$. Pour $m = 1$ : $F_{n-1}F_{1} + F_{n}F_{2} = F_{n-1} + F_{n} = F_{n+1}$. Pour $m = 2$ : $F_{n-1}F_{2} + F_{n}F_{3} = F_{n-1} + 2F_{n} = F_{n+1} + F_{n} = F_{n+2}$. Si la formule est vraie aux rangs $m$ et $m + 1$, on les additionne : $$F_{n+m} + F_{n+m+1} = F_{n-1}(F_{m} + F_{m+1}) + F_{n}(F_{m+1} + F_{m+2}), \quad\text{soit}\quad F_{n+m+2} = F_{n-1}F_{m+2} + F_{n}F_{m+3}.$$

$$\boxed{F_{n+m} = F_{n-1}F_{m} + F_{n}F_{m+1}}$$ La question 2 en donne aussi une preuve sans calcul. Un pavage d'un rectangle $2 \times (n + m - 1)$, il y en a $F_{n+m}$, est soit coupé verticalement entre les colonnes $n - 1$ et $n$, et il se compose alors d'un pavage $2 \times (n - 1)$ et d'un pavage $2 \times m$, soit traversé à cet endroit par deux dominos horizontaux superposés, qui couvrent les colonnes $n - 1$ et $n$ et laissent un pavage $2 \times (n - 2)$ et un pavage $2 \times (m - 1)$. On obtient $F_{n}F_{m+1} + F_{n-1}F_{m}$ pavages.

4. Par récurrence sur $n \geqslant 2$. Pour $n = 2$ : $F_{2}^{2} = 1$ et $F_{1}F_{3} + (-1)^{3} = 2 - 1 = 1$. Si la formule est vraie au rang $n$, alors $$\begin{aligned} F_{n+1}^{2} - F_{n}F_{n+2} &= F_{n+1}^{2} - F_{n}(F_{n+1} + F_{n}) = F_{n+1}(F_{n+1} - F_{n}) - F_{n}^{2} \\ &= F_{n+1}F_{n-1} - F_{n}^{2} = -(-1)^{n+1} = (-1)^{n+2}. \end{aligned}$$

$$\boxed{F_{n}^{2} = F_{n-1}F_{n+1} + (-1)^{n+1}}$$ C'est l'identité de Cassini. Pour $n = 6$ : $64 = 5 \times 13 - 1$. ✓

5. Notons $T_{k} = F_{1}F_{2} + \dots + F_{k}F_{k+1}$, et montrons par récurrence sur $n \geqslant 1$ l'assertion « $T_{2n-1} = F_{2n}^{2}$ et $T_{2n} = F_{2n+1}^{2} - 1$ ». On utilise l'identité de Cassini sous la forme $F_{k}F_{k+2} = F_{k+1}^{2} + (-1)^{k+1}$.

• Si $T_{2n-1} = F_{2n}^{2}$, alors $T_{2n} = F_{2n}^{2} + F_{2n}F_{2n+1} = F_{2n}F_{2n+2} = F_{2n+1}^{2} - 1$.

• Si $T_{2n} = F_{2n+1}^{2} - 1$, alors $T_{2n+1} = F_{2n+1}(F_{2n+1} + F_{2n+2}) - 1 = F_{2n+1}F_{2n+3} - 1 = F_{2n+2}^{2}$.

Comme $T_{1} = F_{1}F_{2} = 1 = F_{2}^{2}$, la récurrence s'amorce. $$\boxed{T_{2n-1} = F_{2n}^{2} \qquad T_{2n} = F_{2n+1}^{2} - 1}$$ Vérification pour $n = 2$ : $1 + 2 + 6 = 9 = F_{4}^{2}$ et $9 + 15 = 24 = 25 - 1$. ✓ Le chapitre 7 donnera une expression explicite de $F_{n}$ à l'aide du nombre d'or rencontré à l'exercice 18.