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\ge 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\le 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}\wedge F_n=F_n\wedge F_{n-1}=\cdots =F_2\wedge F_1=1\wedge 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\wedge 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\le 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.