On définit la suite de Fibonacci {(F_n)_{n\geq0}} par {F_0=0}, {F_1=1} et, pour tout {n\geq0}, {F_{n+2}=F_{n+1}+F_n}.
On a donc {F_2=1}, {F_3=2}, {F_4=3}, {F_5=5}, {F_6=8}, {F_7=13}, {F_8=21}, etc. On définit ainsi une suite d’entiers naturels, strictement croissante à partir du rang 2.
Leonardo Pisano, dit Fibonacci (1170-1250), a contribué, par son œuvre principale, le Liber abaci, à populariser la numération positionnelle utilisant les chiffres arabes. Les entiers {F_n} y apparaissent dans un problème relatif à la descendance d’un couple de lapins. C’est le mathématicien français Édouard Lucas (1842-1891) qui baptisa cette suite et en découvrit d’intéressantes propriétés.
Première partie
Dans cette partie, on étudie quelques propriétés de divisibilité portant sur les entiers {F_n}.
1. Pour tout {n} de {\mathbb N^*}, prouver la relation de Cassini : {F_{n+1}F_{n-1}-F_n^2=(-1)^n}. En déduire que pour tout {n\geq1}, les entiers {F_{n-1}} et {F_n} sont premiers entre eux.
2. Pouvez-vous expliquer le paradoxe suivant, attribué à Lewis Carroll ? On découpe un carré {8\times8} comme indiqué en deux triangles et deux trapèzes. On réarrange les quatre morceaux en un seul rectangle de taille {5\times13}.
Avant découpe, l’aire totale vaut 64. Après réarrangement, elle vaut 65. D’où vient le carré supplémentaire ?
Généraliser très soigneusement en utilisant les entiers {F_n}.
Lewis Carroll (1832-1898), logicien et écrivain britannique, est l’auteur d’Alice au pays des merveilles.
5. On se donne {(m,n)\in\mathbb N^2}, avec {m\leq n}, et un entier naturel {d}. Montrer que si {d} divise {F_n} et {F_m}, alors il divise {F_{n-m}} (utiliser les questions 1 et 3).
6. En déduire que pour tous entiers naturels {m,n}, {F_m\wedge F_n=F_{m\wedge n}}.
Indication : on sera amené à démontrer que si {p} divise {F_m} et {F_n}, alors il divise {F_{m\wedge n}}. Pour cela, raisonner par récurrence sur {m+n} et utiliser la question 5.
On va prouver le lemme de Yuri Matijasevitch (1970) : pour {n\geq3} et {m\geq0}, {F_m} est divisible par {F_n^2} si et seulement si {m} est divisible par {nF_n}.
8. (a) Par récurrence sur {k\geq1}, montrer les congruences {\begin{array}{rcl}F_{kn}&\equiv&kF_nF_{n+1}^{k-1}\pmod{F_n^2}\\[4pt]F_{kn+1}&\equiv&F_{n+1}^k\pmod{F_n^2}\end{array}}
On note {\Phi=(1+\sqrt5)/2} la solution positive de {x^2=x+1} : c’est le nombre d’or. On pose {S_n(x)=\sum\limits_{k=0}^nF_kx^k} pour tout réel {x} et tout entier naturel {n}.
3. (a) Montrer que pour tout entier naturel {n}, {0\leq F_n\leq\Phi^n}.
On va établir que tout entier naturel non nul s’écrit de façon unique comme somme d’entiers {F_n} non consécutifs : c’est le théorème de Zeckendorf (1972). On notera {n\gg m} pour exprimer {n\geq m+2}.
4. (a) Montrer {F_n+F_{n-2}+F_{n-4}+\cdots=F_{n+1}-\varepsilon}, où {\varepsilon=1} si {n} est pair et {\varepsilon=0} sinon.
4. (b) Soit {n\geq1}. On suppose qu’il existe {k_0\gg k_1\gg\cdots\gg k_p\gg0}, avec {p\geq0}, tels que {n=F_{k_0}+\cdots+F_{k_p}}. Montrer que {k_0} est nécessairement l’entier {k} maximum tel que {F_k\leq n}.
Vous demandez à une personne de l’assistance de choisir un entier au hasard, de 1 à 54, puis sur quelles cartes apparaît ce numéro. Sous les applaudissements, vous devinez le numéro mystérieux. Comment faites-vous ?
5. (c) Deux joueurs participent au jeu suivant. Au départ, on dispose d’un tas de {n\geq1} haricots. Le premier en retire {m}, avec {1\leq m\lt n}. Le second en retire au moins un mais au plus {2m}.
Plus généralement, chaque joueur doit retirer un nombre de haricots au moins égal à 1 et au plus égal au double du nombre que vient de retirer l’autre joueur. Le joueur qui retire le dernier haricot gagne la partie.
Y a-t-il une stratégie gagnante pour le premier joueur ?
