Suite de Fibonacci

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 ?

Découpage du carré et réarrangement apparent en rectangle

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.

3. Pour tout {(n,m)\in\mathbb N^2}, montrer {F_{n+m+1}=F_{m+1}F_{n+1}+F_mF_n}.

4. En déduire que pour tout {(q,n)\in\mathbb N^2}, {F_{qn}} est un multiple de {F_n}.

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.

7. Montrer qu’on peut maintenant compléter la question 4 : pour {n\geq3} et {m\in\mathbb N}, {F_n\mid F_m\iff n\mid m}.

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}}

8. (b) Conclure.

Deuxième partie

Dans cette partie, on étudie des problèmes relatifs à des sommes d’entiers {F_n}.

1. Montrer que pour tout entier naturel {n}, {\sum\limits_{k=0}^nF_k=F_{n+2}-1}.

2. Montrer {\sum\limits_{k=0}^nF_k^2=F_nF_{n+1}} pour {n\geq0}.

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}.

3. (b) En déduire que {n\mapsto S_n(x)} converge pour tout {x\in I=]-1/\Phi,1/\Phi[}.

3. (c) Pour {x\in I}, on note {S(x)=\sum\limits_{k=0}^{+\infty}F_kx^k=\lim\limits_{n\to\infty}S_n(x)}. Prouver {S(x)=x/(1-x-x^2)}.

3. (d) Calculer {\begin{array}{rcl}y&=&0.1+0.01+0.002+0.0003\\[4pt]&&+0.00005+0.000008\\[4pt]&&+0.0000013+0.00000021+\cdots\end{array}}

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}.

4. (c) Soit {n\geq1}. Montrer qu’il existe une unique décomposition {n=F_{k_0}+\cdots+F_{k_p}}, avec {p\geq0} et {k_0\gg\cdots\gg k_p\gg0}.

4. (d) Former la décomposition de {n=2002}.

Dans cette question, on cherchera le rapport avec les nombres de Fibonacci.

5. (a) De combien de façons différentes peut-on daller une allée {2\times n} avec des dalles {2\times1} ?

5. (b) Épatez vos amis, brillez en société ! Vous distribuez dans l’assistance 8 cartes numérotées contenant chacune des entiers de 1 à 54.

Carte n°1 : 1, 4, 6, 9, 12, 14, 17, 19, 22, 25, 27, 30, 33, 35, 38, 40, 43, 46, 48, 51, 53

Carte n°2 : 2, 7, 10, 15, 20, 23, 28, 31, 36, 41, 44, 49, 54

Carte n°3 : 3, 4, 11, 12, 16, 17, 24, 25, 32, 33, 37, 38, 45, 46, 50, 51

Carte n°4 : 5, 6, 7, 18, 19, 20, 26, 27, 28, 39, 40, 41, 52, 53, 54

Carte n°5 : 8, 9, 10, 11, 12, 29, 30, 31, 32, 33, 42, 43, 44, 45, 46

Carte n°6 : 13, 14, 15, 16, 17, 18, 19, 20, 47, 48, 49, 50, 51, 52, 53, 54

Carte n°7 : 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33

Carte n°8 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54

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 ?