Montrer que deux termes consécutifs de la suite de Fibonacci sont…

Stratégie : reconnaître dans la relation de Fibonacci une division euclidienne. On note $F_{0} = 0$ , $F_{1} = 1$ et $F_{n + 1} = F_{n} + F_{n - 1}$ .

a) La relation de Fibonacci EST un pas de l'algorithme d'Euclide. Pour $n \geq 2$ , on a $F_{n - 1} < F_{n}$ (la suite est strictement croissante à partir du rang $2$ ), donc l'écriture $F_{n + 1} = 1 \times F_{n} + F_{n - 1}, 0 \leq F_{n - 1} < F_{n}$ est exactement la division euclidienne de $F_{n + 1}$ par $F_{n}$ , de quotient $1$ et de reste $F_{n - 1}$ .

b) Conclusion par l'invariant d'Euclide. Le PGCD est invariant quand on remplace le grand terme par le reste : $F_{n + 1} \land F_{n} = F_{n} \land F_{n - 1} = \dots = F_{2} \land F_{1} = 1 \land 1 = 1$ Chaque étape de l'algorithme d'Euclide descend d'un cran dans la suite : la suite de Fibonacci est sa propre trace d'exécution.

⚠️ Le point délicat : l'inégalité $F_{n - 1} < F_{n}$ est nécessaire, et fausse au départ. On a $F_{1} = F_{2} = 1$ : le reste ne serait pas strictement plus petit. C'est pourquoi on initialise la descente en $n = 2$ et qu'on conclut à la main sur $F_{2} \land F_{1}$ .

Contrôle numérique. $F_{10} = 55 = 5 \times 11$ et $F_{11} = 89$ (premier) : PGCD $1$ . $F_{12} = 144$ et $F_{13} = 233$ : $233 = 1 \times 144 + 89$ , $144 = 1 \times 89 + 55$ , … la descente d'Euclide relit la suite à l'envers et s'arrête sur $1$ . Vérifié pour tous les $n \leq 58$ .

Ce que l'exercice installe. Fibonacci est le pire cas de l'algorithme d'Euclide : à taille donnée, aucun couple ne demande plus d'étapes, puisque chaque quotient y vaut $1$ , le plus petit possible. C'est le point de départ du théorème de Lamé sur le nombre d'étapes de l'algorithme.

Énoncé

Corrigé