Suites de Fibonacci
("99%" des résultats énoncés ici sont démontrés ... ici.)
Trois résultats me semblent inédits : le 1.8 de P10, le 2) de P15 et la propriété citée dans l'énoncé de l'exercice 20 (fin de P15), mais bon je n'ai certainement pas tout lu sur Fibonacci...

1) Aspect historique
Spirale de Fibonacci
2) Définition générale ; cas particuliers des suites (F) et (L) 3) Opérations sur les suites de Fibonacci 4) Formule de Binet
5) Applications immédiates de Binet :
lim un+1/un ; formules explicites pour Fn et Ln ;
cas n<0 ; trigonométrie hyperbolique
6) Fonction génératrice 7) Relations linéaires entre les suites (F) et (L) 8) Des relations non linéaires entre les suites (F) et (L) et et des relations non linéaires intra (F) et intra (L)
Et deux exercices sur la sommation de séries dont le terme général est l'inverse d'un terme d'une suite de Fibonacci ou le produit de deux de ces termes
9) Une fomule donnant Fn+1 en fonction de Fn et du nombre d'or 10) Pgcd et suites (F), (L) ; algorithme d'Euclide 11) Sur l'écriture d'un entier naturel sous forme d'une somme de termes de la suite (F)
Z_somme
12) Equations diophantiennes et Fibonacci
13) Sur la suite de Fibonacci (F) modulo m 14) Sur la suite de Fibonacci (F) et Tchebycheff :
étonnament, Fn peut s'écrire sous forme d'un produit
de termes de la forme 3+2cos(2kp/n)
15) Sur Fkn et Lkn
en fonction de Fn et Ln
16) Sur une généralisation de
F2n=Fn+12-Fn-12
17) Le seul terme de la suite (F)
qui est un carré
(autre que 0 ou 1),
est F12=144
Annexe : le jeu de Nim-Fibonacci

P1->Aspect historique : au début du 13ième siècle, Leonardo Fibonacci se pose la question suivante : combien de couples de lapins obtiendrions-nous la fin d'une anne si, commenant en début de mois avec un couple, chacun des couples, après deux mois d'existence, produisait chaque début de mois un nouveau couple?

Si on note un le nombre de couples de lapins au début du mois n (n1), l'énoncé dit que u1=1, u2=1, puis u3=2 (puisque le 1er couple, couple 1, va en produire un autre, le couple 2, au début du 3ième mois) ; puis u4=2+1=3 (le couple 1 produit un autre couple, le couple 3, mais le couple 2 ne produit encore rien) ; puis u5=les couples existant (déjà) au début du mois 4 + le nombre de couples producteurs au début de ce mois 5 ; or les couples producteurs sont ceux ayant au moins deux mois d'existence, cad u3, et ainsi u5=u4+u3=3+2=5.
En fait, on peut généraliser ce raisonnement :
pour n3, un=les couples existant (déjà) au début du mois n-1 + le nombre de couples producteurs au début de ce mois n ; or les couples producteurs sont ceux ayant au moins deux mois d'existence, cad un-2, et ainsi un=un-1+un-2, cad un est la somme des effectifs des deux mois précédents.
En appliquant cette formule dix fois, on obtient successivement u3=2, u4=3, u5=5, u6=8, u7=13, u8=21, u9=34, u10=55, u11=89, u12=144.

A l'examen des premiers termes de cette suite il semble, notamment, que deux termes consécutifs soient premiers entre eux, et que un divise u2n : cela sera prouvé plus loin (exercice 1 et P8).

Cette suite n'est pas arithmétique (un+1-un n'est pas constant), ni géométrique (un+1/un n'est pas constant).
Cependant le rapport un+1/un semble se "stabiliser" vers un nombre approximativement égal à 1,618 :
u2/u1=1 ; u3/u2=2 ; u4/u3=1,5 ; u5/u4=5/3=1,666... ; u6/u5=8/5=1,6 ; u7/u6=13/8=1,625 ; u8/u7=21/13=1,615... ; u9/u8=34/21=1,619... ; u10/u9=55/34=1,617... u11/u10=89/55=1,618... ; u12/u11=144/89=1,617....
On montrerera effectivement (P5) que la limite en + de un+1/un est le nombre d'or (la définition précise de ce nombre sera donnée à P4), dont le développement décimal commence par 1,6180339... ; c'est-à-dire, pour n grand, la suite de Fibonacci est "presque" géométrique : on passe d'un terme au suivant en le multipliant par un nombre "presque" égal au nombre d'or. On verra à P9 comment on passe exactement de un à un+1.

Cette suite peut se représenter géométriquement par ce qu'on appelle la spirale de Fibonacci :


A part les deux premiers carrés de côtés u1=1 et u2=1 qui sont superposés, chaque carré a pour côté la somme des côtés des deux carrés précédents.
Dans chaque carré est traçé un quart de cercle de rayon le côté du carré et de centre un sommet du carré, cela de telle sorte que ces quarts de cercles se raccordent ("tout le monde" ne met pas un quart de cercle dans le premier carré de côté 1).
La juxtaposition de ces quarts de cercles est la spirale de Fibonacci. Compte-tenu que la longueur du quart de cercle inscrit dans le nième carré est pun/2, la longueur de la spirale de Fibonacci, arrêtée au nième carré (compris) est p(un+2-1)/2 (voir question 3 de l'exercice 1 situé après P4).
En faisant une recherche sur Fibonacci et spirale on trouvera beaucoup de liens sur cet aspect. Attention : cette spirale n'est pas la
spirale d'or, cela malgré le fait qu'il y a un lien étroit entre les suites de Fibonacci et le nombre d'or (voir la formule de Binet à P4).

P2->Définition générale d'une suite de Fibonacci :
c'est une suite (u)=(u)nN définie par un=un-1+un-2, pour tout n2, u0 et u1 étant donnés ; si u0 et u1 sont des entiers relatifs (naturels), il est évident que tous les termes de la suite sont aussi des entiers relatifs (naturels).
.

Note : contrairement l'aspect historique, on fait démarrer ces suites u0 :
en prenant u0=0, u1=1, on obtient u2=1 et on retrouve le cas de l'aspect historique : cette suite sera toujours notée F;
si on prend u0=u1=1, on retrouve aussi le cas de l'aspect historique, mais avec un décalage, car dans ce cas, pour tout entier naturel n, un=Fn+1.

Une autre suite de Fibonacci particulière est la suite de Fibonacci telle que u0=2 et u1=1 : elle est notée (L), et c'est la suite dite de Lucas.

On verra à P7 et P8 de nombreuses relations entre ces deux suites : notamment Fn+Ln=2Fn+1 (formule 1) de P7) et FnLn=F2n ( formule 8) de P8).

n-6-5-4-3-2-1
Fn-85-32-11
Ln18-117-43-1

n01234567891011121314
Fn01123581321345589144233377
Ln213471118294776123199322521843
n1516171819202122232425
Fn61098715972584418167651094617711286574636875025
Ln1364220735715778934915127244763960364079103682167761

Le lecteur "branché nombres premiers" aura tout de suite observé que F3, F5, F7, F11, F13 sont des nombres premiers! Et aussi F17=1597. Par contre F19=4181 n'est pas premier (37×113). Voir P10.

On remarque aussi que F5, F10 et même F15 sont des multiples de 5 : on verra à la question 6 de l'exercice 1 que 5 divise Fn <=> 5 divise n ; on trouvera dans cette question 6 d'autres résultats analogues.
En fait cette divisibilité par 5 "s'élargit" : pour tout p≥1, 5p divise F5p : voir exercice 20 où il y a aussi d'autres résultats analogues.

Compte-tenu de la formule F2n=LnFn (voir la relation 8 de P8), ce tableau permet d'obtenir F16, ..., F28.

Remarque : rien n'empêche de considérer qu'une suite de Fibonacci soit définie sur Z, cad de considérer que la relation un=un-1+un-2 est vraie pour tout n dans Z, u0 et u1 étant toujours donnés!!

u1=u0+u-1, soit u-1=u1-u0,
u0=u-1+u-2, soit u-2=u0-u-1,
cad, pour obtenir un terme d'indice négatif, en ne connaissant que ceux d'indice supérieur, on fait la différence des deux termes suivants : le 2ième suivant-le 1er suivant.
Sauf mention contraire, notamment au 1) et 5) de P3, à P5.3 (où on donnera une relation entre un et u-n) et au 14) de P8 et à P17, on se limitera toujours à des indices positifs ou nuls.

P3->
1) Si (u) et (v) sont deux suites de Fibonacci telles que u0=v0 et u1=v1, alors pour tout n dans N (et même dans Z) on a un=vn, c'est-à-dire, il s'agit de deux suites égales (ou identiques).

Une récurrence évidente le prouve. 2) Une suite de Fibonacci "décalée" reste une suite de Fibonacci : cad, si (u) est une suite de Fibonacci, k un entier naturel quelconque, la suite (v) définie par vn=un+k pour tout entier naturel n, est de Fibonacci. 3) La somme de deux suites de Fibonacci est une suite de Fibonacci.

4) Une suite de Fibonacci multipliée par une constante est une suite de Fibonacci.

Ces trois derniers résultats sont immédiats à prouver.

5) Si (u) est une suite de Fibonacci considérée comme définie sur Z (voir Remarque de P2), alors la suite (v) définie sur Z par vn=(-1)nu-n est aussi une suite de Fibonacci.

En effet, vn-1+vn-2=(-1)n-2(-u-n+1+u-n+2)=(-1)nu-n=vn. Remarque : les résultats 3) et 4) se traduisent par le fait que l'ensemble des suites de Fibonacci est un espace vectoriel sur R (la dimension de cet espace vectoriel sera précisée à l'exercice 1).

6) (F) étant la suite de Fibonacci telle que F0=0 et F1=1, (u) étant une suite de Fibonacci quelconque, on a les relations suivantes :

  • pour tout entier naturel , un+1=u0Fn+u1Fn+1,
    et donc connaissant les termes de la suite (F), on peut donc obtenir tout de suite ceux de la suite (u).
  • pour tout nN*, un+1=u1Fn-1+u2Fn
  • pour tout nN, tout pN*, un+p=Fp-1un+Fpun+1.

Pour la 1ière relation, une récurrence évidente le prouve :
  • la relation est bien vraie pour n=0 et n=1
  • supposons la relation vraie jusqu'au rang n(1) :
    u0Fn+1+u1Fn+2=u0(Fn+Fn-1)+u1(Fn+1+Fn)=(u0Fn+u1Fn+1)+(u0Fn-1+u1Fn)= un+1+un=un+2, et la relation est vraie au rang n+1.

On peut aussi procéder ainsi :
pour tout entier naturel n, on pose vn=un+1 et wn=u0Fn+u1Fn+1. Cf le 2) ci-dessus ces deux suites sont de Fibonacci ; or v0=u1=w0 et v1=u2, w1=u0F1+u1F2 =u0+u1=u2, soit v1=w1 et d'après le 1) ci-dessus, ces deux suites (v) et (w) sont égales, ce qui prouve le résultat.

Pour la 2ième relation, u1Fn-1+u2Fn=u1Fn-1+(u0+u1)Fn=u0Fn+u1Fn+1=un+1.

Pour la 3ième relation soit on fait une récurrence sur p (n est fixé), soit on remarque (à n fixé) que membre de gauche et membre de droite sont des suites de Fibonacci qui sont égales pour p=1 et p=2.

Remarque : pour prouver des relations sur des suites de Fibonacci, on vient de voir deux méthodes : récurrence ou utilisation du 1) ci-dessus de P3.
La formule de Binet ci-après peut donner, si besoin, une 3ième méthode
.

7) (F) étant la suite de Fibonacci avec F0=0 et F1=1, alors pour tout p dans N*, tout n dans N, Fp divise Fpn.

Si n=0 et n=1 c'est trivialement vrai.
Ensuite, cf le 6) ci-dessus, en prenant (u)=(F), on obtient Fk+p=Fp-1Fk+FpFk+1 :
en faisant k=p, on obtient Fp divise F2p,
puis en faisant k=2p, on obtient Fp divise F3p
"etc" (récurrence évidente).

Remarque : on verra d'autres preuves à la question 9 de l'exercice 1 ci-dessous et à P10.

P4->Soit (u) une suite de Fibonacci. En notant a le nombre d'or (a est la racine positive de x2-x-1=0 cad a=(1+5)/2=2cos(p/5) et l'autre racine de cette équation est b=(1-5)/2), pour tout entier naturel n on a :

un=aan+bbn, avec a=(-bu0+u1)/5 et b=(au0-u1)/5 : il s'agit de la formule de Binet On peut noter que : ab=-1, a+b=1, a-b=5
a et b ne sont pas des nombres rationnels car 5 n'est pas un nombre rationnel
a=0 u1=-bu0 ; b=0 u1=au0 ; a=b=0 u0=u1=0
a=b 2u1=u0 (auquel cas a=b=u1) : c'est le cas de la suite (L) ; a=-b u0=0 (auquel cas a=-b=u1/5) : c'est le cas de la suite (F)
Réciproquement, toute suite (u) définie par un=aan+bbn (a et b sont deux constantes réelles quelconques), pour tout entier naturel n est effectivement une suite de Fibonacci.

Voici une preuve de P4. On note vn=aan+bbn.
  • v0=a+b= (1/5)(a-b)u0=u0.
  • v1=aa+bb=(1/5)(a-b)u1=u1.
  • vn-1+vn-2=a(an-2(a+1))+ b(bn-2(b+1))= aan+bbn=vn
  • la suite (v) est donc, tout comme la suite (u), une suite de Fibonacci ; ces deux suites ayant respectivement les mêmes deux premiers termes, d'après le 1) de P3, elles sont égales, soit pour tout n dans N, un=vn.
On notera, que le fait d'avoir prouvé que la suite (v) est de Fibonacci, prouve la réciproque énoncée ci-dessus.

Remarque 0 : la formule de Binet est valable en fait pour n dans Z : la preuve ci-dessus le montre.

Remarque 1 : on peut objecter que pour pouvoir faire la preuve ci-dessus il faut conjecturer que un puisse s'écrire aan+bbn, avec a et b les deux constantes indiquées ci-dessus.
En fait c'est la théorie générale sur les suites récurrentes linéaires qui le dit! Cette théorie dit en effet qu'il existe deux constantes a et b telles que pour tout entier naturel n, un=aan+bbn, où a et b sont les racines de l'équation caractéristique x2-x-1=0.
Il n'y a plus qu'à chercher ces deux constantes a et b par résolution du systéme a+b=u0 et aa+bb=u1.

En fait les suites de Fibonacci sont un cas particulier des suites (u) telles que pour tout n≥0, un=Pun-1-Qun-2, avec P et Q deux constantes réelles (P=1, Q=-1 redonne les suites de Fibonacci).
Si P2-4Q≠0, une telle suite s'écrit aussi un=aαn+bβn, mais cette fois α et β sont les racines de x2-Px+Q=0.

Par exemple, si u0=0, u1=1, les termes suivants de la suite (u) sont
P, P2-Q, P3-2PQ, P4-3P2Q+Q2, P5-4P3Q+3PQ2,...
Chose "étonnante", si P>0 et Q<0 sont des entiers premiers entre eux, cette suite vérifie, tout comme la suite (F) la propriété suivante ( 1.2 de P10) :
pgcd(un,up)=upgcd(n,p).
Par exemple pgcd(u6,u4)=u2, cad pgcd(P5-4P3Q+3PQ2,P3-2PQ)=P

vérification :
pgcd(P5-4P3Q+3PQ2,P3-2PQ)=Ppgcd(P4-4P2Q+3Q2,P2-2Q)
Soit d un diviseur (entier >0) commun à P4-4P2Q+3Q2 et P2-2Q :
il divise P4-4P2Q+3Q2-(P2-2Q)2=-Q2.
Si d≠1, alors d admet un diviseur premier m, lequel divise Q2 donc Q, donc m divise (P2-2Q)+2Q=P2, donc m divise aussi P, ce qui est en contradiction avec le fait que P et Q sont premiers entre eux.
Donc on n'a pas d≠1, et ainsi d=1, ce qui donne pgcd(P4-4P2Q+3Q2,P2-2Q)=1.

Remarque 2 : il existe aussi (au moins) une 3ième preuve de la formule de Binet en écrivant matriciellement la relation de récurrence un=un-1+un-2 et en diagonalisant la matrice obtenue.
En effet, t étant l'opérateur transposé, la matrice colonne Xn=t( un un+1 ) vérifie la relation Xn=AXn-1, pour tout entier naturel n1, avec A la matrice à 2 lignes et 2 colonnes suivantes :

A=01
è11
.
On a donc, pour tout entier naturel n, Xn=AnX0, et donc pour obtenir Xn, donc pour obtenir un, il faut expliciter An en fonction de n, et pour cela il suffit de diagonaliser la matrice A. Cela est possible car A est symétrique.
Son polynôme caractéristique est
|-X1|=X2-X-1
|11-X|
.
Les deux valeurs propres de A sont donc a et b, de vecteurs propres associés t( 1 a ) et t( 1 b ) et ainsi A=PDP-1 avec P matrice 2×2 dont les deux colonnes sont les deux vecteurs propres précédents et D la matrice diagonale
D=a0
è0b
.
On a donc An=PDnP-1, et comme
P-1=1/(b-a)b-1
è-a1

et que Dn reste diagonale, de termes diagonaux an et bn, on obtient finalement
An=1/(b-a)bn-1-an-1bn-an
èbn-anbn+1-an+1

Et comme ( un un+1 )=( u0 u1 )An (on a transposé l'égalité Xn=AnX0), c'est que
un=1/(b-a)(u0(bn-1-an-1)+u1(bn-an)), ce qui donne, puisque a-b=5 et ab=-1
un=(1/(5))((-u0b+u1)an+(u0a-u1)bn).

Note : dans le cas de la suite (F), un=Fn=(an-bn)/5 (cet aspect sera développé à P5.2) et donc

An=Fn-1Fn=FnA+Fn-1I
èFnFn+1

Exercice 1 :

1) Il a été vu au 2) de P3, que l'ensemble des suites de Fibonacci est un espace vectoriel sur R. Trouver la dimension de cet espace vectoriel.

2) (u) étant une suite de Fibonacci quelconque,
montrer que "n0 on a pgcd(un,un+1)=pgcd(u0,u1).
Donc, si u0 et u1 sont premiers entre eux, deux termes quelconques, consécutifs, de la suite (u) sont premiers entre eux.
C'est le cas des suites F et L (F0=0, F1=1 ; L0=2, L1=1)
.
Remarque : ce résultat sera généralisé à P10.

3) (u) étant une suite de Fibonacci quelconque, montrer que
pour tout n dans N on a u0+u1+...+un=un+2-u1=Fn+1u0+(Fn+2-1)u1
(et donc F0+F1+...+Fn=Fn+2-1)
et que
pour tout n dans N et tout k dans N,
un+un+1+un+2+...+un+k=un+k+2-un+1=Fk+1un+(Fk+2-1)un+1
,
(F) étant la suite de Fibonacci telle que F0=0, F1=1.
Trouver des résultats analogues pour les sommes u0+u2+u4+...+u2n et u1+u3+u5+...+u2n+1.

(u) étant toujours une suite de Fibonacci quelconque, montrer que
pour tout n dans N, (u0)2+(u1)2+...+(un)2=unun+1 <=> u0=0 ou u0=u1.
C'est le cas de la suite F, puisque F0=0
.

4) (u) étant une suite de Fibonacci quelconque, montrer que pour tout entier naturel k, pour tout entier naturel nk, un+k=S0jk Ckj un-j
Note : on convient que C00 =1 (pour le cas k=0).

  • k=1 donne un+1=un+un-1
  • k=2 donne un+2=un+2un-1+un-2
  • k=3 donne un+3=un+3un-1+3un-2+un-3

Autre cas particulier, pour tout entier naturel n, u2n=S0jn Cnj uj.
Vérifier pour u8, cette dernière formule dans le cas u0=0, u1=1, cad si (u)=(F).

5) (F) étant la suite de Fibonacci telle que F0=0 et F1=1, montrer que pour n2, Fn est le nombre de parties non vides de En={1 ; 2 ; ... ; n-1}, deux éléments quelconques de chacune de ces parties n'étant pas consécutifs.

6) (F) étant la suite de Fibonacci telle que F0=0 et F1=1,

a) u étant une suite de Fibonacci avec u00 et u10, la suite (u) est croissante à partir du rang 1 et pour tout n2, un+12un ; préciser à quelles conditions cette inégalité sera vraie pour n=0 et n=1.
montrer que pour tout entier naturel n, sauf 0 et 2, Fn+1<2Fn
montrer que pour tout entier naturel n1, Fn+12Fn

b)

n étant un entier 5, montrer que Fn=(Fi+Fk)/2 avec i<k i=n-2 et k=n+1.
Remarque 1 : F2=(F0+F3)/2=(F1+F2)/2
F3=(F1+F4)/2=(F2+F4)/2
F4=(F1+F5)/2=(F2+F5)/2
Remarque 2 :
Voir l'exercice 13 sur l'écriture de kFn, k étant une constante entière, sous forme d'une somme de termes distincts de la suite (F).

c) montrer que

1) Fn pair 3 divise n (écrire Fn en fonction de Fn-2 et Fn-3)
2) 3 divise Fn 4 divise n (écrire Fn en fonction de Fn-3 et Fn-4)
3)
  • trouver des critères de divisibilité de Fn par 4, 5, 6, 7, 8, 9, 10.
  • Soit m un entier ≥2 : en admettant qu'il existe p non nul tel que m divise Fp, trouver un critère de divisibilité de Fn par m, cela en vous inspirant des calculs précédents. "Prière" de ne pas lire la remarque ci-dessous avant de réfléchir à la question...

Remarque : pour tout entier m≥2 on verra
  • au 1)f) de P13 la preuve qu'il existe effectivement un entier naturel p non nul tel que m divise Fp
  • au 1)g) de P13 la preuve qu'il existe un entier non nul g(m) tel que m divise Fn équivaut à g(m) divise n ; la preuve est différente de celle proposée dans cette question c)3).

Donc, de façon moins précise, on peut dire que pour tout entier m2, il existe une infinité de termes de la suite (F) qui sont divisibles par m ; en particulier, par exemple, une infinité de termes de la suite (F) se terminent (lorsqu'ils sont écrits en base 10) par quatre zéros.

4) Ln pair 3 divise n
5) 3 divise Ln 4 divise n-2
6) Ln ≡ 3 (4) n ≡ 2 ou 4 ou 5 (6)
7) Ln+12≡ Ln (8)

d) montrer que pour tout entier naturel n3, Fn>an-2 (si n=2, on a l'égalité : F2=1=a0) ; en déduire que limn->+Fn=+

e) montrer que pour tout entier naturel n1, an=aFn+Fn-1 ; cette relation est-elle encore vraie si on remplace a par b?

montrer que pour tout entier naturel n, Fn=(1/5)(an-bn) (on retrouvera cette formule à P5.2)

et aussi, montrer que pour tout entier naturel n, an=Fn+1-bFn.

f) montrer que pour tout entier naturel n1, Fn=S0k(n-1)/2Cn-1-kk
(Aide : on peut utiliser P3 et la formule combinatoire permettant d'obtenir le triangle de Pascal).

Appliquer cette formule pour n=1 à 8 et vérifier alors que la somme des termes du triangle de Pascal situs sur les segments paralléles "y=x", et partant des 1 constituant la colonne de gauche de ce triangle, sont les termes de la suite (F), à part F0 qui n'est pas obtenu.

g) montrer que pour tout entier naturel n1, S0in(-1)iFi=(-1)nFn-1-1

h) montrer que pour tout entier naturel n1, S1in2n-iFi-1=2n-Fn+2

7) Le lecteur ne verra qu'à la fin de l'énoncé de cette question pourquoi elle est là!
On considère les 11 nombres suivants : e1=23/(5×19)=23/95 ; e2=3×19/23=57/23 ; e3=17/(3×13)=17/39 ; e4=2×5×13/17=130/17 ; e5=11/(2×7)=11/14 ; e6=5×7/11=35/11 ; e7=19/13 ; e8=1/19 ; e9=5×7/2=35/2 ; e10=13/7 ; e11=7 et, a et b étant deux entiers naturels on transforme alors 2a3b par le procédé P suivant :
  • on multiplie u0=2a3b par ei, avec i le plus entier de {1;2;...;11} tel que u1=u0ei soit entier
  • on multiplie u1 par ej, avec j le plus entier de {1;2;...;11} tel que u2=u1ej soit entier
  • on multiplie u2 par ek, avec k le plus entier de {1;2;...;11} tel que u3=u2ek soit entier
  • etc
a) Si a=b=0, déterminer la suite (u) ainsi obtenue.
b) On suppose maintenant b1.
Montrer que le 1er terme de la suite (u) dont la décomposition en nombres premiers ne contient que les nombres 2 et 3 est 2b3a+b ; on pourra commencer par transformer, pas à pas, 2×32 (fait sur le site wiki), et si cela ne suffit pas on transformera pas à pas 2233 : là, on doit voir ce qui se passe.
Remarque : si on applique P à (pour des raisons hml, je note ici Fn par F_n) 2F_03F_1, le premier terme de la suite (u) dont la décomposition en nombres premiers ne contient que 2 et 3 sera 2F_13F_0+F_1=2F_13F_2, puis le premier terme suivant de la suite (u) dont la décomposition en nombres premiers ne contient que 2 et 3 sera 2F_23F_3 ; etc.
Bien entendu on aurait pu prendre, au lieu de la suite (F), n'importe quelle suite de Fibonacci commencant par deux entiers naturels.
Je laisse le lecteur faire le commentaire qu'il souhaite sur ce procédé P et sur ces suites de Fibonacci.

8) Soit A une matrice 3×3 magique ( les trois sommes des termes de chaque ligne et les trois sommes des termes de chaque colonne sont toutes égales à un même nombre s ) et dont tous les termes ai,j sont des entiers naturels.
(u) étant une suite de Fibonacci quelconque, on définit alors une matrice B de la façon suivante : son terme bi,j est le terme de la suite (u) de rang ai,j.
Par exemple, si

A=816
|357|
è492
alors
B=u8u1u6
|u3u5u7|
èu4u9u2
a) En se placant dans le cas général, comparer les deux sommes suivantes
  • S1=b1,1b1,2b1,3+b2,1b2,2b2,3+b3,1b3,2b3,3 (somme des produits des trois termes de chaque ligne de B)
  • S2=b1,1b2,1b3,1+b1,2b2,2b3,2+b1,3b2,3b3,3 (somme des produits des trois termes de chaque colonne de B)

b) Dans le cas de la matrice A donnée en exemple ci-dessus, exprimer S1 et S2 en fonction de u0 et u1.

9) Montrer que pour tous entiers naturels non nuls k et n, et en convenant que Fi0=1 même si i=0
Fkn=∑1≤p≤kCkp FpFnpFn-1k-p.
(Aide : utiliser la matrice A de la remarque 2 de P4 et élever à la puissance k la relation An=FnA+Fn-1I).
Cette relation prouve que Fn divise Fkn pour tout n dans N* et tout k cas dans N* ; mais c'est aussi vrai si k=0, car alors Fkn=0.
On verra à P15 d'autres formules donnnant Fkn uniquement en fonction de Fn si k est impair, et en fonction de Fn et Ln si n est pair.

10)


a)Montrer que pour tout p premier distinct de 3 et tout entier naturel n,
2 divise Fn+2p-Fn+p-Fn

et que
b) pour tout nombre premier p distinct de 2 et 3 et tout entier naturel n,
2p divise Fn+2p-Fn+p-Fn.

En particulier 10 divise Fn+10-Fn+5-Fn, cad Fn+10 et Fn+5+Fn ont même chiffre des unités.

c)Donner un critère de divisibilité par 2p de Fn+2p-Fn+p-Fn lorsque p=2 ou 3.

d) Est-ce que dans les résultats du a) et b) on peut remplacer p par pr où r est un entier naturel et est-ce que le domaine de validité pour n peut être étendu à tout Z?

vers la solution...chercher avant de cliquer

P5->Quelques applications immédiates de la formule de Binet (cf P4) donnant un en fonction de n et du nombre d'or :

P5.1->

1) une suite de Fibonacci (aan+bbn) est convergente si et seulement si a=0 :
si a=0 sa limite est 0, si a>0 sa limite est +, si a<0 sa limite est -
2) en excluant le cas a=b=0, si a=0 ou b=0, la suite de Fibonacci est évidemment géométrique (de raison a si b=0, de raison b si a=0)
3) si a0, limn->+un+1/un=a=le nombre d'or,
et un équivalent de un+1/un-a est -(b/a)5(b/a)n.
On a aussi : "kN, limn->+un+k/un=ak

Remarque 1 : dans le cas a0, la limite de la suite (u) étant + ou -, à partir d'un certain rang, un0.

Remarque 2 : un+1/un converge vers a, mais en oscillant autour de ce nombre d'or ; du moins, à partir d'un certain rang assurant que le rapport (un+1/un-a)/ (-(b/a)5(b/a)n) , qui tend vers 1, soit positif.
Pour la suite (F) il y a oscillation autour du nombre d'or à partir du rang 1, pour la suite (L), il y a oscillation à partir du rang 0.
Illustration numérique dans le cas de la suite (F) où a=-b ( cf P4) : l'équivalent de un+1/un-a est alors 5(b/a)n et
pour n=7 on obtient (21/13-a)/(5(b/a)7)=0,9988151...., ce qui donne 21/13-a<0, soit F8/F7=21/13<a, et
pour n=8 on obtient (34/21-a)/(5(b/a)8)=1,000453..., soit cette fois F9/F8=34/21>a.
En fait,on verra à la solution de Q2) de l'exercice 7 le lien entre Fn+1/Fn et le développement en fractions continues du nombre d'or.

Remarque 3 : si u0 et u1 sont des entiers relatifs non nuls tous les deux, a ne peut être nul (a=0 donne u1=-bu0, et comme b n'est pas rationnel cela conduit à u0=u1=0, donc contradiction)

P5.2->

Si u0=0, u1=1, alors, cf P4, a=(1/5), b=-(1/5) et donc
pour tout entier naturel n on a Fn=(1/5)(an-bn) ; c'est bien un entier naturel cf P2.
(Rappel : voir question 6e de l'exercice 1 pour une preuve sans utilisation de la formule de Binet générale)
Et aussi, pour tout entier naturel n non nul, Fn=(1/2n-1)S0p(n-1)/25pCn2p+1
; si n=0, le sigma n'est pas défini puisque dans ce cas n-1/2=-1/2 n'est pas 0.
Ce qui donne, par exemple, F12=(1/211)(C121 +5C123 + 52C125 +53C127 +54C129 +55C1211).
D'où F12=1/(2048)(12+5×220+25×792+125×792+625×220+3125×12)=294912/2048=144 ; évidemment cette faon de procéder est moins rapide que l'application 10 fois de suite de la relation Fn=Fn-1+Fn-2 (voir P1).

Si u0=2, u1=1, alors cf P4, a=(-bu0+u1)/5=(-2b+1)/5=1 et b=(au0-u1)/5=(2a-1)/5=1,
et donc, pour tout entier naturel n on a Ln=an+bn ; c'est bien un entier naturel cf P2.
Et aussi, pour tout entier naturel n, Ln= (1/2n-1)S0pn/25pCn2p
; cette fois, la formule est bien vraie pour n=0.

Une conséquence de ces formules sommatoires est

  • si n est premier impair, Fn 5(n-1)/2 (n)
    Par exemple, F11=89 ≡1 (11) et 55=25×25×5≡3×3×5≡45≡1 (11).
  • si n est premier, Ln 1 (n)
  • On verra au 1) h de P13 une autre conséquence pour la suite (F).

Enfin, une conséquence immédiate des formules de Binet pour les suites (F) et (L) est la jolie formule suivante, formule que l'on pourrait qualifer de formule de Lucas-Fibonacci-Moivre

pour tous les entiers naturels n et p :
((Ln+5Fn)/2)k=(Lkn+5Fkn)/2 et ((Ln-5Fn)/2)k=(Lkn-5Fkn)/2
Une application, est l'obtention de Fkn et Lkn sous forme de polynômes en Fn et Ln.
Par exemple
  • F3n=(3Fn(Ln)2+5(Fn)3)/4
  • L3n=(15Ln(Fn)2+(Ln)3)/4
On verra à la fin du 15) de P.8, une autre façon d'obtenir ces relations.

P5.3->

Si (u) est une suite de Fibonacci définie sur Z (voir P2),
pour tout n dans Z on a u-n=(-1)n+1(un-u0Ln), Ln désignant le terme de rang n de la suite de Lucas (L).

En particulier, si u0=0 (cas de la suite (F)) on a, pour tout n dans Z, u-n=(-1)n+1un et si 2u1=u0 (cas de la suite (L)) on a, pour tout n dans Z, u-n=(-1)nun.

P5.4->

Un peu de trigonométrie hyperbolique!
Les fonctions, de R dans R, sinus hyperbolique, cosinus hyperbolique, tangente hyperbolique sont définies, à l'aide de la fonction exponentielle, ainsi :
sinh(x)=(ex-e-x)/2, cosh(x)=(ex+e-x)/2, tanh(x)=sinh(x)/cosh(x)
.

Et voici le lien avec les suites de Fibonacci.
En posant l=ln(a) a=el, on a cosh(l)=5/2, et

  • F2n=(2/5)sinh(2nl)
  • F2n+1=(2/5)cosh((2n+1)l)
  • L2n=2cosh(2nl)
  • L2n+1=2sinh((2n+1)l)
  • F2n/L2n=tanh(2nl)/5
  • L2n+1/F2n+1=5tanh((2n+1)l)

Remarque : on verra au 15) de P8 une autre façon de relier (F) et (L) aux fonctions hyperboliques : en posant rn=(n/2)ln(α/β) on a

  • √5Fn=2(-1)n/2sinh(rn)
  • Ln=2(-1)n/2cosh(rn)

Exercice 2 :
1) Prouver P5
2) Trouver une formule sommatoire donnant, pour k≥1, n≥0, Lkn en fonction de Ln et Fn et en déduire que si k est impair, Ln divise Lkn.
Attention, on verra au 1.7 de P10 la réciproque de ce résultat lorsque n≥2, et donc si k est pair et n≥2 alors Ln ne divise pas Lkn

vers la solution...chercher avant de cliquer

P6->

P6.1->La fonction génératrice d'une suite (u) de Fibonacci (avec a0 et b0 ; voir P4) est
G(x)=(u0+(u1-u0)x))/(1-x-x2), c'est-à-dire :
pour |x|<|b|=1/a, G(x)=Sn=0+unxn.
En particulier

Remarque :
si b=0, cad si un=aan avec a0, la fonction génératrice est u0/(1-ax) pour |x|<1/a.
si a=0, cad si un=bbn avec b0, la fonction génératrice est u0/(1-bx) pour |x|<a.

P6.2->Fonction génératrice partielle d'une suite (u) de Fibonacci :
pour tout complexe x distinct de -a et -b, pour tout entier naturel on a :

Sk=0nukxk= (u0+(u1-u0)x-un+1xn+1-unxn+2)/(1-x-x2)

Remarque : si x=-a ou -b, le numérateur et le dénominateur de la fraction du membre de droite sont nuls.

Exercice 3 :
1) Prouver P6.1.
2) Prouver P6.2 et retrouver P6.1
3) Montrer que

  • la fonction génératrice de la suite (F2n)(nN), est H(x)=x/(1-3x+x2)
  • la fonction génératrice de la suite (F2n+1)(nN), est K(x)=(1-x)/(1-3x+x2)
  • la fonction génératrice de la suite ((Fn)2)(nN), est L(x)=(x-x2)/((1+x)(1-3x+x2))

4) n étant un entier naturel, q un réel quelconque, exprimer (sans formule sommatoire) en fonction de Ln, Ln+1 et q les deux expressions suivantes
  • Sk=0nLkcos(kq)
  • Sk=0nLksin(kq)
vers la solution...chercher avant de cliquer

Exercice 4
1) Montrer que Sn=1+Fn/2n=2

2) Montrer que Sn=1+nFn/2n=10

3) Montrer que Sn=0+Ln/2n=6

4) Observer le début du développement décimal de 1/89 et donner une explication.
De façon plus précise, montrer que l'ajout de Sk=6+Fk/10k+1 à d=Sk=05Fk/10k+1=0,011235 donne un nombre dont les six premières décimales sont encore celles de d.

5) Observer le début du développement décimal de 1/9899 et donner une explication.
De façon plus précise, montrer que l'ajout de Sk=11+Fk/102k+2 à d=Sk=010Fk/102k+2donne un nombre dont les vingt-deux premières décimales sont encore celles de d.

vers la solution...chercher avant de cliquer


P7-> Quelques relations linéaires entre les suites de Fibonacci (F) et (L).
1) pour tout entier naturel n, Fn+Ln=2Fn+1
Remarque :

cette relation se généralise en
pour tout n et tout p dans Z, 2Fn=Fn-pLp+Ln-pFp : voir 15.7 de P8.
C'est bien une généralisation car pour p=1 on obtient Fn-1+Ln-1=2Fn

2) pour tout entier naturel n≥1, Fn-1+Fn+1=Ln, qui s'écrit aussi 2Fn-1+Fn=Ln

3) pour tout entier naturel n≥1, Ln-1+Ln+1=5Fn

4) pour tout entier naturel n, Fn+Fn+1+Fn+2+Fn+3=Ln+3

5) pour tout entier naturel n, S0in2iLi=2n+1Fn+1.

Remarque : on verra à l'exercice 12 ci-dessous les formules donnant kFn sous forme d'une somme (Z_somme) de termes distincts et non consécutifs de la suite (F), F0 et F1 étant exclus.
Par exemple 6Fn=Fn-4+Fn+1+Fn+3, pour n6. En fait cette formule est aussi valable pour n=4 et n=5, mais ce n'est plus alors, formellement, une Z_somme.

Exercice 5 : prouver P7,...sans utiliser Binet.

vers la solution...chercher avant de cliquer


P8-> Encore des relations, mais cette fois non linéaires (et pour ceux qui souhaiteraient en découvrir des tas d'autres voir ce lien où on y trouvera pas moins de 200 formules, mais sauf erreur de ma part, on ne trouvera pas, notamment, la 9 ci-dessous) : 1) (u) étant une suite de Fibonacci quelconque, pour tout entier naturel n1, on a la relation (un)2-un-1un+1=(-1)n((u0)2-(u1)2+u0u1).
Remarque : ((u0)2-(u1)2+u0u1)=(au0-u1)(-bu0+u1)=5ab où a et b sont ceux définis à P4.

(F) étant la suite de Fibonacci telle que F0=0, F1=1, et (L) celle telle que L0=2, L1=1, on a

2) pour tout entier naturel n1, (Fn)2-Fn-1Fn+1=(-1)n-1 : Cassini Jean Dominique ; on retrouve alors que Fn et Fn-1 sont premiers entre eux : voir exercice 1, P10.

cette formule (qui a été retrouvée par Simson Robert, voir 6 ci-dessous) est généralisée par la formule de Catalan Eugène Charles :
pour tout entier naturel n, pour tout entier naturel p, avec np, on a :
(Fn)2-Fn-pFn+p=(-1)n-p(Fp)2.

Le cas p=0 donne 0=0, mais le cas p=1 redonne la formule ci-dessus.

3) pour tout entier naturel n, (Fn)2+(Fn+1)2=F2n+1
    Remarque : il n'existe pas de fonction h de N dans N telle que pour tout entier naturel on ait (Fn)2+(Fn+1)2+(Fn+2)2=Fh(n), cad on ne peut pas linéariser (Fn)2+(Fn+1)2+(Fn+2)2.

    pour tout entier naturel n1, (Fn)2+(Fn+1)2=Fn-1Fn+1+FnFn+2

4) pour tout entier naturel n1, (Fn+1)2-(Fn)2=Fn+2Fn-1

   pour tout entier naturel n, (Fn+1)2-(Fn)2=(L2n+1+4(-1)n))/5 ; donc L2n+1(-1)n (5) ; par exemple L7=29 et 29-(-1) est bien divisible par 5.

5) pour tout entier naturel n2, Fn-2Fn+2=Fn-1Fn+1+2(-1)n-1

6) pour tout entier naturel n2, (Fn)4=1+Fn-2Fn-1Fn+1Fn+2 : Simson (Robert : c'est celui de la droite de Simson, pas confondre avec Simpson Thomas associé à une formule approchée d'intégrale)

Remarque : on déduit tout de suite de cette formule que Fn et Fn+2 sont premiers entre eux. Voir aussi P10.

7) pour tout entier naturel n, 5(Fn)2+4(-1)n=(Ln)2=L2n+2(-1)n et 5(Fn)2+(Ln)2=2L2n ;
donc 5(Fn)2+4(-1)n est un carré parfait et aussi (Ln)2(-1)n+1 (5)

Remarque 1 : il "semblerait" que la relation 5(Fn)2+4(-1)n=(Ln)2 <=> (Ln)2-5(Fn)2=4(-1)n soit la seule identité algèbrique reliant Fn et Ln.

Remarque 2 : cette relation (Ln)2-5(Fn)2=4(-1)n prouve que Ln et Fn ont même parité : voir question 6c) de l'exercice 1 où on montre que Fn est pair <=> Ln est pair <=> n divise 3.

Remarque 3 : pour n impair on a donc (Ln)21 (5), ce qui est cohérent avec la relation de congruence du 4) ci-dessus.

Remarque 4 : on verra au chapitre 12 la résolution de l'équation diophantiene x2-5y2=±4.

8) pour tout entier naturel n, F2n=Fn(5(Fn)2+4(-1)n)1/2=FnLn ; donc pour tout entier naturel n1, Fn divise F2n. Cet aspect sera généralisé à P10.

Remarque 1 : pour n1, comme Ln=Fn+1+Fn-1 (cf P7), on en déduit F2n=Fn(Fn-1+Fn+1)=Fn(Fn+2Fn-1) et aussi (Lucas) F2n=(Fn+1-Fn-1)(Fn+1+Fn-1)=(Fn+1)2-(Fn-1)2.

Remarque 2 : quant F2n+1, les formules qui se "rapprochent" le plus de F2n=FnLn sont
F2n+1=Fn+1Ln+(-1)n+1 et F2n-1=Fn-1Ln+(-1)n+1 : voir la relation 15.7 de 15) ci-dessous.

9) pour tout entier naturel n, F8n=F4n(5(F2n)2+2)

10) pour tous les entiers naturels n et p (p non nul pour la 1ère égalité, n et p non nuls pour la 2ième), Fn+p=Fn+1Fp+FnFp-1=Fn+1Fp+1-Fn-1Fp-1

Remarque 1 : la 1ière égalité est en fait un cas particulier de la relation un+p=Fp-1un+Fpun+1 vue au 6) de P3, (u) étant une suite de Fibonacci quelconque.

Remarque 2 : on déduit de la 1ière égalité que,
pour tous les entiers naturels n et p, si d divise Fn et Fp, alors d divise Fn+p.
Voir la remarque de la relation 12 ci-dessous pour Fn-p.

11) pour tous les entiers naturels n, p, a , b (de telles sortes que tous les indices soient positifs ou nuls),
FnFp-Fn+aFp-a=(-1)b(Fn-bFp-b-Fn-b+aFp-b-a)

12) pour tous les entiers naturels n et p (avec np) on a FnFp+1-FpFn+1=(-1)pFn-p (Ocagne Philibert Maurice)

et aussi FnLp-FpLn=2(-1)pFn-p (on retrouvera cette relation au 15) ci-dessous avec une autre démonstration).
Cas particulier : pour tout entier naturel p, Fp+1Lp-FpLp+1=2(-1)p.

Remarque : on déduit de la relation d'Ocagne que,
pour tous les entiers naturels n et p, avec n≥p, si d divise Fn et Fp, alors d divise Fn-p.
Voir la remarque 2 de la relation 10 ci-dessus pour Fn+p.

13) pour tout entier naturel n1, S1k nF2k-2F2k-1+F2k-1F2k=(F2n)2

14) pour tout entier naturel n1, S1k n(Fk)2=FnFn+1.
Bien entendu la sommation peut commencer à k=0, et alors elle est vraie pour n≥0, puisque F0=0.
En fait cette relation a déjà été vue à la question 3 de l'exercice 1 où on donne la cns (lorsque la sommation commence à k=0) pour qu'une suite de Fibonnacci vérifie cette relation.

15) On a déjà vu à P5.4 un lien entre les suites (F) et (L) et la trigonométrie hyperbolique. On peut aller plus loin :
les relations 5(Fn)2-(Ln)2=4(-1)n+1, 5(Fn)2+(Ln)2=2L2n (voir 7) ci-dessus) et F2n=FnLn (voir 8) ci-dessus) rappellent (ou peuvent rappeler..) les relations cosh2(x)-sinh2(x)=1, cosh2(x)+sinh2(x)=cosh(2x), sinh(2x)=2sinh(x)cosh(x), valables pour tout réel x. On peut alors y voir une certaine analogie entre Fn et sinh(x), et entre Ln et cosh(x).
Effectivement, en posant rn=(n/2)ln(α/β) (on notera que rkn=krn), on a

  • √5Fn=2(-1)n/2sinh(rn)
  • Ln=2(-1)n/2cosh(rn)

Cela se démontre de façon immédiate en utilisant cosh(x)=(exp(x)+exp(-x))/2 et sinh(x)=(exp(x)-exp(-x))/2 et les formules de Binet.
On retrouve (voir le 7 ci-dessus) alors
  • 5Fn2-Ln2=4(-1)n(sinh2(rn)-cosh2(rn))=4(-1)n
  • 5Fn2+Ln2=4(-1)n(sinh2(rn)+cosh2(rn))=4(-1)ncosh(2rn)=4(-1)ncosh(r2n)=2L2n

Il devrait donc être possible de calculer Fm+n, Lm+n en fonction de FmFn, LmLn, FmLn, LmFn. Effectivement :
pour tout m et tout n dans Z on a -> 15.1 : Fm+n=(FmLn+LmFn)/2 ;
  • m=n donne F2n=FnLn qui est la 8) ci-dessus

-> 15.2 : Lm+n=(5FmFn+LmLn)/2 ;
  • m=n donne L2n=(5(Fn)2+(Ln)2)/2 qui est une des relations du 7) ci-dessus

-> 15.3 : Fm-n=(-1)n(FmLn-LmFn)/2 ;
  • m=n donne ... 0=0

-> 15.4 : Lm-n=(-1)n(LmLn-5FmFn)/2 ;
  • m=n donne 4=(-1)n((Ln)2-5(Fn)2) qui est une des relations du 7) ci-dessus

-> 15.5 : FmFn=(Lm+n+(-1)n+1Lm-n)/5
;
  • n=1 donne Fm=(Lm+1+Lm-1)/5 qui est la 3) de P7
  • m=n donne (Fn)2=(L2n+2(-1)n+1)/5 qui est une des relations du 7) ci-dessus
  • en changeant m en n-p et n en p, on obtient
    5Fn-pFp=Ln+(-1)p+1Ln-2p, soit pour tout n et tout p dans Z, Ln=5Fn-pFp+(-1)pLn-2p

-> 15.6 : LmLn=Lm+n+(-1)nLm-n ;
  • m=n donne (Ln)2=L2n+2(-1)n, qui est une des relations du 7) ci-dessus, et on peut vérifier, en utilisant P5.3, que si on échange m et n, le membre de droite est invariant (idem, pour ce dernier aspect, pour la relation ci-dessous).
  • m=2n donneL3n=(L2n+(-1)n-1)Ln, relation qui apparaît pour la 1ière fois dans cette page ; compte-tenu du 7) ci-dessus elle s'écrit L3n=((Ln)2+3(-1)n+1)Ln, ou (Ln)3=L3n+3(-1)nLn
  • m=n+1 donne Ln+1Ln=L2n+1+(-1)n
  • en changeant m en n-p et n en p, on obtient
    Ln-pLn=Ln+(-1)pLn-2p, soit pour tout n et tout p dans Z, Ln=Ln-pLp+(-1)p+1Ln-2p

-> 15.7 : FmLn=Fm+n+(-1)nFm-n
;
  • m=n donne FnLn=F2n qui est la 8) ci-dessus
  • m=2n donneF2nLn=F3n+(1)nFn, mais F2nLn=Fn(Ln)2, soit cf le 7), F2nLn=Fn(4(-1)n+5(Fn)2)et finalement F3n=(5(Fn)2+3(-1)n)Fn, relation qui apparaît pour la 1ière fois sur cette page et qui s'écrit aussi (Fn)3=(F3n-3(-1)nFn)/5
  • m=n+1 donne Fn+1Ln=F2n+1+(-1)n
  • m=n-1 donne Fn-1Ln=F2n-1+(-1)n, car F-1=F1=1
  • en changeant m en n-p et n en p, on obtient
    Fn-pLp=Fn+(-1)pFn-2p, soit pour tout n et tout p dans Z, Fn=Fn-pLp+(-1)p+1Fn-2p
  • en changeant m en p et n en n-p, on obtient
    FpLn-p=Fn+(-1)n-pF2p-n, soit pour tout n et tout p dans Z, Fn=Ln-pFp+(-1)pFn-2p, car par ailleurs, F2p-n=F-(n-2p)=(-1)n-2p+1Fn-2p, cf P5.3, et (-1)-3p=(-1)p.
  • L'ajout membre à membres de ces deux dernières relations donne
    pour tout n et tout p dans Z, 2Fn=Fn-pLp+Ln-pFp, relation qui redonne pour p=1 la relation 1) de P7.

16) Les sept formules (celles avec m et n) du 15) ci-dessus permettent de linéariser de faon systématique les puissances de Fn ou de Ln, et de calculer Fkn ou Lknen fonction de Fn et de Ln.

Pour (Fn)2, (Ln)2, (Fn)3, (Ln)3, F2n, L2n, voir ci-dessus (cas particuliers de 15.5, 15.6, 15.7) ; pour la linéarisation de (Fn)3 et (Ln)3 on verra une autre preuve dans la solution de l'exercice 6.

On a aussi, par exemple, pour tout n dans Z (en fait les deux formules ci-dessous ont déjà été obtenues à la fin de P5.2, via la formule de Lucas-Fibonacci-Moivre)

  • F3n=(3Fn(Ln)2+5(Fn)3)/4
  • L3n=(15Ln(Fn)2+(Ln)3)/4
Mais en utilisant la relation 7), Ln2=5Fn2+4(-1)n, ces deux formules deviennent
  • F3n=Fn(Ln2-(-1)n)
  • L3n=Ln(5Fn2+(-1)n)

Petit récapitulatif de ce qui vient d'être vu pour F3n et L3n :

  • F3n=Fn(5Fn2+3(-1)n)=Fn(Ln2-(-1)n)
  • L3n=Ln(Ln2-3(-1)n)=Ln(5Fn2+(-1)n)

Remarque : on verra à P15 une généralisation : il existe des polynômes Qk,n et Rk,nà coefficients entiers tels que

  • Fkn=Qk,n(Fn), pour k impair
  • Lkn=Rk,n(Ln), que k soit impair ou pair

Exercice 6 : prouver P8, et par application du 9), donner la valeur exacte de F64.
Enfin, montrer, en utilisant essentiellement la relation 10, et non la relation 12, que pour tous les entiers naturels n et p, si d divise Fn et Fp alors d divise Fn-p.

vers la solution...chercher avant de cliquer

Et deux exercices sur la sommation de séries
dont le terme général est l'inverse d'un terme d'une suite de Fibonacci ou le produit de deux de ces termes

Tout d'abord quelques remarques sur ∑n≥11/Fn.
Cette série est évidemment convergente puisque (cf β=-1/α)
0<1/Fn=√5/(αn(1+(-1)n+1n)), dont un équivalent, lorsque n tend vers +∞, est √(5)(1/α)n, terme général d'une série géométrique convergente, cf |1/α|<1.
Toujours à l'aide des séries géométriques, on obtient la majoration suivante : n≥01/Fn <(3√5+5)/2<5.855.

En effet,
pour n≥1 impair 1/(1+(-1)n+1n)=1/(1+1/αn)<1
pour n≥1 pair 1/(1+(-1)n+1n)=1/(1-1/αn)≤1/(1-1/α2)=α2/(α+1-1)=α
Donc, 1/Fn<√5/αn si n impair et 1/Fn≤√5/αn-1 si n pair.
Comme 1/αn<1/αn-1, ∑n≥11/Fn<∑n≥1√5(1/α)n-1=√5/(1-1/α)=(3√5+5)/2,
(puisque pour |x|<1, 1/(1-x)=1+x+x2+x3+......... ).

En fait, cf le site wiki, ∑n≥11/Fn≈3.35988566...

Et dans l'ouvrage Théorie des nombres de Daniel Duverney , on trouve l'exercice 5.22 qui propose un cheminement pour prouver que
n≥11/Fn n'est pas dans Q(√5), donc n'est pas rationnel.
Il est donc, "à mon avis" illusoire de chercher une formule "simple" pour ∑n≥11/Fn.

Cependant on a n≥11/F2n=√5(L(α-2)-L(α-4)), où L(x)=∑n≥1xn/(1-xn) est la somme de la série dite de Lambert, somme définie pour |x|<1.

En effet,
n≥11/F2n=√5(∑n≥11/(α2n2n)), et puisque β2n=(-1/α)2n=1/α2n,
n≥11/F2n=√5(∑n≥1α2n/(α4n-1))
n≥11/F2n=√5(∑n≥1α-2n/(1-α-4n))=√5(∑n≥1α-2n/(1-α-2n)-α-4n/(1-α-4n)).
note : la série de Lambert est absolument convergente pour |x|<1, car la valeur absolue de son terme général est équivalente à |x|n.
Par contre, puisque β2n+1=-1/α2n+1, on a n≥01/F2n+1=√5(∑n≥1α2n+1/(α4n+2+1)).

Voir cependant ci-dessous des résultats très simples pour la sommation des 1/(1+F2n+1) (exercice 7) et pour la sommation de 1/F2+1/F4+1/F8+1/F16+1/F32+... (exercice 8).

Exercice 7
1) (u) étant une suite de Fibonacci quelconque mais avec a0 et b0, il existe (voir P5.1) un rang k0 à partir duquel un0.
Montrer alors

a) la série de terme général wn=(-1)n-1/(unun+1), pour nk, est absolument convergente et sa somme est Su=C(uk+1/uk-a), où C est une constante que l'on précisera en fonction de u0 et u1 ; on pourra utiliser, pour ce dernier aspect, le 1) de P8.
b) En déduire que
  • Sn=1+ (-1)n-1/(FnFn+1)=a-1=(√5-1)/2

  • Note :
    cf la 14) de P8, on a donc ∑n≥1 (-1)n-1/(∑j=1n Fj2)=(√5-2)/2.
  • Sn=0+ (-1)n-1/(LnLn+1)=(1-2a)/10=-√5/10.
2) Si le lecteur connaît la notion de développement en fractions continues (dfc), il peut essayer de retrouver la 1ière formule du 1)b en utilisant le fait que le dfc du nombre d'or α est constitué que de 1.

3) Montrer que Sn=1+ 1/(FnFn+2)=1. (Ecrire 1/(FnFn+2) sous la forme vn-vn+1).

4) Montrer que

  • Sn=1+ 1/(F2nF2n+2)=a-1=(3-5)/2
  • Sn=0+ 1/(F2n+1F2n+3)=(5-1)/2
On remarquera que par ajout membres à membres on retrouve bien le résultat du 3).
Pour la preuve de ces deux derniers résultats (via dfc), je renvoie à l'ouvrage Théorie des nombres de Daniel Duverney (exercice 4.16).

5) Montrer que n=0+∞ 1/(1+F2n+1)=√5/2.
Aide : montrer que cette somme n'est autre que 1/2+∑n=0+∞ 1/(F2n+1F2n+3)!

vers la solution...chercher avant de cliquer

Exercice 8 :
attention : dans cet exercice F(n) désignera Fn: je suis obligé d'utiliser cette notation, car imbriquer indice et puissance en html ne fonctionne pas avec tous les navigateurs, et cet exercice est entièrement relatif à des indices qui sont des puissances de 2.

1) q étant un entier naturel non nul, montrer que Sk=1+ (F(2q))/(F(2q+k))=1/(ae), avec e=2q.
Bien entendu, on remarque tout de suite que le membre de gauche peut être factorisé par F(2q), mais cela n'apporte rien pour la démonstration.
Pour cette démonstration, on pourra utiliser la relation 11 de P8.

2) cas q=0 : montrer que Sk=1+ 1/(F(2k))=-5b=(5-5)/2 (Lucas).
Pour arriver à ce résultat, on pourra montrer que
pour tout K≥1 on a ∑k=1K 1/F(2k)=2-F(2K-1)/F(2K).

Remarque : on a aussi les relations
Sk=1+ 1/(F(m2k))=5/(a2m-1), m entier naturel non nul ; m=1 redonne le 2) ci-dessus puisque a2-1=a=-1/b.

Sk=1+ (F(m))/(F(m2k))=1/(am), si m pair ; m=2q redonne le 1)ci-dessus.

Sk=1+ (L(m))/(F(m2k))=5/(am), si m impair

vers la solution...chercher avant de cliquer


P9->
1) "nN-{0;1}, Fn+1=E(a(Fn+1))-1, E(x) désignant la partie entière du réel x, c'est-à-dire le plus grand entier relatif inférieur ou égal à x.

Remarque : cette égalité, fausse pour n=0, n=1, est la relation "rigoureuse" correspondant au fait que pour n grand, Fn+1@aFn (puisque limn->+Fn+1/Fn=a, cf voir P5.1) ; on peut d'ailleurs retrouver cette limite à partir de cette relation.

Exemple : F12=144, donc F13=E(145a)-1=E(234,614...)-1=233 (qui est bien F12+F11), puis F14=E(234a)-1=E(378,61...)-1=377.

On a aussi

2) pour tout entier naturel n, Fn est l'entier le plus proche de an/5

3) pour tout entier naturel n2, Ln est l'entier le plus proche de an

Exercice 9 : prouver P9.

vers la solution...chercher avant de cliquer


P10-> Sur pgcd et suites (F), (L), algorithme d'Euclide.

Rappel : pour tout a et tout b dans Z (pas tous les deux nuls), pgcd(a,b)=pgcd(|a|,|b|)>0.
Comme F-n et Fn sont les mêmes au signe près, de même que L-n et Ln (voir P5.3), les énoncés ci-dessous se limitent à des indices positifs ou nuls.

1) n et p étant des entiers naturels,

1.1) pgcd(Fn,Fp)=pgcd(Fn,Fn+p), n et p n'étant pas tous les deux nuls

1.2) pgcd(Fn,Fp)=Fpgcd(n,p), n et p n'étant pas tous les deux nuls

application :
on retrouve (voir exercice 1 ou relation 2 de P8) que Fn et Fn+1 sont premiers entre eux car leur pgcd est Fpgcd(n,n+1)=F1=1, et aussi,
on retrouve (voir relation 6 de P8) que Fn et Fn+2 sont premiers entre eux car leur pgcd est Fpgcd(n,n+2) et pgcd(n,n+2)=1 (si n impair) ou 2 (si n pair) et F1=F2=1.

Remarque 1 : certes, la 2ième relation redonne pgcd(Fn,Fn+1)=1, mais en fait on a besoin de ce résultat pour prouver ces deux relations sur pgcd(Fn,Fp) : donc on ne peut pas dire que la 2ime relation est une autre preuve du fait que Fn et Fn+1 soient 1er entre eux.

Remarque 2 : (F) n'est pas la seule suite d'entiers à vérifier cette propriété : voir remarque 1 de P4.

1.3) p étant non nul, si p divise n, alors Fp divise Fn, cad
pour tout p dans N*, tout k dans N, Fp divise Fkp.

Sans recours au pgcd, cette propriété a déjà prouvée au 7) de P3 et à la question 9 de l'exercice 1.
Lorsque k=2, le quotient de cette division est Lp : voir la relation 8 de P8.
En fait, d'une façon plus générale, on verra à P15 que si k est pair Fkn=LnFnP(Fn), avec P polynôme à coefficients entiers, alors que si k est impair, Fkn=FnP(Fn), avec P polynôme à coefficients entiers.
1.4) Réciproquement pour p3, n dans N, si Fp divise Fn, alors p divise n.
Ceci est évidemment faux si p=2, car F2=1 divise F2k+1 et 2 ne divise pas 2k+1 ; pour p=1, F1=1 et le résultat est trivialement vrai. Quant au cas p=0, il est sans objet puisque F0=0.

1.5) Si n est distinct de 4 et si Fn est un nombre premier, alors n est aussi un nombre premier.
Par exemple, F3, F5, F7, F11, F13, F17 sont premiers et 3, 5, 7, 11, 13, 17 sont bien premiers ; et bien sûr, F4 est premier et pas 4, ce qui explique le n≠4 dans l'hypothèse.
La réciproque est fausse puisque F19 n'est pas premier (4181=37×113).

1.6) pgcd(Ln,Lp), n et p étant deux entiers naturels :
si n≠0, on note n=2an' avec a≥0, n' impair
si p≠0, on note p=2bp' avec b≥0, p' impair
si n et p pas tous les deux nuls, on note d=pgcd(n,p)

  • Cas où au moins un des indices est nul
    • pgcd(Ln,L0)=1 si 3 ne divise pas n (cad Ln impair)
    • pgcd(Ln,L0)=2 si 3 divise n (cad Ln pair ; c'est le cas si n=0)
  • Cas où n≥1 et p≥1
    • si n/d ou p/d pair (<=> a≠b) alors
      • pgcd(Ln,Lp)=1 si 3 ne divise pas d
      • pgcd(Ln,Lp)=2 si 3 divise d
    • si n/d et p/d impairs (<=>a=b) alors
      pgcd(Ln,Lp)=Ld

Conséquences :
1) pour n≥1 et p≥1,
Ln et Lp sont premiers entre eux <=> [n/d ou p/d est pair et 3 ne divise pas d] ou [n et p sont premiers entre eux et impairs]

Rappel : Ld=1 <=> d=1.
2) On retrouve (voir exercice 1, question 2), que pour tout entier naturel n, Ln et Ln+1 sont premiers entre eux En effet, c'est trivial si n=0 et pour n≥1, puisque d=pgcd(n,n+1)=1 et n/d=n ou (n+1)/d=n+1 est pair et que 3 ne divise pas d=1, c'est que pgcd(Ln,Ln+1)=1. 3) On retrouve aussi (voir exercice 2, question 2) évidemment le fait que si k et p sont des entiers naturels, avec k impair et p≥0, Lp divise Lkp : si p=0 c'est trivial, si p≥1 c'est parceque pgcd(kp,p)=p et kp/p, p/p sont impairs donc pgcd(Lkp,Lp)=Lp.
4) En fait on a la réciproque :
pour n≥1 et p≥2, Lp divise Ln <=> p divise n et n/p impair
et donc si k et p sont des entiers naturels avec k pair et p≥2 alors Lp ne divise pas Lkp
.

1.7) pgcd(Ln,Fp), n et p étant deux entiers naturels :
si n≠0, on note n=2an' avec a≥0, n' impair
si p≠0, on note p=2bp' avec b≥0, p' impair
si n et p pas tous les deux nuls, on note d=pgcd(n,p)

  • Cas où au moins un des indices est nul
    • pgcd(Ln,F0)=Ln
      • pgcd((L0,Fp)=1 si 3 ne divise pas p (cad si Fp est impair)
      • pgcd((L0,Fp)=2 si 3 divise p (cad si Fp est pair)
  • Cas où n≥1 et p≥1
    • si p/d impair (<=> b≤a) alors
      • pgcd(Ln,Fp)=1 si 3 ne divise pas d
      • pgcd(Ln,Fp)=2 si 3 divise d
    • si p/d pair (<=> b>a) alors
      pgcd(Ln,Fp)=Ld
Cas particulier n=p
si n=p=0 le pgcd est L0=2
si n=p≥1, d=n et p/d=1 est impair, donc le pgcd est 1 si 3 ne divise pas n, et 2 si 3 divise n.
Ceci se résume en :
si n≥0
  • pgcd(Ln,Fn)=1 si 3 ne divise pas n
  • pgcd(Ln,Fn)=2 si 3 divise n.

1.8) pour k et n dans N*,

  • pgcd(Fkn/Fn,Fn)=pgcd(k,Fn) si k est impair ou si k est pair et 3 divise n
  • pgcd(Fkn/Fn,Fn)=pgcd(k/2,Fn) si k est pair et 3 ne divise pas n
Conséquence : pour k et n dans N*, pgcd(Fkn/Fn,Fn) divise k.

Rappel : Fn pair <=> Ln pair <=> 3 divise n .

Remarque : la conséquence ci-dessus est le point de départ de Mansur S. Boase pour prouver que
si n≥3, n≠6; n≠12, alors il existe p premier divisant Fn et ne divisant aucun des Fp pour 1≤k≤n-1.
On en déduit facilement que
si n≥2, n≠3; n≠6, alors il existe p premier divisant Ln et ne divisant aucun des Lp pour 0≤k≤n-1
Note : Mansur S.Boase n'évoque pas le fait que pgcd(Fkn/Fn,Fn) est égal à pgcd(k,Fn) ou à pgcd(k/2,Fn), et donc il me semble qu'au moment où j'écris ces lignes (janvier 2013), ce résultat est inédit.

2) Soit n un entier naturel non nul : l'algorithme d'Euclide appliqué à la recherche de pgcd(Fn+1,Fn+2) (on sait que ce pgcd est égal à 1 cf le 1.2 ci-dessus) prend exactement n itérations (cad n divisions).

3) Théorème de Lamé : le plus petit entier naturel a2 pour lequel il existe un plus petit entier b (ab1) tel que l'algoritme d'Euclide appliqué à la recherche de pgcd(a,b) demande exactement n itérations est Fn+2 ; dans ce cas b=Fn+1.

4) Soient a et b deux entiers naturels tels que ab1 et n le nombre d'itérations de l'algorithme d'Euclide pour obtenir leur pgcd.
Alors nmin(lnb/lna+1,lna/lna)
; ce min est égal à lnb/lna+1b<a/a.

Remarque 1 : cf par exemple la revue APMEP n445, le mathématicien franais Gabriel Lamé a été le premier à établir une majoration de n :
n≤M1=5 fois le nombre de chiffres décimaux de b.
En fait le résultat 4) de P10 permet non seulement de retrouver cette majoration de Lamé, mais il permet aussi de l'améliorer : si b a au moins cinq chiffres, n≤M1-1.
Pour prouver cela, posons M2=lnb/lnα+1.
Puisque n≤M2 et que n est un entier, c'est qu'en fait n≤E(M2), E désignant la fonction partie entière.
On a alors le résultat suivant :

  • si b a au plus quatre chiffres, n≤E(M2)≤M1
  • si b a au moins cinq chiffres, n≤E(M2)≤M1-1
preuve :
Soit p≥1 le nombre de chiffres de b : M1=5p et puisque 10p-1≤b<10p, c'est que M2 est dans [(p-1)ln10/lnα+1;pln10/lnα+1[.
On note que ln10/lnα=4.784...
Evidemment puisque n≤M2<pln10/lnα+1<5p+1, on a n<5p+1, soit n≤5p=M1.
Mais on peut faire mieux.
  • si 1≤p≤4
    pln10/lnα+1<5p+1 (ceci est vrai en fait pour tout p≥1)
    et 5p<pln10/lnα+1 puisque p(5-ln10/lnα)<p(5-4.78)≤4×0.22<1.
    Donc 5p est le plus grand entier inférieur strictement à pln10/lnα+1.
    Or E(M2)≤M2<pln10/α+1, donc E(M2)≤5p=M1.
  • si p≥5
    pln10/lnα+1<5p car p(5-ln10/lnα)≥5(5-4.79)=1.05>1.
    Donc M2<M1 et E(M2)≤M1-1, puisque E(M2)≤M2<M1.

Remarque 2 : on verra aussi dans l'article AMEP cité en début de la remarque 1, que si a et b sont deux entiers naturels tels que ab1 et si n est le nombre d'itérations de l'algorithme d'Euclide pour obtenir leur pgcd, alors apgcd(a,b)Fn+1.

Exercice 10 : prouver P10 (pour prouver 1.8 on pourra utiliser le 2) de P15)

vers la solution...chercher avant de cliquer

Exercice 11 : montrer que les seuls termes de la suite (F) qui soient des puissances entières de 3 sont F1=F2=1 et F4=3.

vers la solution...chercher avant de cliquer


P11->
1) Théorème de Hogatt :
tout entier naturel non nul est somme de termes distincts de la suite (F), les termes F0 et F1 étant exclus.
Par exemple 4=F2+F4, 5=F3+F4=F5, 8=F4+F5=F6, 9=F4+F6.

2) Théorème de Zeckendorf :
tout entier naturel e non nul est somme de termes distincts et deux à deux non consécutifs de la suite (F), les termes F0 et F1 étant exclus, et cette écriture est unique, à l'ordre près.

Cette somme sera dite la Z_somme de e.
Pour la trouver on procéde ainsi (
comme lors de l'exercice 8, j'utiliserai parfois la notation F(n) pour Fn, car le double indicage en html ne fonctionne pas avec tous les navigateurs) :

  • on cherche le plus grand terme, F(n1), de la suite (F) qui soit e :
  • on cherche le plus grand terme, F(n2), de la suite (F) qui soit e-F(n1)
  • on cherche le plus grand terme, F(n3), de la suite (F) qui soit e-F(n1)-F(n2)
  • etc, jusqu'à arriver à e-F(n1)-F(n2)-...-F(nn-k-1)=F(nk)
La Z_somme de e est alors e=F(n1)+F(n2)+...F(nn-k-1)+F(nk).

On peut écrire e en base de Fibonacci, cad e="ajaj-1...a1a0", avec j=n1-20, aj=1, et pour tout i{0;1;...;j}, ai=1 si et seulement Fi+2 est dans la Z_somme de e sinon ai=0.
Cette écriture en base de Fibonacci comporte n1-2+1=n1-11 chiffres, et entre deux 1, il y a toujours au moins un 0, puisque dans une Z_somme, il n'y a pas deux termes consécutifs de la suite (F).

Exemples :
la Z_somme de 99 est F11+F6+F3=89+8+2, donc 99="1000010010" (il y a 11-1=10 chiffres)
La Z_somme de 211 est F12+F10+F6+F4+F2=144+55+8+3+1, donc 211="10100010101" (il y a 12-1=11 chiffres).

Remarque 1 : Zeckendorf   Edouard (Belge) a découvert ce théorème en 1939.
En 1960 David E.Daykin a prouvé que la seule suite vérifiant ce théorème est la suite (F).

Remarque 2 : on peut définir sur N* l'opération interne suivante :

si e et e' sont deux entiers naturels non nuls, de Z_sommes respectives
F(n1)+F(n2)+...+F(nn-k-1)+F(nk) et F(n'1)+F(n'2)+...+F(n'n-k'-1)+F(n'k')
alors on pose e*e'=S1ikS1jk'F(ni+n'j), expression qui n'est pas forcément, telle quelle, une Z_somme.
Exemples :
pour n et p entiers naturels 2, Fn*Fp=Fn+p
2*4=F3*(F4+F2)=F7+F5=18
(F2+F6)*(F4+F8)=F6+F10+F10+F14 (ce n'est pas une Z_somme)=F6+F8+F11+F14
2*(5+5)=F3*(F3+F6)=F6+F9=42 ; 2*5+2*5=F3*F5+F3*F5=F8+F8=42 : sur cet exemple la distributivité de * par rapport à + est vérifiée. De là à ce que cela soit toujours vrai est autre chose! Pour l'instant je ne dispose d'aucune certitude sur cette question. Voir aussi, à ce sujet, la 2ième question de l'exercice 13 ci-dessous.

Cette opération * est cependant commutative (évident), mais aussi associative (dû à Donald E.Knuth).

3) Soient

e un entier naturel non nul tel que le plus petit terme de sa Z_d, noté fe, soit 2
K un entier tel que 1K<fe
e'=e-K et fe' le plus petit terme de sa Z_d
alors fe'2K

Exemple : si e=11=8+3 alors fe=3

soit K=1 et e'=10=8+2 et fe'=22K
soit K=2 et e'=9=8+1 et fe'=12K
mais si K=fe=3, e'=8=fe' qui e'est pas 2K
de même, si K=0, e'=e, fe'=fe qui n'est pas2K

Remarque 1 : si fe=1, il n'existe aucun entier K tel que 1K<fe. Si on remplace K<fe par Kfe , la seule possibilité pour K est K=1 ; mais, par exemple, pour e=13+1 (on a bien fe=1), en prenant K=1 on obtient e'=e-1=13=fe' qui n'est pas 2K.

Remarque 2 : cette propriété sera à la base de l'élaboration d'une stratégie gagnante dans le jeu de Nim-Fibonacci.

Exercice 12 : prouver P11.
Aide : pour le 2) on pourra démontrer le résultat intermédiaire suivant :

Soit S une somme de termes distincts, deux à deux non consécutifs de la suite (F), F0 et F1 exclus ; en notant Fj le plus grand de ces termes, alors on a S<Fj+1.
vers la solution...chercher avant de cliquer
Exercice 13 :

1) prouver les Z_sommes ci-dessous :

kZ_somme de kFn
pour ns
s
1Fn2
2Fn-2+Fn+14
3Fn-2+Fn+24
4Fn-2+Fn+Fn+24
5Fn-4+Fn-1+Fn+36
6Fn-4+Fn+1+Fn+36
7Fn-4+Fn+46
8Fn-4+Fn+Fn+46
9Fn-4+Fn-2+Fn+1+Fn+46
10Fn-4+Fn-2+Fn+2+Fn+46
11Fn-4+Fn-2+Fn+Fn+2+Fn+46
12Fn-6+Fn-3+Fn-1+Fn+58
13Fn-6+Fn-3+Fn+1+Fn+58
14Fn-6+Fn-3+Fn+2+Fn+58
15Fn-6+Fn-3+Fn+Fn+2+Fn+58

Remarque : en fait les formules sont vraies dès que tous les indices sont positifs ou nuls, mais ce ne sont plus forcément des Z_sommes, puisque F0 ou F1 peuvent apparaître ; et même elles sont vraies pour tout n dans Z, si on prolonge la suite (F) pour tout indice dans Z- : voir remarque de P2.

2) * étant l'opération définie à la remarque 2 du 2) ci-dessus, vérifier que :

  • (2Fp)*(3Fq)=6(Fp*Fq), pour p et q à préciser
  • (3Fp)*(5Fq)=15(Fp*Fq), pour p et q à préciser
vers la solution...chercher avant de cliquer

P12->
1) Pour tout entier naturel n 2, le triplet (Fn-1Fn+2, 2FnFn+1, F2n+1) est un triplet pythagoricien.
C'est immédiat : (Fn-1Fn+2)2+(2FnFn+1)2=((Fn+1)2-(Fn)2)2+4(Fn)2(Fn+1)2, cf 4) de P8,
soit ((Fn+1)2+(Fn)2)2=(F2n+1)2, cf 3) de P9.

Exemples : n=2 donne le fameux (3,4,5), n=3 donne (5,12,13) ; il est facile de vérifier que l'on n'obtient pas le triplet pythagoricien (6,8,10).

Remarque 1 : on a exclu le cas n=1, car il donne le triplet (0,2,2) qui n'est pas considéré comme pythagoricien, un des ses éléments étant nul.

Remarque 2 : F2n peut être aussi l'hypothénuse d'un triangle rectangle à côtés entiers. C'est le cas de F14=377, puisque 1522+3452=3772 ; par contre ce n'est pas le cas de F6=8, puisqu'il est facile de vérifier que 64 n'est pas la somme de deux carrés d'entiers non nuls.

2) Théorème de Lucas :
les solutions en nombres entiers naturels de l'équation diophantienne |x2+xy-y2|=1 sont exactement les couples (x,y)=(Fn,Fn+1) pour tous les entiers naturels n, plus le couple (1,0).

3) On a vu (relation 7 de P8) que pour tout n dans N, Ln2-5Fn2=4(-1)n.
En fait :

Cela se prouve facilement sous réserve de connaître les équations de Pell-Fermat.
En effet l'équation x2-5y2=±4 est une équation de Pell-Fermat, et on dispose du résultat suivant :
si l'entier naturel D n'est pas un carré, alors
tous les couples d'entiers positifs ou nuls solutions de x2-Dy2=±4 sont, pour n dans N,
les couples (xn,yn) tels que (xn+yn√D)/2=((t+u√D)/2)n
avec (t,u) le plus petit couple d'entiers positifs solution de x2-Dy2=-4 ;
les solutions de x2-Dy2=4 sont obtenues en prenant n pair, et celles de x2-Dy2=-4 en prenant n impair.

Application au cas D=5 :
dans ce cas (t,u)=(1,1) et xn+yn√5=2((1+√5)/2)n=2((L1+F1√5)/2)n.
Et en appliquant P5.2 (Lucas-Fibonacci-Moivre), on obtient tout de suite xn+yn√5=Ln+Fn√5, ce qui donne xn=Ln et yn=Fn

Exercice 14 : vérifier que les couples (Fn,Fn+1) sont effectivement solutions de l'équation diophantienne |x2+xy-y2|=1 ;
Pour une réciproque, je renvoie le lecteur à la preuve proposée par la revue Quadrature d'Avril, Mai Juin 1997 ; cette preuve passe par la recherche des éléments inversibles de l'anneau {x+ay ; xZ ; yZ}.

vers la solution...chercher avant de cliquer


P13-> Sur la suite de Fibonacci (F) modulo m, m étant un entier naturel 2.
C'est la suite (F') définie ainsi : pour tout n dans N, F'n est le reste de la division de Fn par m.

Ceci est équivalent à dire que F'n{0;1;...;m-1} et que F'nFn (m), cad F'n{0;1;...;m-1} et F'n congru à Fn modulo m.
Exemples :

n0123456789101112
Fn01123581321345589144
F'n
pour m=2
0110110110110
F'n
pour m=3
0112022101120
F'n
pour m=4
0112310112310
F'n
pour m=5
0112303314044
F'n
pour m=6
0112352134150

Il semble, dans cas m=2, 3, 4, que les suites (F') soient périodiques, de périodes respectives 3, 8, 6. Pour les autres, le nombre de termes calculés est insuffisant pour émettre une conjecture ; mais si on continue il semble que pour m=5 la période est 20 et pour m=6 elle est 24 (voir le 2) ci-dessous pour une autre façon pour m=6).

En fait on a les résultats suivants :
1) "mN-{0;1}

  • a) F'0=0, F'1=1
  • b) Si F'p=F'q=0 alors F'p+q=0.
  • c) Pour tout entier naturel n, F'n+2F'n+1+F'n (m) ; il y a égalité si et seulement si F'n+1+F'n{0;1;...;m-1}
  • d) La suite (F') est périodique : il existe un plus petit entier naturel non nul, k(m), tel que "nN, F'n+k(m)=F'n.
    k(m) est appelé la période de la suite (F') ; c'est le plus petit entier naturel non nul tel que F'k(m)=0 et F'k(m)+1=1.
    On a toujours k(m)m2

    Donc, cf tableau ci-dessus, k(2)=3, k(3)=8, k(4)=6 ; je laisse le lecteur courageux vérifier que k(5)=20 ; k(6)=24 sera obtenu plus loin par application du c) de 2).

  • Remarque 1 : on verra à l'exercice 16 ci-dessous la formule générale pour k(2e).

    Remarque 2 : k(m) est l'ordre, modulo m, de la matrice

    A=01
    è11
    considérée comme élément du groupe des inversibles de l'anneau des matrices 2×2 à coefficients dans Z/mZ. Ce groupe, pour m 1er, étant d'ordre (m2-1)(m2-m), c'est que pour m 1er, k(m) divise (m2-1)(m2-m) ; en fait pour m 1er, distinct de 5, k(m) divise (m2-1) : voir l'étude de Marc Renault (lien dans la remarque ci-dessous).
  • e) Soit k un entier naturel quelconque non nul, alors
    "nN, F'n+k=F'n F'k=F'0(=0) et F'k+1=F'1(=1) k(m) divise k.
    Un entier k vérifiant une des conditions ci-dessus (donc les deux) est appelé une période de la suite (F').
  • f) Il existe une infinité de termes de la suite (F) qui sont divisibles par m : par exemple les termes Fn avec n=qk(m), où q est un entier naturel quelconque.
    Mais il peut y en avoir d'autres : pour m=3, k(3)=8 donc 3 divise F8q pour tout entier naturel q, mais en fait, voir question 6)c) de l'exercice 1, 3 divise Fn 4 divise n.
    Ce résultat justifie la remarque faite à la même question 6)c) de cet exercice 1).
  • g) Si g(m) est le plus petit entier >0 tel que m divise Fg(m), (g(m) est parfois appelé le point d'entrée de m dans la suite (F)) alors
    les seuls termes de la suite (F) qui soient divisibles par m sont Fqg(m) pour q dans Z,
    et k(m)/g(m)=1 ou 2 ou 4.

    Une "petite" conséquence du premier aspect : si 7 divise Fn, alors 21 divise Fn.
    Et pour illustrer le deuxième aspect : k(4)/g(4)=6/6=1, k(6)/g(6)=24/12=2, k(5)/g(5)=20/5=4.

    Remarque : m est appelé facteur primitif de Fn signifie que m est premier et que n=g(m).
    Ceci implique que m est un nombre premier divisant Fn.

    Exemples :

    • F8=21 a 7 pour unique facteur primitif, puisque 7 est premier et g(7)=8 ; par contre g(3)=4≠8.
    • F6=8 n'a pas de facteur primitif : en effet 2 est le seul nombre premier qui divise F6 mais g(2)=3≠6
    • F12=144 n'a pas de facteur primitif : F12 a pour diviseurs premiers 2 et 3, et g(2)=3≠12, g(3)=4≠12.
  • h) Si p est un nombre premier différent de 2 et 5, alors
    p divise Fp-1 ou Fp+1, et donc g(p)≤p+1.
      De façon plus précise,
    • si 5 est un carré modulo p, alors p divise Fp-1
      et aussi p divise Fp+1-1
    • si 5 n'est pas un carré modulo p alors p divise Fp+1
    • Note : un moyen rapide pour savoir si 5 est ou pas un carré modulo p est d'utiliser le résultat suivant (voir théorie des résidus ; rappel p≠2, p≠5):
      5 est un carré modulo p <=> p≡±1 (5)
      5 n'est pas un carré modulo p <=> p≡±2 (5)
    • Note : le résultat ci-dessus ( p divise Fp-1 ou Fp+1, selon que 5 est un carré ou pas modulo 5) est souvent présenté à l'aide du symbole de Legendre ainsi :
      pour tout p premier différent de 2 et 5, p divise Fp-(5/p) : voir remarque 1 ci-dessous.

    Exemples :
    5 est un carré modulo 11 puisque 5≡42 (11) ou parceque 11≡1 (5) ; on vérifie que 11 divise F11-1=55 et 11 divise F11+1-1=144-1=11×13.
    5 n'est pas un carré modulo 13 car aucun des nombres 02, 12, 22, 32, 42, 52, 62 n'est congru à 5 modulo 13 ou parceque 13≡3 (5) ; on vérifie que 13 divise F13+1=377=13×29.

    Remarque 1 :
    Pour p premier impair, pour tout a dans Z, le symbole de Legendre (a/p) est défini ainsi :

    • (a/p)=0 si a≡0 (p) cad p divise a
    • (a/p)=1 si a est un résidu quadratique de p, cad si p ne divise pas a et a est un carré modulo p
    • (a/p)=-1 si a n'est pas un résidu quadratique de p, cad si p ne divise pas a et a n'est pas un carré modulo p

    D'où pour p premier impair distinct de 5, p divise Fp-(5/p)
    Note : puisque p≠5, ici (5/p) est toujours 1 ou -1.

    Une propriété importante de ce symbole de Legendre est :
    pour tout a dans Z, tout nombre premier impair q : (a/q)≡a((q-1)/2) (q)

    Remarque 2 :
    cf par exemple, la relation 6 de P8, Fp-1 et Fp+1 étant premiers entre eux, ils ne sont pas simultanément divisibles par p.

    Remarque 3
    pour le lecteur voulant aller plus loin sur cet aspect, cf un article de Paul S.Bruckman de juillet 1992 :

    • un entier naturel n est appelé "Fibonacci pseudo prime" ou FPP signifie que pgcd(n,10)=1 et n divise Fn-(5/n)
    • un entier naturel n est appelé "Lucas pseudo prime" ou LPP signifie que n divise Ln-1
    Donc, cf ci-dessus, si n est premier distinct de 2 et 5, n est un FPP ; mais cf P5.2, si n est premier, c'est aussi un LPP.
    Dans son papier, Paul S.Bruckman donne deux familles d'entiers qui ne sont pas premiers mais qui sont à la fois des FPP et LPP.
    Sa preuve utilise des relations vues au 15) de P8.
  • i) Si p est un nombre premier distinct de 5, Fp≡±1 (p)
    De façon plus précise, pour p premier impair distinct de 2, Fp≡(5/p) (p).
    Note
    : voir remarque 1 ci-dessus pour la définition du symbole de Legendre (a/p)

    Exemples :

    • F2=1≡1 (2) car 5 est un carré modulo 2 : 5≡12 (2)
    • F3=2≡-1 (3) car 5 n'est pas un carré modulo 3 : 5≡2 (3) et le seul carré (non nul) modulo 3 est 1
    • F5=5 n'est pas congru à 1 ou -1 modulo 5
    • F7=13≡-1 (7) car 5 n'est pas un carré modulo 7 puisque 7≡2 (5) (voir 1ière note du h) ci-dessus)
    • F11=89≡ 1 (11) car 5 est un carré modulo 11 puisque 11≡1 (5)
    • F13=233≡-1 (13) car 5 n'est pas un carré modulo 13 puisque 13≡-2 (5)

    Remarque : j'ai mis ce résultat ici car il y a un lien avec le précédent :
    pour p premier impair distinct de 5, si 5 est un carré modulo p, alors
    cf le g), p divise Fp-1
    mais cf un résultat du h), p divise Fp+1-1
    d'où par différence, p divise Fp+1-Fp=Fp-1 et on retrouve l'autre résultat du h).

2) Quelques propriétés sur la fonction m->k(m)= la période de la suite (F').

  • a) si m3 alors k(m) est pair
  • b) si m' (entier naturel 2) divise m, alors k(m') divise k(m)
  • c) si m=Ppin_i ( décomposition en nombres premiers pi de m), alors k(m)=ppcm des k(pin_i)
    note : n_i est en fait ni (entier naturel non nul), mais en html, imbriquer des exposants et indices ne fonctionne pas avec tous les navigateurs.

    Exemple : k(6)=ppcm(k(2),k(3))=ppcm(3,8)=24.

Remarque : on verra beaucoup de compléments sur ce sujet, dans l'étude de Marc Renault. Notamment il existe un résultat sur k(pe), pour p premier : si t est le plus grand entier tel que k(pt)=k(p), alors k(pe)=pe-tk(p) pour et ; voir les questions 2) et 3) de l'exercice 16 ci-aprs pour le cas particulier k(2e).
On conjecture, toujours selon l'étude de marc Renault, que pour tout p premier t serait égal à 1, et pour l'instant on ne dispose pas de formule générale donnant k(p) en fonction de p, p étant premier.

Exercice 15 : prouver les résultats ci-dessus, sauf celui de la remarque du 2)...

vers la solution...chercher avant de cliquer

Exercice 16 :

1) Montrer que pour tout entier naturel n et tout entier naturel k on a
Fn+6k≡Fn (4) et Ln+6k≡Ln (4), cad,

valeurs de n modulo 6012345
valeurs de Fn modulo 4011231
valeurs de Ln modulo 4213033

A partir du tableau ci-dessus, donner, modulo 4, une relation entre Fn2 et Ln2 ; retrouver cette relation à l'aide d'une formule de P8.

2) Montrer que pour tout entier r3, F(3×2r-2)0 (2r) et F(3×2r-2+1)2r-1+1 (2r)

3) Montrer que pour tout entier e1, k(2e)=3×2e-1.
Ceci donne que k(2)=3, k(4)=6, ce qui avait été constaté au début de ce paragraphe sur le tableau d'exemples.

Aide :

    On pourra utiliser, pour les questions 2 et 3, que
  • Fn pair 3 divise n : voir question 6 de l'exercice 1
  • F2n+1=(Fn)2+(Fn+1)2 : voir relation 3 de P8
  • F2n=Fn(Fn-1+Fn+1) : voir remarque de la relation 8 de P8
vers la solution...chercher avant de cliquer


P14-> Sur l'écriture, de Fn et Ln sous forme de produit d'expressions trigonométriques! Ces formules sont vraiment étonnantes dans la mesure où les suites de Fibonacci sont définies par un processus additif.
On me répondra qu'il y a les formules de Binet qui font intervenir des puissances. Certes, mais dans ce cas il est assez facile de retrouver l'aspect additif vérifié par les suites, alors que pour la formule ci-dessous c'est une autre histoire : c'est là que Tchebycheff intervient (ses polynômes de 2ième espèce). pour tout entier naturel n2,
(Fn)2=Pk=1 n-1(1+4cos2(kp/n))=(1+4cos2(p/n))×...×(1+4cos2((n-1)p/n))

Remarque : pour tout réel x, 1+4cos2(x/2)=3+2cos(x).

C'est facile à vérifier pour n=2,3,4,6, mais pour n=5,7,8,9 c'est déjà moins facile.
Par exemple pour n=5 cela signifie que 25=(1+4cos2(p/5))(1+4cos2(2p/5))(1+4cos2(3p/5))(1+4cos2(4p/5))

La formule ci-dessus peut aussi s'écrire

pour tout entier naturel n3,
Fn=Pk=1 E((n-1)/2)(1+4cos2(kp/n))=Pk=1 E((n-1)/2)(3+2cos(2kp/n)),
E désignant la fonction partie entière.
Ce qui donne pour n=5, 5=(3+2cos(2p/5))(3+2cos(4p/5)).

Remarque : on peut écrire (si on le souhaite ... ) F2=3+2cos(2p/2).

On a aussi des relations analogues pour la suite (L) :

pour tout entier naturel n2,
(Ln)2=Pk=0 n-1(3+2cos((2k+1)p/n)) et Ln=Pk=0 E(n/2-1)(3+2cos((2k+1)p/n))

Exercice 17 : son but est de prouver les résultats ci-dessus, cela d'après l'idée de la preuve de l'étude de N.Garnier et O.Ramaré Université Lille 1 : elle utilise les polynômes de 2ième espèce de Tchebycheff.

1) Les polynômes de 2ième espèce de Tchebycheff, Un(X), sont définis par

  • U0(X)=1
  • U1(X)=2X
  • pour tout entier naturel n, non nul, Un+1(X)=2XUn(X)-Un-1(X)

Montrer alors que

  • "nN, dUn=n, le coefficient de tête étant 2n
  • "nN,Un(cos(q))=(sin((n+1)q))/sin(q), pour sin(q)0
  • "nN*, Un(X)=2nPk=1 n(X-cos(kp/(n+1)))

2) Et voici le lien avec Fibonacci : trouver une constante q telle que la suite (W) définie par Wn=qnUn(-i/2), pour tout entier naturel n, soit une suite de Fibonacci!

3) Montrer que pour tout entier naturel n2, (Fn)2=Pk=1 n-1(1+4cos2(kp/n))

4) Montrer que pour tout entier naturel n3, Fn=Pk=1 E((n-1)/2)(1+4cos2(kp/n))=Pk=1 E((n-1)/2)(3+2cos(2kp/n))

5) Déduire de ce qui précéde, les deux résultats relatifs à la suite (L).

vers la solution...chercher avant de cliquer

Exercice 18 : le but de cet exercice est de "vérifier", pour les petites valeurs de n, la formule Fn=Pk=1 E((n-1)/2)(3+2cos(2kp/n)), cela par linéarisation du membre de droite. C'est ainsi que j'avais essayé de prouver cette formule, mais je ne suis pas arrivé à généraliser.

Pour n=3,4,6,8 les cos se calculent de façon évidente et la vérification est immédiate ; mais pour n=5,7,9 c'est autre chose.

1) On pose pk(q)=(3+2cos(q))×(3+2cos(2q))×...×(3+2cos(kq)) : par utilisation de 2cos(p)cos(q)=cos(p+q)+cos(p-q), linéariser p2, p3 et p4.

2) En utilisant 1) et le fait que la somme des racines nièmes de 1 (dans C) est 0, et le fait que ces racines sont conjuguées deux à deux, vérifier pour n=5, 7, 9 la formule ci-dessus relative à Fn.

vers la solution...chercher avant de cliquer


P15-> Sur les polynômes donnant Fkn en fonction de Fn (si k est pair, Fkn est Ln fois un polynôme en Fn) et sur les polynômes donnant Lkn en fonction de Ln.

La question a commencée à être vue à la fin de P5.2 et au 15 de P8.

Dans tout ce qui suit on conviendra que le coefficient binomial Cnp est nul si p<0 ou si n<p.

1) Pour tout entier k≥1 et tout entier naturel n, Lkn=Rk,n(Ln), avec Rk,n est un polynôme vrifiant la relation de récurrence :

  • Rk+1,n(X)=XRk,n(X)+(-1)n+1Rk-1,n(X).
Comme

  • R1,n(X)=X
  • R2,n(X)=X2+2(-1)n+1

    on en déduit

  • R3,n(X)=X3+3(-1)n+1X
  • R4,n(X)=X4+4(-1)n+1X2+2
  • R5,n(X)=X5+5(-1)n+1X3+5X
  • R6,n(X)=X6+6(-1)n+1X4+9X2+2(-1)n+1
  • R7,n(X)=X7+7(-1)n+1X5+14X3+7(-1)n+1X
  • R8,n(X)=X8+8(-1)n+1X6+20X4+16(-1)n+1X2+2

La formule explicite de Rk,n est la suivante : pour tout entier k≥1 et tout entier naturel n,

Rk,n(X)=∑r=0E(k/2)(-1)r(n+1)(Ck-rr  +Ck-r-1r-1 )Xk-2r.

Ce polynôme est donc de degré k, unitaire et il a pour parité celle de k :

  • si k est pair, Rk,n est pair et son terme constant est 2(-1)k(n+1)/2
    (terme r=E(k/2)=k/2 du ∑)
  • si k est impair, Rk,n est impair et le coefficient de X est k(-1)(k-1)(n+1)/2
    (terme r=E(k/2)=(k-1)/2 du ∑)

Note : Ck-rr +Ck-r-1r-1 =(k/(k-r))Ck-rr
(c'est trivial si r=0, et pour r≥1, c'est parceque Ck-rr =((k-r)/r)Ck-r-1r-1 )

2) Pour tout entier k≥0 et tout entier naturel n, F(2k+1)n=Q2k+1,n(Fn),
pour tout entier k≥1 et tout entier naturel n, F2kn=LnQ2k,n(Fn)
avec Q2k+1,n et Q2k,n deux polynômes vérifiant les relations de récurrence suivantes :

  • Q2k+1,n(X)=(5X2+4(-1)n)Q2k,n(X)+(-1)n+1Q2k-1,n(X)
  • Q2k+2,n(X)=Q2k+1,n(X)+(-1)n+1Q2k,n(X)

Comme

  • Q1,n(X)=X
  • Q2,n(X)=X

    on en déduit

  • Q3,n(X)=5X3+3(-1)nX
  • Q4,n(X)=5X3+2(-1)nX
  • Q5,n(X)=25X5+25(-1)nX3+5X
  • Q6,n(X)=25X5+20(-1)nX3+3X
  • Q7,n(X)=125X7+175(-1)nX5+70X3+7(-1)nX
  • Q8,n(X)=125X7+150(-1)nX5+50X3+4(-1)nX

Les formules explicites de Q2k+1,n et Q2k,n sont les suivantes :

  • pour tout entier k≥0 et tout entier naturel n,
    Q2k+1,n(X)=(1/√5)R2k+1,n-1(√5X)=∑r=0k(-1)rnθk,r5k-rX2k+1-2r,
    avec θk,r=C2k+1-rr +C2k-rr-1 =((2k+1)/(2k+1-r))C2k+1-rr
    Donc Q2k+1,n est impair, de degré 2k+1 (coefficient de tête : 5k)
    et le coefficient de X est (2k+1)(-1)kn.
  • pour tout entier k≥1 et tout entier naturel n,
    Q2k,n(X)=∑r=0k-1(-1)rnC2k-r-1r 5k-r-1X2k-1-2r
    Donc Q2k,n est impair, de degré 2k-1 (coefficient de tête : 5k-1)
    et le coefficient de X est k(-1)(k-1)n.
    Une petite remarque : F2kn=LnQ2k,n(Fn)=F2nSk,n(Fn), Sk,n étant le polynôme Q2k,n(X)/X, puisque F2n=LnFn.
Remarque : dans un papier de Stanley Rabinowitz, on trouve (sans démonstration) la formule donnée ci-dessus pour Rk,n(X), avec le commentaire suivante :
"In general, Fkn cannot be replaced by sums of powers of Fnalone, so no formula of this type is given".
Est-ce à dire que ces formules explicites de Qk,n sont inédites?

On notera que tous les polynômes Qk,n et Rk,n sont à coefficients entiers, coefficients qui sont soient indépendant de n, soient de la forme (-1)n×un coefficient indépendant de n (donc tous de valeur absolue indépendante de n).

On retrouve, tous les Qk,n étant impairs, le fait que pour tout k non nul et tout n non nul, Fn divise Fkn (déja vu à la question 9 de l'exercice 1 et à P10) et aussi que si k est pair, FnLn=F2n divise Fkn, (résulte aussi de P10, 2n divisant kn) ; mais ici on obtient des renseignements sur les quotients.

On retrouve aussi que si k est impair, Rk,n étant impair, Ln divise Lkn (déjà vu à la question 2 de l'exercice 2 et à P10)
Rappelons (voir 1.7 de P10) que si k est pair et n≥2, Ln ne divise pas Lkn : L3=4 ne divise pas L2×3=18.

Remarque : il peut paraître étonnant que pour k pair, Fkn ne s'exprime pas comme un polynôme uniquement fonction de Fn.
Cependant, par exemple, pour k=2 où F2n=LnFn, on peut montrer qu'il n'existe pas des réels an, bn, cn, à valeur absolue indépendante de n tels que, pour tout entier naturel n on ait F2n=anFn2+bnFn+ cn

Exercice 19 : prouver P15.

vers la solution...chercher avant de cliquer

Exercice 20 : en utilisant, pour k impair, une propriété de Qk,n montrer que que si n0 est le plus petit entier >0 tel que k divise Fn0 (l'existence de n0 est justifiée au 1)g) de P13) alors
pour tout entier p≥1, kp divise Fn0kp-1
.
Par exemple

  • pour tout p≥1, 3p divise F4×3p-1
  • pour tout p≥1, 5p divise F5p (par exemple F25=25×3001)
    Ce résultat, celui sur 5p, n'aurait était trouvé que récemment, pourtant...
    Est-ce à dire que cette propriété générale énoncée ci-dessus est inédite?
  • pour tout p≥1, 7p divise F8×7p-1
  • pour tout p≥1, 9p divise F12×9p-1
vers la solution...chercher avant de cliquer


P16-> Sur une généralisation de la formule vue au 8 de P8 : F2n=Fn+12-Fn-12.

Pour tout entier k2, il existe une fonction rationnelle de la forme Pk(X)=SiIaiXi, avec I un sous-ensemble fini de Z,
telle que pour tout n dans Z, Fkn=SiIaiFn+ik.

    Par exemple
  • k=2, P2=X-1/X et on a F2n=Fn+12-Fn-12
  • k=3, P3=X-1/X+1 et on a F3n=Fn+13+Fn3-Fn-13
    par exemple F12=F53+F43-F33, ce qu'on vérifie puisque 144=53+33-23
  • k=4, P4=X2/6+X/2-1/(2X)-1/(6X2) et on a F4n=Fn+24/6+Fn+14/2-Fn-14/2-Fn-24/6
    par exemple F12=F54/6+F44/2-F24/2-F14/6, ce qu'on vérifie puisque 144=54/6+34/2-1/2-1/6
  • Pour P5 et P6, voir solution de l'exercice 21.
  • Attention : cette fraction rationnelle n'est pas forcément unique ; par exemple on peut prendre, pour k=2, P2=X3-3X2+X+3-2/X, ce qui donne cette autre identité F2n=Fn+32-3Fn+22+Fn+12+3Fn2-2Fn-12 ; par exemple F12=F92-3F82+F72+3F62-2F52 ; mais cette identité est mons "intéressante" que F2n=Fn+12-Fn-12.
    A noter que la combinaison de ces deux relations donne la nouvelle identité Fn+32-3Fn+22+3Fn2-Fn-12=0.

Exercice 21 : prouver P16 (utiliser la formule de Binet).

vers la solution...chercher avant de cliquer


P17-> Sur les termes carrés dans les suites (L) et (F).

n étant un entier relatif (voir P2, P5.3)

  • Ln est un carré si et seulement si n=1 ou 3 : L1=1, L3=4
  • Ln est 2 fois un carré si et seulement si n=0 ou -6 ou 6 : L0=2, L-6=L6=18
  • Fn est un carré si et seulement si n=0 ou -1 ou 1 ou 2 ou 12 : F0=0, F-1=F1=1, F2=1, F12=144=122
  • Fn est 2 fois un carré si et seulement si n=0 ou -3 ou 3 ou 6 : F0=0, F-3=F3=2, F6=8

C'est John H.E. Cohn qui a été le premier à prouver ces résultats, en 1964.
Je n'ai fait ici que traduire et dtailler un
papier de John H.E Cohn qui donne une preuve plus courte que celle de 1964.

Cette preuve utilise essentiellement 11 formules sur les suites de Fibonacci :

  • CO1 : 2Fm+n=FmLn+FnLm : on en déduit F2n=FnLn voir 8 et 15.1 de P8
  • CO2 : 2Lm+n=5FmFn+LmLn : voir 15.2 de P8
  • CO3 : L2n=Ln2+2(-1)n-1 : voir 7 de P8
  • CO4 : pgcd(Fm,Lm)=2 si 3 divise m, sinon c'est 1 : voir P10
  • CO5 : 2 divise Lm équivaut à 3 divise m : voir question 6c de l'exercice 1
  • CO6 : 3 divise Lm équivaut à 4 divise m-2 : voir question 6c de l'exercice 1
  • CO7 : 4 divise Lk-3 si 2 divise k et 3 ne divise pas k : voir question 6c de l'exercice 1
  • CO8 : 8 divise Lm+12-Lm : voir question 6c de l'exercice 1
  • CO9 : F-n=(-1)n-1Fn ; L-n=(-1)nLn : voir P5.3
  • CO10 : Lp divise Lm+2p+(-1)pLm ainsi que Fm+2p+(-1)pFm : ce résultat est le seul qui n'a pas encore été établi explicitement dans les chapitres précédents.
    En voici une preuve : on utilise tout simplement les formules
    FmLn=Fm+n+(-1)nFm-n et LmLn=Lm+n+(-1)nLm-n vues aux 15.6 et 15.7 de P8.
    En y remplacant m par m+p et n par p, on obtient C10.

    A vrai dire, dans le papier de Cohn, ce résultat n'est donné que pour p pair (Lp divise Lm+2p+Lm ainsi que Fm+2p+Fm)

  • CO11 (non citée en fait par Cohn, mais lorsqu'il l'utilise il renvoit à C10) : Ln divise Lkn si k est impair : voir P15.
    On peut effectivement justifier CO11 à partir de CO10 : en effet,
    cf CO10, Lp divise L3p+(-1)pLp, donc Lp divise L3p
    cf CO10, Lp divise L5p+(-1)pL3p, donc Lp divise L5p
    etc (récurrence)

Remarque 1 :
John H.E.Cohn n'utilise en fait jamais CO2 dans sa preuve et effectivement je n'en vois pas l'utilité?

Remarque 2 :
par ailleurs, cette preuve de John H.E Cohn utilise deux résultats classiques sur les résidus quadratiques modulo p (ou résidu quadratique de p ou résidu de p ou résidu si le contexte est clair), avec p nombre 1er impair :
a dans Z est résidu quadratique de p signifie p ne divise a et il existe x dans Z tel que p divise x2 -a, cad a≡x2 (p), cad a congru à x2 modulo p.

  • le produit d'un résidu par un non résidu est un non résidu
  • -1 est résidu si et seulement si p=1+4k, avec k dans N, cad p congru à 1 modulo 4 : p≡1 (4)

Remarque 3
cf CO9, et puisque (-1)n-1 et (-1)n sont toujours des puissances impaires (de -1 ou de 1) :

  • F-n est une puissance impaire <=> Fn est une puissance impaire
  • L-n est une puissance impaire <=> Ln est une puissance impaire

Par contre, ce n'est plus vrai pour les puissances paires : F12 est un carré pas F-12=-144, L3=4 est un carré, pas L-3=-4.
En fait
  • si n est impair, alors F-n=Fn et l'un est une puissance paire <=> l'autre est une puissance paire
  • si n est pair, alors L-n=Ln et l'un est une puissance paire <=> l'autre est une puissance paire

Remarque 4 :

  • pour ce qui est des cubes on a le résultat suivant : les seuls cubes de la suite (F) sont :
    F-6=-8, F-2=-1, F0=0, F-1=F1=F2=1 et F6=8
    les seuls cubes de la suite (L) sont :
    L-1=-1 et L1=1

    Cela est prouvé par Hymie London et Rapahael Finkelstein, lesquels par utilisation de la relation 7 de P8, cad Ln2-5Fn2=4(-1)n, se raménent à la résolution dans N*×N*, des équations diophantiennes Y2-100=X3, Y2+100=X3, Y2-300=X3, Y2+500=X3.
  • En dehors des termes des suites (F) et (F) qui sont des carrés ou des cubes, aucun autre n'est une puissance entière d'un entier.
    Pour ce qui est des puissances entières paires, c'est facile à vérifier, puisque une puissance paire d'un entier est forcément le carré d'un entier.
    Pour les puissances pures impaires, c'est moins immédiat. En tout cas H.London et R.Finkelstein disent que selon un résultat de Siegel, la détermination de tous les cubes des suites (F) et (L) permet de conclure : c'est un aspect que je n'ai pas approfondi encore.
    vers la traduction de la preuve de John H.E.Cohn

Solution des exercices et preuves (si besoin) des propriétés

Exercice 1

1) Soit (u) une suite de Fibonacci quelconque ; d'aprs la foumule de Binet vue à P4, (u)=a(e)+b(f), les suites (e) et (f) étant définies par en=an et fn=bn, et a et b étant deux constantes réelles. Ainsi les deux suites (e) et (f) forment une famille génératrice de l'espace vectoriel des suites de Fibonacci. La dimension de cet est espace est donc 1 ou 2 .
Mais ces deux suites sont linéairement indépendantes, puisque a(e)+b(f)=0 entraîne (on fait n=0, n=1) a+b=0 et aa+bb=0, ce qui donne a=b=0. La dimension est donc 2.

2) Soit n dans N* : si d divise un+1 et un, alors d divise un et un-1=un+1-un, et la réciproque est aussi vraie : donc les diviseurs de un et un+1 sont les diviseurs de un et un-1 et ainsi pgcd(un,un+1)=pgcd(un-1,un).
En poursuivant la descente on arrive à pgcd(un,un+1)=pgcd(u0,u1).

3) Par ajout membres à membres des égalités suivantes, pour n et k dans N :

un+2=un+1+un
un+3=un+2+un+1
.
.
un+k+1=un+k+un+k-1
un+k+2=un+k+1+un+k
on obtient un+k+2=un+1+un+un+1+...+un+k,
ce qui donne le résultat demandé : un+un+1+...+un+k=un+k+2-un+1.
Mais cf le 6) de P3, un+k+2=Fk+1un+Fk+2un+1, ce qui donne
un+un+1+...+un+k=un+k+2-un+1=Fk+1un+(Fk+2-1)un+1
En faisant n=0 et en remplacant k par n, on obtient
u0+u1+...+un=un+2-u1=Fn+1u0+(Fn+2-1)u1.

Par ajout membres à membres des égalités suivantes, pour nN* :

u3=u2+u1
u5=u4+u3
.
.
u2n+1=u2n+u2n-1
on obtient u2n+1=u2+u4+...+u2n+u1, ce qui donne u0+u2+u4+...+u2n=u2n+1-u1+u0, relation encore vraie pour n=0.

Par ajout membres à membres des égalités suivantes, pour nN :

u2=u1+u0
u4=u3+u2
.
.
u2n+2=u2n+1+u2n
on obtient u2n+2=u1+u3+...+u2n+1+u0, ce qui donne u1+u3+...+u2n+1=u2n+2-u0.

On peut vérifier que par ajout membres à membres des deux dernières relations on obtient la première relation (deux cas à envisager : 1er cas : on ajoute m à m les deux dernières relations telles quelles, 2ième cas : on remplace n par n+1 dans la 3ième relation, avant d'ajouter m à m les deux dernières relations).

Passons à l'autre question.
La relation, pour tout n dans N, u02+...+un2=unun+1 implique, en faisant n=0, que u02=u0u1, soit u0=0 ou u0=u1.
Réciproquement, si on a u0=0 ou u0=u1, alors

la relation u02+...+un2=unun+1 est bien vraie pour n=0
et si elle est vraie au rang n≥0, alors
u02+...+un+12=unun+1+un+12=un+1(un+un+1)=un+1un+2,
cad la relation est vraie au rang n+1 ;
On a donc montré par récurrence que si on a u0=0 ou u0=u1 la relation u02+...+un2=unun+1 est vraie pour tout n≥0.

4) Par utilisation de la formule de Binet, un=aan+bbn, on obtient
S0jk Ckj un-j=a(S0jk Ckj an-j)+b(S0jk Ckj bn-j) =aan-k(S0jk Ckj ak-j)+bbn-k(S0jk Ckj bn-j)
= aan-k(S0jk Ckk-j ak-j)+bbn-k(S0jk Ckk-j bn-j)=aan-k(1+a)k+ bbn-k(1+b)k=aan-k(a)2k+ bbn-k(b)2k=aan+k+bbn+k=un+k.

En faisant n=k, la formule précédente donne u2k=S0jk Ckj uk-j. Et comme Ckj =Ckk-j, en posant k-j=i on obtient u2k=S0ik Cki ui : en remplacant k par n et i par j on obtient la formule annoncée.

Cette formule donne u8=C40 u0+C41 u1+C42 u2+C43 u3+ C44 u4=u0+4u1+6u2+4u3+u4, ce qui donne pour u0=0, u1=1, u8=4+6+8+3=21.

5)
Notons, pour n2, kn=le nombre de parties non vides de En={1 ; 2 ; ... ; n-1} dont deux éléments quelconques ne sont pas consécutifs.

si n=2, E2={1}, dont la seule partie convenant est {1} : k2=1=F2
si n=3, E2={1 ; 2}, dont les seules parties convenant sont {1} et {2} : k3=2=F3
Montrons maintenant que pour tout n3 on a kn+1=kn+kn-1 : En+1=En{n}, et donc les kn+1 parties de En+1 convenant se répartissent en deux catégories disjointes: celles constituées que d'éléments de En : il y en a kn
celles contenant n : les autres élément étant distincts de n-1, ils sont dans En-1, et donc le nombre de ces parties est kn-1
Ceci prouve que kn+1=kn+kn-1, donc que la suite (k), définie pour n2, est une suite de Fibonacci et comme k2=F2, k3=F3, c'est que pour tout n2 on a kn=Fn, cf une suite de Fibonacci est caractérisée par ses deux premiers termes (voir P3).

6a)

La suite (u) est évidemment croissante à partir du rang 1 : u1u2u3...
Donc pour tout n2, un+1=un+un-12un.
Cela sera vrai pour n=0 si et seulement si u12u0,
et cela sera vrai pour n=1 si et seulement si u0u1 (puisque on doit avoir u22u1)

Le 2ième résultat (évidemment faux pour n=0 et n=2) résulte de Fn+1=Fn+Fn-1 et Fn-1<Fn pour n3 et n=1 ; le 3ième en découle immédiatement puisque F3=2F2.

6b)

IL est immédiat que Fn=(Fn-2+Fn+1)/2, et cela pour tout n2, puisque Fn-2+Fn+1=Fn-2+Fn-1+Fn=Fn+Fn.

Mais la réciproque ne peut être vraie qu'à partir de n=5, cf les exemples donnés dans l'énoncé.
Supposons donc n5 et Fn=(Fi+Fk)/2 avec i<k et montrons qu'obligatoirement i=n-2 et j=n+1.

supposons kn comme i<k, on a Fi<Fk (sauf si i=1 et k=2, cas qui sera examiné ci-après), donc Fi+Fk<2Fk ; mais 2Fk2Fn, donc (Fi+Fk)/2<Fn, soit (Fi+Fk)/2 Fn.
Si i=1 et k=2 alors Fi+Fk=2 et donc (Fi+Fk)/2=1 Fn (puisque n3).
Donc on ne peut avoir kn.
Supposons kn+2 On a alors FkFn+2 ; mais Fn+2-2Fn=Fn+1-Fn>0, puisque n2, et ainsi Fk>2Fn, (Fi+Fk)/2>Fn, et donc (Fi+Fk)/2 Fn.
Donc on ne peut avoir kn+2.
La seule possibilité pour k est donc k=n+1.
Déterminons maintenant i :
Fn=(Fi+Fn+1)/2 donne (Fn-2+Fn+1)/2=(Fi+Fn+1)/2, soit Fi=Fn-2. Comme n-23 (c'est là que l'hypothèse n5 est indispensable), c'est que i=n-2.

6c)

1) Fn=Fn-1+Fn-2=2Fn-2+Fn-3 : donc Fn et Fn-3 ont même parité, et comme F0=0 est pair, c'est que F3, F6, F9, etc, sont pairs.
Par contre F1, F4, F7, etc, ont la parité de F1=1, donc sont impairs, et F2, F5, F8, etc, ont la parité de F2=1, donc sont impairs.
Finalement Fn est pair si et seulement si 3 divise n.

2) Fn=3Fn-3+2Fn-4 : comme 3 est 1er avec 2, 3 divise Fn 3 divise Fn-4.
D'où en posant n=4q+r avec r=0 ou 1 ou 2 ou 3 (division euclidienne dans N),
3 divise Fn 3 divise Fn-4 3 divise Fn-8... 3 divise Fn-4q=Fr.
Or, parmi F0=0, F1=1, F2=1, F3=2, seul F0 est divisible par 3 ; donc, 3 divise Fn si et seulement si 4 divise n (n=4q).

3)

On peut faire deux constatations sur ce qui précéde :

m plus petit entier p
tel que m divise Fp
critère de divisibilité
de Fn par m
233 divise n
344 divise n
466 divise n
555 divise n
61212 divise n
788 divise n
866 divise n
91212 divise n
101515 divise n
Des deux 6 et des deux 12 dans la 2ième colonne, on déduit que
4 divise Fn <=> 8 divise Fn et 6 divise Fn <=> 9 divise aussi Fn

On va montrer que cela est toujours vrai, sous réserve d'admettre que pour tout m≥2 il existe p non nul tel que m divise Fp ( la preuve est au 1)f) de P13).
Soit donc m≥2 : on considère alors le plus petit entier p (non nul) tel que m divise Fp.
De la relation (cf 6) de P3) Fn=FpFn-p+1+Fp-1Fn-p on déduit que m divise Fn <=> m divise Fp-1Fn-p.
Mais m et Fp-1 sont premiers entre eux car sinon ils auraient un diviseur commun >1, qui serait diviseur commun de Fp (puisque m divise Fp) et Fp-1, ce qui est impossible car Fp et Fp-1 sont premiers entre eux (voir question 2) de cet exercice).
Donc (Gauss) m divise Fn <=> m divise Fn-p ; il suffit alors de regarder quels sont parmi les termes F0,...,Fp-1 ceux divisibles par m : ca ne peut être que F0=0 cf la définition de p.
Donc, m divise Fn <=> p divise n, o p est le plus petit entier >0 tel que m divise Fp
Remarque : 1)g) de P13 prouve d'une autre façon ce résultat.

4) On a aussi Ln=2Ln-2+Ln-3, donc Ln et Ln-3 ont même parité et comme parmi L0=2, L1=1, L2=3, seul L0 est pair, Ln est pair 3 divise n.

5) Ln=3Ln-3+2Ln-4, donc 3 divise Ln 3 divise Ln-4, et cf le même raisonnement qu'à 2) ci-dessus, 3 divise Ln 3 divise Lr avec r reste de la division euclidienne de n par 4. Comme parmi L0=2, L1=1, L2=3, L3=4, seul L2 est divisible par 3, Ln est divisible par 3 si et seulement si r=2, soit Ln divisible par 3 4 divise n-2.

6) En poursuivant les calculs, on obtient Ln=8Ln-5+5Ln-6 ; cette relation peut s'obtenir directement par application de la relation un+p=Fp-1un+Fpun+1 (vue à 6) de P3) en remplacant u par L, n par n-p et en faisant p=6.
Comme 5 ≡ 1 (4), 8 ≡ 0 (4), c'est que Ln ≡ Ln-6 (4), donc Ln ≡ Lr (4) avec r reste de la division euclidienne de n par 6. Comme parmi L0=2, L1=1, L2=3, L3=4, L4=7, L5=11, seuls L2, L4, L5 sont égaux à 3 modulo 4, c'est que Ln ≡ 3 (4) si et seulement r=2 ou 4 ou 5, soit Ln ≡ 3 (4) n ≡ 2 ou 4 ou 5 (6).

7) Par application de la relation un+p=Fp-1un+Fpun+1 (vue à 6) de P3) en remplacant u par L, et en faisant p=12, on obtient Ln+12=F11Ln+F12Ln+1=89Ln+144Ln+1.
Mais 89 ≡ 1 (8), 144 ≡ 0 (8), donc Ln+12≡ Ln (8).

6d)

On va procéder par récurrence pour prouver que pour tout entier naturel n3, on a Fn > an-2.

Comme a>1, limn->+Fn=+.

6e)

On va procéder, là aussi, par récurrence pour prouver que pour tout entier naturel non nul on a an=aFn+Fn-1.
(On peut aussi utiliser le 1) de P3).


La relation est encore vraie si on remplace a par b, puisque de même que a+1=a2, on a b+1=b2.

Par différence membre à membre des deux relations an=aFn+Fn-1 et bn=bFn+Fn-1, on obtient tout de suite Fn=(1/5)(an-bn).

Prouvons maintenant la relation an=Fn+1-bFn.
Elle est évidemment vraie pour n=0.
Pour n1, on utilise la relation précédente :
an=aFn+Fn-1= aFn+Fn+1-Fn=(a-1)Fn+Fn+1=Fn+1-bFn.

6f)

Notons G0=0 et pour tout entier naturel n1, Gn=S0k(n-1)/2Cn-1-kk.
On a G0=0=F0 et G1=C10 =1=F1.
On va alors montrer que la suite (G) est une suite de Fibonacci, et donc, cf P3, on aura (G)=(F), soit Fn=Gn pour tout entier naturel, ce qui prouvera la relation demandée.
Notons que si n est impair, le dernier terme de Gn correspond à k=(n-1)/2 et il vaut 1 et Gn posséde (n-1)/2+1=(n+1)/2 termes.
Par contre si n est pair le dernier terme de Gn correspond à k=l'entier immédiatement inférieur à (n-1)/2=n/2-1/2, soit n/2-1=(n-2)/2 et vaut Cn/2(n-2)/2 =Cn/21 =n/2 et Gn posséde (n-2)/2+1=n/2 termes.
Calcul de s=Gn+Gn+1, avec n1. Rappelons que Cnp-1 +Cnp =Cn+1p, p étant un entier compris au sens large entre 1 et n.

Donc pour tout n1, on a Gn+Gn+1=Gn+2 ; mais c'est aussi vrai pour n=0, car G0+G1=0+C10 =1 et G2=C10 =1 : donc la suite (G) est bien une suite de Fibonacci, et cf ce qui a été dit ci-dessus on a (F)=(G), ce qui prouve la relation demandée.

Application (on vérifiera la remarque ci-dessus sur le nombre de terme du S et sur son dernier terme) :

6g)

Une récurrence facile donne le résultat : notons pour tout entier naturel n1, Sn=S0in(-1)iFi.

Remarque : par ajout membres à membres des relations (-1)n+2Fn+2=(-1)n+2(Fn+1+Fn), on obtient aussi le résultat.

6h)

Là aussi une récurrence facile donne le résultat : pour tout entier naturel n1, on pose Sn=S1in2n-iFi-1.

7a) On a u0=2030=1

Donc la suite (u) est périodique : 1, 7, 13, 19, 1, 7, 13, 19, 1.....

7b) Supposons d'abord a1 (comme b)

Le 1er terme de la suite (u) dont la décomposition en nombres premiers ne contient que 2 et 3 est bien 2b3a+b.

Reste le cas a=0, b restant 1 : 2a3b=3b.
Cette fois on ne peut pas commencer par multiplier par 5×7/2 comme ci-dessus.
En fait, c'est comme pour la question a) :
on commence par multiplier par 7 et on obtient u1=3b7, qui est de la forme 3b5a7 (avec a=0), et on peut alors reprendre le raisonnement ci-dessus à partir de la multiplication par 13/7, ce qui nous fait arriver à encore à 2b3a+b=2b3b.

8)

a) Cf P4, un=aan+bbn, avec a=(-bu0+u1)/r, b=(au0-u1)/r et r=51/2.
Je laisse alors le lecteur vérifier que (on remarquera que akbs-k=(-1)kbs-2k, puisque ab=-1)
S1=S2=3a3as+3b3bs+ab2K+a2bK' avec

b) Pour calculer S1 et S2 dans le cas particulier demandé (s=15), il y a deux méthodes possibles :

9) Il a été vu dans la note de la remarque 2 de P4 que

An=Fn-1Fn=FnA+Fn-1I
èFnFn+1
avec
A=01
è11
On élève alors à la puissance k la relation An=FnA+Fn-1I et on développe par la formule du binôme le membre de droite, ce qui donne
Ank=∑0≤p≤kCkp FnpFn-1k-pAp.
Il ne reste plus qu'à identifier les éléments situées en (2,1) de chaque membre pour obtenir la formule souhaitée (cf F0=0, on peut commencer la sommation à p=1) :
Fkn=∑1≤p≤kCkp FpFnpFn-1k-p.
Ce qui donne

10) a) Montrons que pour tout p premier distinct de 3, 2 divise Fn+2p-Fn+p-Fn :

les restes des trois nombres n+2p, n+p, n lorsqu'on les divise par 3 sont distincts, car si deux restes étaient égaux, par différence des deux nombres correspondants , 3 diviserait p, ce qui est exclu par hypothse.
Donc parmi les trois nombres n+2p, n+p, n, un a pour reste 0, un a pour reste 1 et un a pour reste 2, donc un et un seul est divisible par 3 ; or cf la question 6c)1) ci-dessus, Fn est pair si et seulement si 3 divise n : donc parmi les trois nombres Fn+2p, Fn+p,Fn un et un seul est pair, ce qui prouve que Fn+2p-Fn+p-Fn est pair.
Note : il est évident que si p=3, cf toujours le fait que Fn est pair si et seulement si 3 divise n, soit n divise 3 et alors Fn+6, Fn+3, Fn sont tous pairs donc Fn+6-Fn+3-Fn est pair, par contre si n ne divise pas 3, les trois nombres sont impairs et Fn+6-Fn+3-Fn est cette fois impair.

b) On utilise maintenant les résultat de la question 4) ci-dessus : pour toute suite de Fibonacci (u) on a
pour tout n≥p, un+p=S0jpCpj un-j, soit en changeant n en n+p,
pour tout entier naturel n, un+2p=S0jkCpj un+p-j.
Or, cf un rsultat d'arithmtique, p tant premier, p divise Cpj pour j distinct de 0 et p.
Donc, pour tout nombre premier (même 2 ou 3) et si u0 et u1 sont des entiers, p divise un+2p-un+p-un.
En particulier, tout nombre premier p divise Fn+2p-Fn+p-Fn

D'o, si p est premier distinct de 3, on a la fois
2 et p qui divisent Fn+2p-Fn+p-Fn ; en rajoutant maintenant l'hypothèse p≠2, p et 2 sont alors premiers entre eux et 2p divise Fn+2p-Fn+p-Fn.

Exemples :
p=5, n=5 donnent 10 divise F15-F10-F5=610-45-5=560
Remarque : cf question 6c), 10 divise Fn <=> 15 divise n.
p=7, n=1 donnent 14 divise F15-F8-F1=610-21-1=588=14×42
p=11, n=1 donnent 22 divise F23-F12-F1=28657-144-1=28512=22×1296

c) Cas particuliers p=2 et p=3 :

d) On peut effectivement remplacer p par pr, avec r dans N, pour les rsultats a) et b) :
pour r=0, cele ne présente pas beaucoup d'intérêt car Fn+2pr-Fn+pr-Fn=0, et pour r=1 c'est le cas précédent.
Le problème c'est pour r≥2 :

Et ces rsultats sont encore vrais pour tout n dans Z :
on a vu (P2) que la relation de base Fn+2=Fn+1+Fn peut se prolonger à tout n dans Z : donc le a) est en core vrai.
En outre, cf le P5.3, F-n=(-)n+1Fn ce qui permet de justifier que la formule de de Binet est encore vraie, donc le résultat de la question 4) aussi, et donc le b) est encore vrai .

Par exemple, (p=5, r=2), pour tout n dans Z, 10 divise Fn+50-Fn+25-Fn.
Ce qu'on vérifie pour F53-F28-F3=53316291173-317811-2 et F44-F19-F-6=701408733-4181+8 qui sont bien divisibles par 10.

Exercice 2

1)
1.1) preuve de P5.1
On a un=aan+bbn.


1) si a=0, alors un=bbn, et comme |b|<1, limn->un=b×0=0.
Mais si a0, ca ne va plus être vrai car |a|=a>1.
Précisons : un=aan(1+(b/a)bn), et comme le terme entre parenthèses a pour limite 1 (puisque |b|<1), alors :
si a>0, limn->un=+ et si a<0, limn->un=-

2) C'est évident.

3) Rappelons qu'à partir d'un certain rang un0 (voir remarque 1 de P5) : les calculs ci-dessous sont donc faits pour n au delà de ce rang.
un+1/un=(aan+1+bbn+1) /(aan+bbn)= (aa+bb(b/a)n) /(a+b(b/a)n) ; comme |b/a|<1, limn->un+1/un=aa/a=a.
Précisons la vitesse de convergence :
a-un+1/un=a-(aan+1+bbn+1)/(aan+bbn)
=(abbn-bbn+1)/(aan+bbn)
=bbn(a-b)/(aan+bbn)
=b(b/a)n(a-b)/(a+b(b/a)n).
Comme le dénominateur de la dernière expression tend vers a, c'est qu'un équivalent de a-un+1/un est (b/a)(a-b)(b/a)n ; comme a-b=5, c'est que cet équivalent est bien (b/a)5(b/a)n.

Quelques précisions sur l'oscillation de un+1/un autour de a.
On a un+1/un-a =-(b/a)(b/a)n(a-b)/(1+(b/a)(b/a)n).
Notons vn=1+(b/a)(b/a)n (il est non nul, puisque on s'est placé dans le cas où un=aanvn est non nul) ; b/a étant <0, (b/a)n change de signe lorsque n augmente de 1.
Mais vn n'a pas toujours le méme signe ; cependant, puisque limn->+vn=1, à partir d'un certain rang, on est sûr que vn reste >0, et donc à partir de ce rang, un+1/un oscillera autour de a.
Exemple 1 : b/a=-100, donc un+1/un-a a le signe de (b/a)nvn, avec vn=1-100(a/b)n :

Ici, il y a oscillation de un+1/un à partir du rang 5.

Exemple 2 : b/a=-1 (c'est le cas de la suite (F), définie par F0=0, F1=1 : P4 donne alors tout de suite a=-b).
Dans ce cas vn=1-(b/a)n ; comme |b/a|<0.382, pour tout n1 on a |b/a|n<0.382, donc -0.382<(b/a)n<0.382, ce qui donne vn>0 pour tout n1, et un+1 converge vers a en oscillant à partir du rang 1 (ici u0=0).
On peut le vérifier sur la suite (F) : F2/F1=1<a, F3/F2=2>a, F4/F3=3/2<a,...

Exemple 3 : b/a=1 (c'est le cas de la suite (L) définie par L0=2, L1=1 : voir exercice 1 pour a=b=1)
Cette fois vn=1+(b/a)n, et l'encadrement ci-dessus donne, pour tout n1, (b/a)n>-0.382 (qui est encore vrai si n=0) et pour tout n0, on a vn>0, et donc un+1/un oscille autour de a dès le rang 0.
On peut le vérifier pour la suite (L) : L1/L0=1/2<a, L2/L1=3>a, L3/L2=4/3<a,...

Pour ce qui est de limn->+un+k/un=ak, il suffit de remarquer que, pour k entier naturel non nul, un+k/un=(un+k/un+k-1))(un+k-1/un+k-2)...(un+1/un) est un produit de k facteurs, chacun de ces facteurs ayant pour limite a lorsque n tend vers + ; si k=0 le résultat est trivial.

Remarque : de Fn+1=Fn+Fn-1, on tire Fn+1/Fn=1+Fn-1/Fn ; donc SI Fn+1/Fn a une limite finie L, nécessairement, par passage à la limite, L=1+1/L, soit L2-L-1=0 et donc L=a ou L=b ; mais il s'agit d'une suite à termes positifs ou nuls, et donc la limite, si elle existe, est aussi positive ou nulle. Donc, si Fn+1/Fn a une limite finie L, cette limite L ne peut être que a.
Mais cela ne prouve pas qu'effectivement la suite Fn+1/Fn converge vers a.

1.2) preuve de P5.2
Pour prouver que pour tout entier naturel n non nul, Fn=(1/2n-1)S0p(n-1)/25pCn2p+1, il suffit d'appliquer deux fois la formule du binôme dans Fn=(1/5)(an-bn) :
Fn=(1/5)(1/2n)(S0knCnk (5)k- S0knCnk (-1)k(5)k) : on voit tout de suite que les termes de chaque S correspondants à k pair (il y en a que si n est non nul) s'éliminent, et ceux correspondants à k impair s'ajoutent :

Fn=(1/5)(1/2n)(S0p, 2p+1nCn2p+1 (5)2p+1×2), ce qui donne le résultat.

Un calcul analogue donne la formule avec coefficients binômiaux relative à Ln.

Pour n premier, les valeurs modulo n de Fn et Ln s'obtiennent en remarquant que

Donc, si n est premier et impair, 2n-1Fn 5(n-1)/2Cnn (n), ce qui donne Fn 5(n-1)/2 (n) ; par exemple F7=13, et 5(7-1)/2=125 13 (7), puisque 125=13+16×7.

Quant au cas de la suite de Lucas, L2=3 1 (2), et si n est premier et impair, 2n-1Ln 50Cn0 (n), ce qui donne Ln 1 (n) ; par exemple L7=29, et 29 1 (7), puisque 29=1+4×7.

Quant à la formule dite de Moivre, sa preuve est évidente, les membres de droite et de gauche étant égaux à akn.

Justifions les deux formules

En développant le membre de gauche (de la formule de Moivre avec k=3) selon la formule du binôme on obtient (avec r=51/2)
L3n+rF3n=(2/23)(Ln3+3rLn2Fn+3×5LnFn2+5rFn3).
Mais si a,b,c,d sont quatre rationnels tels que a+rb=c+rd alors a=c et b=d : en effet si b était différent de d, on aurait r=(c-a)/(b-d), donc r serait rationnel, ce qui est impossible, et donc b=d, puis a=c.
L'application de ceci, c'est-à-dire l'identification des termes sans le facteur r et l'identification de ceux avec le facteur r, donne tout de suite les formules rappelées plus haut.

1.3) preuve de P5.3
On va utiliser la formule de Binet (P4) qui est aussi vraie pour tout n dans Z : en effet la preuve de P4 reste valable car de façon évidente vn=aan+bbn vérifie pour tout n dans Z la relation vn=vn-1+vn-2 et le 1) de P3 reste vrai si on remplace N par Z.
En notant r=5, on a alors, pour tout n dans Z, un=(u1(an-bn)+u0(abn-ban))/r.
Donc, en changeant n en -n et compte-tenu que ab=-1,
u-n=(-1)n(u1(bn-an)+u0(an+1-bn+1))/r,
ce qui donne (-1)n+1u-n=un+(u0/r)(bn+1-an+1-abn+ban),
soit (-1)n+1u-n=un+(u0/r)(bn(b-a)-an(a-b)),
et comme a-b=r, on obtient (-1)n+1u-n=un-u0Ln, soit u-n=(-1)n+1(un-u0Ln) .

On en déduit :
si u0=0, u-n=(-1)n+1un
si 2u1=u0 alors a=b=u1 (voir P4) et un=u1(an+bn)=u1Ln,d'où
u-n=(-1)n+1(un-u0un/u1)=(-1)n+1(un-2un)=(-1)nun ; bien sûr ce calcul est licite que si u1 est non nul, mais si u1=0, alors u0 est aussi nul, et donc la suite (u) est telle que pour tout n dans Z, un=0 et le résultat est encore vrai.

1.4) preuve de P5.4
Puisque a=el, b=-1/a=-e-l.
F2n=(1/5)(a2n-b2n)=(1/5)(e2nl-(-1)2ne-2nl)
=(1/5)(e2nl-e-2nl)=(2/5)sinh(2nl)

F2n+1=(1/5)(a2n+1-b2n+1)
=(1/5)(e(2n+1)l-(-1)2n+1e-(2n+1)l)
=(1/5)(e(2n+1)l+e-(2n+1)l)
=(2/5)cosh((2n+1)l)

Les résultats relatifs L2n et L2n+1 s'obtiennent de façon identique à partir de Ln=an+bn.

2)
On utilise la formule de Lucas-Fibonacci-Moivre de P5.2 et on développe le membre à la puissance k, ce qui donne (voir justification de l'identification à la preuve de P5.2 ci-dessus) :
Lkn=(1/2k-1)(∑0≤2j≤k Ck2j 5j Fn2jLnk-2j).
D'où, si k est impair, l'exposant k-2j de Ln est toujours positif non nul et donc Ln divise Lkn.

Exercice 3
1) Posons vn=unxn=(aan+bbn)xn et cherchons le rayon de convergence de cette série entière ; on sait que pour n assez grand un est non nul et que limn->+un+1/un=a, donc limn->+|un+1/un|=a et ainsi le rayon de convergence de cette série est 1/a=|b|.
Pour |x|<|b| on a

En ajoutant membres à membres ces trois égalités on obtient (1-x-x2)G(x)=u0+(u1-u0)x+0x2+0x3+..., et donc G(x)=(u0+(u1-u0)x)/(1-x-x2) (pour |x|<|b|, 1-x-x2 est non nul, puisque cette expression ne s'annule que pour a et b, dont les valeurs absolues ne sont pas strictement inférieures à |b|).
Un autre moyen de déterminer G(x) est d'utiliser la formule de Binet : unxn=a(ax)n+b(bx)n, qui est une somme de deux séries géométriques (puisque a et b sont non nuls) de rayons respectifs de convergence 1/|a|=|b| et 1/|b|=a ; le plus petit de ces rayons de convergence est |b| qui est donc le rayon de convergence de la série somme, et on a alors pour |x|<|b|,
G(x)=a/(1-ax)+b/(1-bx)=(a+b-(ba+ab)x)/(1-x-x2), cela en utilisant deux fois 1+z+z2+z3+....=1/(1-z) pour |z|<1.
On vérifie tout de suite que a+b=u0 (en fait cela a déjà été vu à P4) et -ba-ab=b(b-1)+a(a-1)= aa+bb-(a+b)=u1-u0.

Dans le cas b=0, a0, vn=a(ax)n est une série géométrique de raison ax et donc de rayon de convergence 1/|a|=|b| et de somme G(x)=a/(1-ax)=u0/(1-ax).

Dans le cas a=0, b0, vn=b(bx)n est une série géométrique de raison bx et donc de rayon de convergence 1/|b|=a et de somme G(x)=b/(1-bx)=u0/(1-bx).

En fait si b=0, G(x)=(u0+(u1-u0)x)/(1-x-x2) se simplifie en G(x)=u0/(1-ax) et si b=0, G(x)=(u0+(u1-u0)x)/(1-x-x2) se simplifie en G(x)=u0/(1-bx). En effet :

si b=0 on a u1-u0=-ab=-u0b et ainsi
(u0+(u1-u0)x)/(1-x-x2)=u0(1-bx)/((ax-1)(bx-1))=u0/(1-ax)
si a=0 on a u1-u0=-ba=-u0a et ainsi
(u0+(u1-u0)x)/(1-x-x2)=u0(1-ax)/((ax-1)(bx-1))=u0/(1-bx).
2) On développe le produit (1-x-x2)(u0+u1x+...+unxn), et compte-tenu de la relation uk+uk+1=uk+2, on obtient tout de suite (1-x-x2)(u0+u1x+...+unxn)=u0+(u1-u0)x-un+1xn+1-unxn+2
1-x-x2 étant nul que pour x=-a ou x=-b (donc le second membre est aussi nul pour ces deux valeurs de x, ce qu'on peut vérifier par un calcul direct en utilisant la formule de Binet pour un et un+1 : voir note ci-dessous), pour x différent de -a et -b on peut diviser les deux membres par 1-x-x2 et on obtient (u0+u1x+...+unxn)=(u0+(u1-u0)x-un+1xn+1-unxn+2)/(1-x-x2)

Pour retrouver P6.1, on suppose |x|<|b|=1/a (donc x est bien différent de -a et de -b) et on fait tendre n vers l'infini dans la relation qui vient dêtre trouvée.
Cf Binet,unxn=a(ax)n+b(bx)n, et puisque |ax|<1, |bx|<|b|2<1, unxn tend vers 0 (c'est une somme de deux termes qui tendent vers 0), et donc il en est de même pour un+1xn+1 et unxn+2=unxnx2, et ainsi le membre de droite tend vers (u0+(u1-u0)x)/(1-x-x2), ce qui redonne P6.1.

Note : retrouvons par un calcul direct que u0+(u1-u0)x-un+1xn+1-unxn+2 est bien nul pour x=-a.
On obtient alors (voir P4 pour a et b)
u0+(u1-u0)(-a)+(-1)n(aa2n+2+b(ab)n+1)-(-1)n(aa2n+2+b(ab)na2)
=u0+(u1-u0)(-a)-b-ba2, puisque ab=-1
=a+(ab+ba)a-ba2, puisque u0=a+b et u1-u0=a(a-1)+b(a-1)=-ab-ba
=a+a(-1)=0

3) En posant r=1/5, on a F2nxn=r(a2x)n-(b2x)n), différence de deux suites géométriques, qui convergent toutes les deux si et seulement si |a2x|<1 et |b2x|<1, ce qui équivaut à |x|<b2, puisque ab=-1, |b|<a.
Donc, pour |x|<b2, H(x)=Sn=0+F2nxn=r(1/(1-a2x)-1/(1-b2x)), ce qui donne, puisque a2+b2=(a+b)2-2ab=1+2=3 et a2-b2=(a-b)(a+b)=1/r,
H(x)=x/(1-3x+x2).

F2n+1xn=r(a(a2x)n-b(b2x)n),
d'où, pour |x|<b2, K(x)=Sn=0+F2n+1xn=r(a/(1-a2x)-b/(1-b2x))=r(a-b+ab(a-b)x)/(1-3x+x2), soit
K(x)=(1-x)/(1-3x+x2).

Remarque : autre façon d'obtenir K(x), en utilisant H(x).
H(x)+K(x)=Sn=0+(F2n+F2n+1)xn=Sn=0+F2n+2xn, et donc
x(H(x)+K(x))=Sn=0+F2(n+1)xn+1=H(x)-F0=H(x), soit xK(x)=(1-x)H(x).

(Fn)2xn=(1/5)((a2x)n+(b2x)n-2(-x)n) ; on a cette fois une somme de trois séries géométriques qui convergent toutes les trois si et seulement si |x|<b2 (min des trois rayons de convergence),
d'où, pour x<|b|2,
L(x)=Sn=0+(Fn)2xn=(1/5)(1/(1-a2x)+1/(1-b2x)-2/(1+x))=(1/5)((2-3x)/(1-3x+x2)-2/(1+x)), soit
L(x)=(x-x2)/((1+x)(1-3x+x2)).

Remarque : autre façon d'obtenir L(x) en utilisant K(x) et la relation 3 de P8.
En effet, cette relation 3 donne :
pour tout n1, (Fn-1)2xn+(Fn)2xn=F2n-1xn, et donc par sommation, à partir de n=1,
xL(x)+L(x)-(F0)2=F1x+F3x2+ ... =xK(x), soit (1+x)L(x)=xK(x).

4) On remplace dans la relation P6.2, uk par Lk et x par eiq (quantité bien différente de -a et -b pour tout réel q) et on obtient, en posant A=Sk=0nLkcos(kq) et B=Sk=0nLksin(kq),
A+iB=U/V avec


On peut retrouver ce résultat en remarquant que A+iB=Sk=0n((aeiq)k+(beiq)k), somme de deux suites géométriques.

Le conjugué de V est W=1-e-iq-e-2iq et V×W=3-2cos(2q), ce qui donne A+iB=W×U/(3-2cos(2q)).
En développant (courageusement...), et en conservants "tels quels" Ln et Ln+1, on obtient

Quelques vérifications :

si q=0 alors
si n=1

Exercice 4

1) On applique P6.1 : Sn=0+Fnxn=x/(1-x-x2) et on fait x=1/2 (F0=0).

2) On dérive l'identité précédente (on peut dériver termes à termes une série entière à l'intérieur de l'intervalle de convergence), ce qui donne : Sn=1+nFnxn-1=(1+x2)/(1-x-x2)2, puis on fait x=1/2, et on divise des deux côtés par 2.

3) On applique P6.1 : Sn=0+Lnxn=(2-x)/(1-x-x2) et on fait x=1/2.

4) 1/89=0,01123599550... : les six premiers chiffres de ce développement décimal sont exactement les six premiers termes de la suite de Fibonnacci : 0,1,2,3,5 ; par contre après 5 on n'a pas 8 mais 9.
L'explication vient encore de la fonction génératrice : en faisant x=1/10 dans Sn=0+Fnxn+1=x2/(1-x-x2), on obtient 1/89=F1/100+F2/1000+F3/10000+F4/100000+F5/1000000+F6/10000000+......
soit 1/89=0,011235+F6/107+F7/108+....
Or si F6/107=0,0000008, ce 8 ne vient pas se mettre après le 5 car ensuite arrive F7/108=0,00000013 qui ajouté au précédent donne 0,00000093, ce qui explique le 9 après le 5.
Mais on peut tout de même se poser la question de savoir si l'ajout de A=Sk=6+Fk/10k+1 à 0,011235=Sk=05Fk/10k+1 ne va pas modifier les décimales de ce dernier! (cette question est parfois passée sous silence...).
En fait il n'en est rien car A<10-6.
A=10-6(u6+u7+.....), avec un=Fn/10n-5. On observe que un+1/un=(1/10)Fn+1/Fn<1/5, car Fn+1=Fn+Fn-1<2Fn, pour n3 (voir exercice 1, Q6).
Donc A<10-6u6(1+(1/5)+(1/5)2+...)=10-6(F6/10)(1/(1-1/5))=10-6.

5) 1/9899=0,000101020305081321345590... : si on découpe en tranches de deux chiffres les chiffres de ce développement décimal, on obtient exactement les onze premiers termes de la suite de Fibonacci, mais là aussi, après 55=F10, on n'a pas comme chiffres suivants 8 et 9 (89=F11) mais 9 et 0
L'explication vient toujours de la fonction génératrice :
en faisant x=1/100 dans Sn=0+Fnxn+1=x2/(1-x-x2),
on obtient 1/9899=F1/104+F2/106+...+F10/1022+F11/1024+F12/1026+...
soit 1/9899=0,0001010203050813213455+F11/1024+F12/1026+....
Or si F11/1024=0,000000000000000000000089, ce 89 ne vient pas se mettre après le 55 car ensuite arrive F12/1026=0,000000000000000000000000144 qui ajouté au précédent donne 0,00000000000000000000009044, ce qui explique le 9 après le 55.
Montrons là aussi que l'ajout de A=Sk=11+Fk/102k+2 à 0,0001010203050813213455=Sk=010Fk/102k+2 ne va pas modifier les décimales de ce dernier.
A=10-22(u11+u12+.....), avec un=Fn/102n-20. On observe que un+1/un=(1/100)Fn+1/Fn<1/50.
Donc A<10-22u11(1+(1/50)+(1/50)2+...)=10-22(F11/100)(1/(1-1/50))=10-22(89/98)<10-22.

Exercice 5
1) un=Fn+Ln et vn=2Fn+1 sont deux suites de Fibnacci cf le 2) de P3 ; or u0=0+2=2=2F1=v0, et u1=1+1=2=2F2=v1, et donc cf le 1) de P3, les suites (u) et (v) sont égales.

2) cf 1), Ln=2Fn+1-Fn=2Fn+1-(Fn+1-Fn-1)=Fn-1+Fn+1

3) Posons pour n entier naturel un=Ln+Ln+2 et vn=5Fn+1 : ce sont deux suites de Fibonacci, cf le 2) de P3. Or u0=2+3=5=5F1=v0 et u1= 1+4=5=2F2=v1, et cf le 1) de P3, les suites (u) et (v) sont égales.

4) cf 2), (Fn+Fn+2)+(Fn+1+Fn+3)=Ln+1+Ln+2=Ln+3.

5) On procéde par récurence : posons Sn=S0in2iLi.

Exercice 6
1) On utilise la formule de Binet : un=aan+bbn, avec a=(-bu0+u1)/5 et b=(au0-u1)/5.
(un)2=a2a2n+b2b2n+2ab(-1)n, car ab=-1.
un-1un+1=a2a2n+b2b2n+aban-1bn+1+ aban+1bn-1, d'où
(un)2-un-1un+1=2ab(-1)n-ab(ab)n-1(a2+b2) ; mais a2+b2=(a+b)2-2ab=1-2×(-1)=3, et
(un)2-un-1un+1=2ab(-1)n-3ab(-1)n-1=5ab(-1)n.
Il ne reste plus qu'à remplacer a et b par leurs valeurs en fonction de u0 et u1.

2) Application immédiate du 1).
On peut aussi utiliser la matrice A de la remarque 2 de P4 : en effet, Fn-1Fn+1-Fn2 n'est autre que le déterminant de la matrice An, donc Fn-1Fn+1-Fn2=|det(A)|n=(-1)n.

On en déduit qu'il existe deux entiers relatifs u et v (dépendants de n) tels que uFn-1+vFn=1, donc d'après cette relation de Bezout, Fn-1 et Fn sont premiers entre eux (leurs diviseurs communs sont -1 et 1), et on retrouve le résultat de l'exercice 1.
Remarque : si on applique 1) à la suite de Lucas on obtient (Ln)2-Ln-1Ln+1=5(-1)n, qui ne donne pas cette fois une relation de Bezout entre Ln-1 et Ln. Cependant ils sont bien premiers entre eux, cf exercice 1.

Pour établir la formule de Catalan, je reviens à Binet (rappel ab=-1) :
(Fn)2-Fn-pFn+p=(a2n+b2n-2(-1)n)/5-(an-p-bn-p)(an+p-bn+p)/5=(-2(-1)n+an+pbn-p+an-pbn+p)/5
=(-1)n(-2+(a/b)p+(b/a)p)/5=(-1)n(-2+(a2p+b2p)/(-1)p)/5=(-1)n-p(-2(-1)p+a2p+b2p)/5, expression qui est bien égale à (-1)n-p(Fp)2.

3) Fn=(1/5)(an-bn) donne
(Fn)2+(Fn+1)2=(1/5)(a2n+ b2n-2(ab)n+ a2n+2+b2n+2-2(ab)n+1)
=(1/5)(a2n(1+a2)+ b2n(1+b2))=(1/5)(a2n (2+a)+b2n(2+b)),
=(1/5)(a2n(5+5)/2+b2n(5-5)/2)=1/(5)(a2n(5+1)/2+b2n(5-1)/2)
=(1/5) (a2n+1-b2n+1)=F2n+1.
Par exemple (F3)2+(F4)2=F7, ce qu'on vérifie puisque F3=2, F4=3 et F7=13.

Remarque : (F1)2+(F2)2+(F3)2=1+1+4=6, qui n'est pas un terme de (F) : on ne peut pas linéariser (Fn)2+(Fn+1)2+(Fn+2)2.
En fait (F1)2+(F2)2+(F3)2=F2F3 : voir la relation 14) ci-après.

Pour la 2ième formule, il suffit d'utiliser deux fois le 2) : (Fn)2=Fn-1Fn+1+(-1)n-1 et (Fn+1)2=FnFn+2+(-1)n, ce qui donne la formule voulue par ajout membres à membres.

4) Fn+2Fn-1=(Fn+1+Fn)(Fn+1-Fn)=(Fn+1)2-(Fn)2.

Pour la 2ième relation, on va utiliser Binet :
(Fn+1)2-(Fn)2=((an+1-bn+1)2-(an-bn)2)/5 =(a2n+2+b2n+2-2(ab)n+1-a2n-b2n+2(ab)n)/5
=(a2n(a2-1)+b2n(b2-1)+4(-1)n)/5=(L2n+1+4(-1)n)/5.
Cette formule prouve que 5 divise L2n+1+4(-1)n, cad L2n+1-4(-1)n (5) ; mais -41 (5) et ainsi L2n+1(-1)n (5).

5) Posons, pour n2, wn=Fn-2Fn+2-Fn-1Fn+1.
wn+1=Fn-1Fn+3-FnFn+2= Fn-1(Fn+2+Fn+1)-(Fn-1+Fn-2)(Fn+1+Fn).
wn+1=Fn-1(Fn+2-Fn)-Fn-2(Fn+1+Fn)= Fn-1Fn+1-Fn-2Fn+2=-wn.
Donc wn=(-1)n-2w2 ; comme w2=-F1F3=-2, on obtient wn=-2(-1)n-2=2(-1)n-1.

6) On élève 2) au carré : (Fn)4=(Fn-1Fn+1+(-1)n-1)2= (Fn-1)2(Fn+1)2+1+2(-1)n-1Fn-1Fn+1, et on applique 5) pour transformer le 2(-1)n.
(Fn)4=(Fn-1)2(Fn+1)2+1+Fn-1Fn+1(Fn-2Fn+2-Fn-1Fn+1)=Fn-2Fn-1Fn+1Fn+2

7) La formule de Binet donne tout de suite

(Ln)2=a2n+b2n+2(ab)n=L2n+2(-1)n
(Fn)2=(1/5)(a2n+b2n-2(ab)n)=(1/5)(L2n-2(-1)n)
D'où par ajout on obtient (Ln)2+5(Fn)2=2L2n et par différence, (Ln)2-5(Fn)2=4(-1)n, soit 5(Fn)2+4(-1)n=(Ln)2.
Et aussi, (Ln)2-4(-1)n est divisible par 5, soit (Ln)24(-1)n (5) et comme 4-1 (5), (Ln)2(-1)n+1 (5).

8) F2n=(1/5)(a2n-b2n)= (1/5)(an-bn)(an+bn) =FnLn=Fn(5(Fn)2+4(-1)n)1/2.

9) Du résultat précédant on tire F8n=F4n(5(F4n)2+4)1/2 et F4n=F2n(5(F2n)2+4)1/2.
Donc 5(F4n)2+4=5((F2n)2(5(F2n)2+4))+4= 25(F2n)4+20(F2n)2+4=(5F2n+2)2, et ainsi F8n=F4n(5(F2n)2+2).
Par exemple F16=F8(5(F4)2+2)=21(5×32+2)=987, et donc
F32=F16(5(F8)2+2)=987(5×212+2)=2178309,
F64=F32(5(F16)2+2)=217809(5×9872+2)=2178309×4870847=10610209857723.

10) Pour prouver que pour pour tous les entiers naturels n et p (p non nul), Fn+p=Fn+1Fp+FnFp-1, on va faire une récurrence sur p, n étant fixé.

Pour la 2ième égalité, il suffit de remarquer que Fn+1Fp+FnFp-1=Fn+1(Fp+1-Fp-1)+(Fn+1-Fn-1)Fp-1=Fn+1Fp+1-Fn-1Fp-1.

11) FnFp=(1/5)(an-bn)(ap-bp)= (1/5)(an+p-anbp-apbn+bn+p), d'où
Fn+aFp-a=(1/5)(an+p-an+abp-a-ap-abn+a+bn+p), et
FnFp-Fn+aFp-a=(1/5)(-anbp-apbn+an+abp-a+ap-abn+a)
On remarque alors que si dans chacun des quatre termes de la parenthèse on remplace n par n-b et p par p-b, chacun de ces termes est multiplié par a-bb-b=(ab)-b=(-1)-b=(-1)b, et donc
FnFp-Fn+aFp-a=(-1)b(Fn-bFp-b-Fn-b+aFp-b-a).

12) Pour la relation d'Ocagne, on fixe p et on fait un récurrence sur n, à partir de n=p :

Pour l'autre relation,
posons gn=FnLp-FpLn et dn=2(-1)pFn-p.
Fixons p : alors cf P3, gn et dn sont des suites de Fibonacci, pour n dans Z.
Et

Donc cf P3, les 2 suites de Fibonacci (g) et (d) sont égales sur Z, cad
pour tout p et n dans Z, FnLp-FpLn=2(-1)pFn-p.
En fait ici on a montré plus que ce demandait l'énoncé, puisque ce dernier se limitait à n≥p≥0.

Remarque : le cas particulier Fp+1Lp-FpLp+1=2(-1)p (cad gp+1=dp+1) se vérifie facilement avec Binet ; en fait toutes ces relations du 12) peuvent se prouver facilement par Binet, mais faut faire les calculs...

13) Une récurrence immédiate donne le résultat.
En effet, en posant Sn=S1k nF2k-2F2k-1+F2k-1F2k :

14) Là aussi une récurrence immédiate donne le résultat.
En effet, en posant Sn=S1k n(Fk)2 :

15) Les deux premières relations sont des applications immédiates de la formule de Binet :
FmLn+LmFn=(1/5)((am-bm)(an+bn)+(am+bm)(an-bn))=(1/5)(2am+n-2bm+n)=2Fm+n

5FmFn+LmLn=(am-bm)(an-bn)+(am+bm)(an+bn))=2am+n+2bm+n=2Lm+n

En changeant n en -n, ces deux formules donnent les deux suivantes, puisque cf P5.3, on a F-n=(-1)n+1Fn et L-n=(-1)nLn.

Les trois dernières relations s'obtiennent aussi de façon immédiate avec Binet.
Mais on peut aussi les obenir par ajout membre à membre (avec coefficients multiplicateurs bien choisis) de deux des quatre premières relations.
Par exemple, Lm+n-(-1)nLm-n=(5FmFn+LmLn)/2-(-1)n(-1)n(LmLn-5FmFn)/2=10FmFn/2=5FmFn.

Applications :

Sans utiliser la relation 12 de P8, prouvons que pour tous les entiers naturels n et p, si d divise Fn et Fp, alors d divise Fn-p.

C'est évidemment vrai si n=p, puisque F0=0.
On suppose maintenant que n-p≥1.
Par application de la relation 10 de P8, en y remplacant n par p et p par n-p (qui est bien non nul),
on obtient Fn=Fp+1Fn-p+FpFn-p-1, et donc d divise Fp+1Fn-p.
Mais cf la relation 2 de P8, Fp et Fp+1 sont premiers entre eux, donc d et Fp+1 sont aussi premiers entre eux (sinon il existe d'>1 divisant d et Fp+1, et comme d divise Fp, c'est que d' divise aussi Fp et alors on est en contradiction avec Fp et Fp+1 premiers entre eux).
Le théorème de Gauss permet alors de dire que d divise effectivement Fn-p.
Reste le cas n<p : cf ce qui précéde, d divise Fp-n ; et comme Fn-p est au signe près Fp-n on a encore d divise Fn-p.

Exercice 7
1)a
|wn+1/wn|=|un/un+2|, qui a pour limite (cf le 3) de P5.1), lorsque n tend vers +, |1/a|2=b2<1, ce qui prouve l'absolue convergence de la série wn.
Le 1) de P8 donne (un)2-un-1un+1=5ab(-1)n, avec 5ab=(u0)2-(u1)2+u0u1. Vu l'hypothèse faite sur a et b, le coefficient 5ab est non nul : notons le 1/C.
On a alors C((un+1)2-unun+2)/(unun+1)=(-1)n+1/(unun+1), soit
(-1)n-1/(unun+1)=C(vn-vn+1) avec vn=un+1/un, et ainsi Sn=kN (-1)n-1/(unun+1)=C(vk-VN+1) ; en faisant tendre N vers + on obtient
Sn=k+ (-1)n-1/(unun+1)=(1/((u0)2-(u1)2+u0u1))(uk+1/uk-a).

1)b
Pour la suite (F), on a F0=0, F1=1, k=1 et ainsi Sn=1+ (-1)n-1/(FnFn+1)=-(F2/F1-a)=a-1.
Pour la suite (L), on a L0=2, L1=1, k=0 et ainsi Sn=0+ (-1)n-1/(LnLn+1)=(1/5)(L1/L0-a)=(1-2a)/10.

2) Le dfc du nombre d'or est constitué que de 1 :

a=1+1/(1+1/(1+1/(1+1/(1+1/(...))))

et si Pn/Qn est sa réduite d'ordre n, on a notamment En fait pour tout n2 on a Comme Q0=Q1=1, c'est que pour tout n0 on a Qn=Fn+1, alors que Pn=Fn+2 (puisque P0=1 et P1=2) ;
Or (cela résulte d'une propriété générale sur les dfc) a=1+Sn=1+ (-1)n-1/(QnQn-1), et donc
a=1+Sn=1+ (-1)n-1/(FnFn+1), ce qui redonne le 1er résultat de 1)b.

Remarque : un autre résultat sur les dfc dit que Pn/Qn a pour limite a lorsque n tend vers +, cela en oscillant autour de a : comme Pn/Qn=Fn+2/Fn+1, on retrouve alors la remarque 2 de P5.1

3) 1/(FnFn+2)=(Fn+2-Fn)/(FnFn+1Fn+2)=1/(FnFn+1)-1/(Fn+1Fn+2)=vn-vn+1, avec vn=1/(FnFn+1).
D'où Sn=1+ 1/(FnFn+2)=v1-0=1/(F1F2)=1.

4) Voir ouvrage de Daniel Duverney, Théorie des nombres, exercice 4.16.

5) Puisque 0<1/(1+F2n+1)<1/F2n+1 et que la série 1/Fn converge (voir l'introduction des exercices 7 et 8), la série 1/(1+F2n+1) est bien convergente.
Cf la relation 15.7 de P10, F2n+1=Fn+1Ln+(-1)n+1 et F2n-1=Fn-1Ln+(-1)n+1.
D'où si n pair on remplace F2n+1 par Fn+1Ln-1, et si n impair on remplace F2n+1=F2(n+1)-1 par FnLn+1-1,
ce qui donne 1/(1+F2n+1)=1/(Fn+1Ln) pour n pair et 1/(1+F2n+1)=1/(FnLn+1) pour n impair.
On obtient alors
n≥0 1/(1+F2n+1)=1/(F1L0)+1/(F1L2)+1/(F3L2)+1/(F3L4)+1/(F5L4)+1/(F5L6)+1/(F7L6)+.......
n≥0 1/(1+F2n+1)=1/2+∑n≥0 1/(F2n+1L2n+2)+1/(F2n+3L2n+2).
Rappel : lorsqu'une série est convergente, on ne change pas sa somme en faisant une sommation par "paquets" de au plus k termes, k étant un nombre donné : ici k=2.
Enfin, cf la relation 2) de P7, F2n+1+F2n+3=L2n+2, d'où
n≥0 1/(1+F2n+1)=1/2+∑n≥0 1/(F2n+1F2n+3), soit cf Q4,
n≥0 1/(1+F2n+1)=1/2+(√5-1)/2=√5/2.

Exercice 8
1) On va utiliser la relation 11 de P8 :
FnFp-Fn+aFp-a=(-1)b(Fn-bFp-b-Fn-b+aFp-b-a), en prenant b=p-a, ce qui donne, puisque F0=0
FnFp-Fn+aFp-a=(-1)p-a(Fn-p+aFa), pour n0, pa0, n+ap (pour que tous les indices soient 0).
Prenons maintenant n=2q+k-2q, p=2q+k-1, a=2q, avec k1 (qui assure que pa ; par ailleurs on a bien n0, a0, n+ap).
On notera que p-a=2q(2k-1-1) est toujours pair, car q1.
On a donc F(2q+k-2q)F(2q+k-1)-F(2q+k)F(2q+k-1-2q)=F(2q+k-2q+k-1)F(2q), et en divisant les deux membres par F(2q+k)F(2q+k-1), on obtient (puisque 2q+k-2q+k-1=2q+k-1)
(F(2q+k-2q))/(F(2q+k))-(F(2q+k-1-2q))/(F(2q+k-1))=(F(2q))/(F(2q+k)),
soit en posant rk=(F(2q+k-2q))/(F(2q+k)),
rk-rk-1=(F(2q))/(F(2q+k)) ; une sommation évidente donne alors
Sk=1K (F(2q))/(F(2q+k))=rK-r0=rK ; or 1/rK=(F((2q+K-2q)+2q))/(F(2q+K-2q)), dont la limite, lorsque K tend vers + est ae, avec e=2q, d'après le 3) de P5.1.
Ce qui donne bien Sk=1+ (F(2q))/(F(2q+k))=1/(ae).

2) On utilise ce qui vient d'être fait, mais en faisant attention, car cette fois p-a=2k-1-1 est impair, sauf pour k=1 et donc
cette fois on n'a pas toujours rk-rk-1=1/(F(2k)), mais rk-rk-1=-1/(F(2k)), sauf pour k=1 où il n'y a pas le signe moins, ce qui donne
Sk=1K 1/(F(2k))=r1-r0 -(r2-r1)-(r3-r2)+...-(rK-rK-1)= 2r1-r0-rK=2F1/F2-rK, avec cette fois 1/rK=(F(2K))/(F(2K-1)).
Donc k=1K 1/F(2k)=2-F(2K-1)/F(2K) ,et finalement, toujours cf le 3) de P5.1,
Sk=1+ 1/(F(2k))=2-1/a=2+b=(5-5)/2

Voici une autre façon de prouver cette formule :

Exercice 9
1) Posons dn=a(Fn+1)-(Fn+1+1). On a :
dn=(a/5)(an-bn)+a-(1/5)(an+1-bn+1)-1= (1/5)(-abbn-1+a5+bn+1-5) ; or ab=-1, donc dn=(1/5)(a5-5+bn-1+bn+1)=a-1+(1/5)bn-1(1+b2).
Mais (1+b2)/5=(2+b)/5=(5-5)/(25)=-b, ce qui donne
dn=-b-bn, cela pour tout entier naturel n.

d0=-b-1=a-2 (c'est bien a(F0+1)-(F1+1)) : d0<0, donc d0[0;1[
d1=-2b=-2+2a (c'est bien a(F1+1)-(F2+1)) : d1>1, donc d1[0;1[
d2=-b-b2=-1-2b[0;1[
(Rappel : a=1,61803..., b=-0,61803... et a, b sont les deux solutions de x2+x+1=0)
En fait, puisque b3=-0,23606..., et que |b|<1, c'est que "n3, on a |bn|<0,237 et ainsi pour n3,
dn]-b-0,237;-b+0,237[[0;1[.
Finalement pour n2, a(Fn+1)=Fn+1+1+dn avec dn[0;1[ : donc E(a(Fn+1))=Fn+1+1, cela par définition de la partie entière.
Par contre, pour n=0 ou 1, ce résultat est faux puisque l'on a vu que d0 et d1 ne sont pas dans [0;1[.

Remarque : ce résultat permet de retrouver que limn->+Fn+1/Fn=a (voir P5.1).
En effet pour n2, il permet d'écrire Fn+1+1a(Fn+1)<Fn+1+2, ce qui donne, en divisant par Fn, a(1+1/Fn)-2/Fn<Fn+1/Fna(1+1/Fn)-1/Fn. Et, lorsque n tend vers +, les membres de gauche et de droite de cette double inégalité tendent vers a : il en est donc de même pour le terme central Fn+1/Fn (cf théorème des gendarmes, ou selon les goûts, théorème des sandwichs).

2)F0=0 est bien l'entier le plus proche de a0/5@0,45.
Puisque |b|<0,62 alors, pour tout entier naturel n non nul on a |b|n<0,62, donc -0,28<-bn/5<0,28 et finalement
an/5-0,28<Fn<an/5+0,28. D'où, pour n entier naturel non nul

Ceci prouve que Fn est l'entier le plus proche de an/5.

3) L0=2 n'est pas l'entier le plus proche de a0=1,
et L1=1 n'est pas l'entier le plus proche de a1@1,6.
Mais pour un entier naturel n2, on a |b|n|b|2<0,384 et ainsi
-0,384<bn<0,384, soit an-0,384<Ln<an+0,384.
D'où pour n entier naturel2

Ceci prouve que Ln est l'entier le plus proche de an.

Exercice 10
preuve de 1.1)
si p=0, n doit être non nul et dans ce cas la relation demandée est vraie, car pgcd(Fn,F0)=Fn=pgcd(Fn,Fn+0).
On suppose maintenant que p est non nul et on utilise la relation 10 de P7 :
pour tous les entiers naturels n et p (p non nul), Fn+p=Fn+1Fp+FnFp-1
Soit d un entier non nul quelconque

si d divise Fn et Fp, il divise alors Fn et Fn+p ;
réciproquement, si d divise Fn et Fn+p, alors il divise Fn et aussi Fn+1Fp ; mais d est obligatoirement 1er avec Fn+1 (sinon d et Fn+1 auraient un diviseur commun autre que -1 ou 1, et comme d divise Fn, ce diviseur serait diviseur commun à Fn et Fn+1 et Fn et Fn+1 ne seraient pas 1er entre eux, ce qui est faux d'après la question 3 de l'exercice 1) : le théorème de Gauss dit alors que d divise Fp.
Donc les diviseurs de Fn et Fn+p sont les mêmes que ceux de Fn et Fn+p : et ainsi pgcd(Fn,Fp)=pgcd(Fn,Fn+p).

preuve de 1.2) : pgcd(Fn,Fp)=Fpgcd(n,p).
Si n=0 ou p=0, la relation demandée est évidemment vraie, puisque, par exemple, pgcd(0,Fp)=Fp=Fpgcd(0,p).
Supposons maintenant n et p non nuls ; la division euclidienne de p par n donne p=qn+r avec 0r<n.
L'application du résultat ci-dessus (vrai pour tous les entiers naturels n et p, non nuls tous les deux), donne alors successivement :
pgcd(Fn,Fr)=pgcd(Fn,Fn+r)=pgcd(Fn,F2n+r)=...=pgcd(Fn,Fqn+r)=pgcd(Fn,Fp), c'est-à-dire

pgcd(Fp,Fn)=pgcd(Fn,Fr), avec r reste de la division de p par n, donc, en "continuant" :
pgcd(Fn,Fr)=pgcd(Fr,Fr_1), avec r_1 reste de la division de n par r, donc
pgcd(Fr,Fr_1)=pgcd(Fr_1,Fr_2), avec r_2 reste de la division de r par r_1, donc
....etc ,
jusqu'à arriver à un dernier reste r_k nul ; bien sûr, on aura remarqué que les divisions faites sont celles de l'algorithme d'Euclide pour rechercher le pgcd de n et p.
On obtient donc pgcd(Fn,Fp)=pgcd(Fr_(k-1),F0)=Fr_(k-1), puisque F0=0.
Et comme r_(k-1)=rk-1 est le dernier reste non nul dans l'algorithme d'Euclide pour le pgcd de n et p, c'est que rk-1=pgcd(n,p) et donc pgcd(Fn,Fp)=Fpgcd(n,p).

preuve de 1.3) et 1.4)
Si p (non nul) divise n, pgcd(n,p)=p et le résultat ci-dessus donne pgcd(Fn,Fp)=Fp et donc Fp divise Fn.
Si Fp divise Fn (avec p3), pgcd(Fn,Fp)=Fp, donc Fp=Fpgcd(n,p), donc, puisque p3, p=pgcd(n,p) et p divise n (Remarque : tous les termes de la suite (F) sont distincts sauf F2 et F1, ce qui explique pourquoi le résultat est faux si p=2).

preuve de 1.5) : si n est distinct de 4 et si Fn est premier (donc nécessairement n=3 ou n5), nécessairement n est aussi premier.
C'est une conséquence immédiate du résultat précédent.

Pour n=3 le résultat est évidemment vrai ; on se place mantenant dans le cas où n5 : si n n'était pas premier, n=pq, avec p et q supérieurs ou égaux à 2 et (donc) distincts de n ; Fp et Fq ne peuvent être tous les deux égaux à 1, car cela voudrait dire p=q=2 et n=4 ; supposons que Fp soit distinct de 1 ; comme il divise Fn et que par ailleurs il est distinct de Fn (car Fn=Fp exige p=n, puisque n5), donc Fn ne serait pas premier.

preuve de 1.6) sur pgcd(Ln,Lp)

Cette preuve, qui repose presque entièrement sur la relation vue en 15.6 de P8, est personnelle, ce qui explique qu'elle soit un peu "longuette".
Mais ses arguments sont simples et elle détaillée entièrement. En outre il y deux caractérisations pour différentier les trois résultats possibles.

Cf 15.6 de P8, pour tout n et tout p dans Z, Ln=Ln-pLp+(-1)p+1Ln-2p (preuve immédiate par Binet).
On en déduit tout de suite que pgcd(Ln,Lp)=pgcd(Ln-2p,Lp), puisque les diviseurs communs à Ln et Lp sont les diviseurs communs à Ln-2pet Lp.
Mais cf L-p=±Lp (voir P5.3), en changeant p en -p, on obtient
pgcd(Ln,Lp)=pgcd(Ln+2p,Lp).
Et par itération,
pour tout q dans N, pgcd(Ln,Lp)=pgcd(Ln-2qp,Lp)=pgcd(Ln+2qp,Lp),
et ainsi pour tout q dans Z, pgcd(Ln,Lp)=pgcd(Ln+2qp,Lp).
Enfin, en changeant n en -n, on obtient pour tout q dans Z, pgcd(Ln,Lp)=pgcd(L-n+2qp,Lp).

On peut résumer ces deux dernières relations par l'unique relation :
si n'≡±n (2p) alors pgcd(Ln,Lp)=pgcd(Ln',Lp).

Applications :

1) pgcd(L120,L56)=pgcd(L56,L8)=pgcd(L8,L8)=L8=Lpgcd(120,56)
(puisque 120-2×56=8 ; 56-3×(2×8)=8)

2) pgcd(Ln,Ln-1)=pgcd(Ln-1,Ln-2(n-1))=pgcd(Ln-1,L-n+2)=pgcd(Ln-1,Ln-2)
Et par itérations, pgcd(Ln,Ln-1)=pgcd(L1,L0)=pgcd(1,2)=1=L1=Lpgcd(n,n-1)

3) pgcd(L12,L8)=pgcd(L-4,L8)=pgcd(L8,L4)=pgcd(L4,L0)=pgcd(7,2)=1≠Lpgcd(12,8)=L4

4) pgcd(L48,L12)=pgcd(L12,L0)=pgcd(L12,2)=2, car 3 divisant 12, L12 est pair (voir question 6)c de l'exercice 1) et donc pgcd(L48,L12)=2≠Lpgcd(48,12)=L4

on constate que si pgcd(Ln,Lp) peut être égal à Lpgcd(n,p), cela n'est pas toujours vrai, contrairement au cas de la suite (F).

Le lemme suivant va permettre d'obtenir le résultat général sur pgcd(Ln,Lp).
Lemme(n,p), avec n≥p≥0 et n≠0.

On est maintenant en mesure de déterminer pgcd(Ln,Lp) avec n≥p≥0 et n≠0.

Donc, au cours d'applications successives du lemme, si le cas 1 et le cas 2 ne se réalisent jamais, c'est qu'il va exister une suite infinie d'entiers naturels strictement décroisante : p>n1>p1...≥0, donc qu'il va exister une infinité d'entiers naturels dans {0;1;2;...;p-1}, ce qui est impossible.
Obligatoirement, au bout d'un nombre fini d'applications successives du lemme, le cas 1 ou le cas 2 va se réaliser.
Ainsi, vu que lors du passage par le cas 3 du lemme, il y a conservation de pgcd(Ln,Lp) et de pgcd(n,p) et que le couple d'indices (n,p) est remplacé par un couple d'indices constitué aussi de deux entiers naturels et dont le plus grand n'est pas nul, c'est que Le problème est maintenant d'essayer de prévoir le type d'arrivée en fonction de n et p, ce qui en fait va être très simple à établir.
Si p est nul, on arrive forcément "tout de suite" au cas 1.
Sinon, n et p étant alors non nuls, on peut alors écrire n et p sous la forme (unique) n=2an' et p=2bp' avec a, b, n', m' entiers naturels, n' et m' impairs.

Finalement, au cours d'applications successives du lemme,
on arrive au cas 2 <=> a=b, et donc
on arrive au cas 1 <=> a≠b
Avant de conclure, remarquons que, en notant d=pgcd(n,p)

a=b <=> n/d et p/d sont impairs

en effet
si a=b, d=2apgcd(n',p') avec n' et p' impairs et d'=pgcd(n',p') est impair : donc n/d=n'/d' est impair et p/d=p'/d' est impair
si n/d et p/d sont impairs, la valuation en 2 de n et p est celle de d, donc la même, soit a=b
D'où la conclusion pour déterminer pgcd(Ln,Lp), n et p étant deux entiers naturels :
si n≠0, on note n=2an' avec a≥0, n' impair
si p≠0, on note p=2bp' avec b≥0, p' impair
si n et p pas tous les deux nuls, on note d=pgcd(n,p)
Conséquences :
1) pour n≥1 et p≥1,
Ln et Lp sont premiers entre eux <=> [n/d ou p/d est pair et 3 ne divise pas d] ou [n et p sont premiers entre eux et impairs]

Rappel : Ld=1 <=> d=1.
2) On retrouve (voir exercice 1, question 2), que pour tout entier naturel n, Ln et Ln+1 sont premiers entre eux En effet, c'est trivial si n=0 et pour n≥1, puisque d=pgcd(n,n+1)=1 et n/d=n ou (n+1)/d=n+1 est pair et que 3 ne divise pas d=1, c'est que pgcd(Ln,Ln+1)=1. 3) On retrouve aussi (voir exercice 2, question 2) évidemment le fait que si k et p sont des entiers naturels, avec k impair et p≥0, Lp divise Lkp : si p=0 c'est trivial, si p≥1 c'est parceque pgcd(kp,p)=p et kp/p, p/p sont impairs donc pgcd(Lkp,Lp)=Lp.
4) En fait on a la réciproque :
pour n≥1 et p≥2, Lp divise Ln <=> p divise n et n/p impair
et donc si k et p sont des entiers naturels avec k pair et p≥2 alors Lp ne divise pas Lkp
. En effet,
si p divise n et n/p impair, c'est que n=kp avec k impair et voir la conséquence ci-dessus.

si Lp divise Ln, alors pgcd(Ln,Lp)=Lp.
Comme p≥2, Lp≥3 et donc pgcd(Ln,Lp)≠1 et 2, donc on est dans le cas où n/d et p/d sont impairs et pgcd(Ln,Lp)=Ld, donc d=p et ainsi on a bien p divise n avec n/p impair


Remarque : ces deux résultats se généralisent au cas où les indices sont dans Z, puisque L-n et Ln sont égaux ou opposés.

preuve de 1.7) sur le pgcd(Ln,Fp)
De la relation 6 de P3, Ln+p=Fp-1Ln+FpLn+1 (valable pour tout n et tout p dans Z), on déduit que
pgcd(Ln,Fp)=pgcd(Ln,Ln+p), pour tout n et tout p dans Z.

En effet,
si d divise Ln et Fp, alors d divise Ln et Ln+p
réciproquement, si d divise Ln et Ln+p, alors d divise Ln et FpLn+1.
Mais d est premier avec Ln+1, sinon d et Ln+1 ont un diviseur premier commun, lequel va aussi diviser Ln, puisque d divise Ln, et donc Ln et Ln+1 ne seraient pas premiers entre eux, ce qui est faux (voir conséquence du 1.6 ci-dessus).
Donc d divise aussi Fp.
Ainsi, les diviseurs communs à Ln et Fp sont les diviseurs communs à Ln et Ln+p.
Il suffit d'appliquer alors 1.6, en remarquant que d=pgcd(n,p)=pgcd(n,n+p).
Pour n≥1, p≥1,
soit n/d et (n+p)/d sont impairs et pgcd(Ln,Lp)=Ld
soit n/d ou (n+p)/d est pair et pgcd(Ln,Lp)=1 si 3 ne divise pas ou pgcd(Ln,Lp)=2 si 3 divise d
On peut alors remarquer que n/d et (n+p)/d impairs <=> p/d pair en effet
si n/d et (n+p)/d sont impairs, leur différence, p/d est paire
si p/d est pair, forcément n/d est impair sinon p/d et n/d seraient pairs, donc non premiers entre eux, ce qui est contraire au fait que d=pgcd(n,p) ; et n/d étant impair , (n+p)/d est aussi impair.

Si on introduit là aussi les valuations en 2 de n et p :
n=2an' et p=2bp', avec a, b, n', p' entiers naturels, n' et p' impairs, alors
p/d pair <=> b>a

en effet
si p/d est pair alors b>val2(d) ; mais on a vu que p/d pair implique n/d impair, donc a=val2(d), et ainsi b>a
si b>a, forcément, val2(d)=a, d'où val2(p)=b>a=val2(d), donc p/d est pair
D'où la conclusion pour déterminer pgcd(Ln,Fp), n et p étant deux entiers naturels (les cas où un des indices est nul sont immédiats) :
si n≠0, on note n=2an' avec a≥0, n' impair
si p≠0, on note p=2bp' avec b≥0, p' impair
si n et p pas tous les deux nuls, on note d=pgcd(n,p) Cas particulier n=p
si n=p=0 le pgcd est L0=2
si n=p≥1, d=n et p/d=1 est impair, donc le pgcd est 1 si 3 ne divise pas n, et 2 si 3 divise n.
Ceci se résume en :
si n≥0
Bien entendu, une preuve directe (et rapide) dans ce cas particulier est possible.
Par exemple on peut utiliser la relation 4=(-1)n((Ln)2-5(Fn)2) (voir 7 de P8), qui prouve que si d (>0) divise Fn et Ln, alors d2 divise 4 donc d=1 ou 2, et donc le pgcd de Fn et Ln est 1 ou 2.
Ce sera 2 si et seulement si ces deux nombres sont divisibles par 2, soit si et seulement si 3 divise n (voir Q6)c de l'exercice 1).
Variantes :

preuve de 1.8) pour k et n ≥1, pgcd(Fkn/Fn, Fn) est égal à pgcd(k,Fn) si k impair ou k pair et 3 divise n et égal à pgcd(k/2,Fn) si k pair et 3 ne divise pas n.
Posons dk=pgcd(Fkn/Fn, Fn).
Il est facile de vérifier le résultat pour les premières valeurs de k :

Pour traiter le cas général on va utiliser le 2) de P15 : Deux exemples (k=2, k=3 ont été vus au début de cette preuve)

preuve de 2) L'application de l'algorithme d'Euclide Fn+2 et Fn+1 est immédiate :

Fn+2=Fn+1+Fn (il s'agit bien de la division euclidienne de Fn+2 par Fn+1 : le quotient est 1, le reste Fn)
Fn+1=Fn+Fn-1
.
.
.
F4=F3+F2
F3=2F2+0 (là, le quotient est 2, et le reste est 0)
Le dernier reste non nul est F2=1, donc le pgcd est 1 (ce n'est pas une surprise...) et cela a demandé exactement n itérations.
On remarquera aussi, que la suite des n quotients est (1,1,1,...,1,2) : il y n-1 fois le quotient 1.
Remarque :
on peut vérifier que c'est bien vrai pour n=1, la seule division à faire étant celle de F3 par F2,F3=2F2, qui donne tout de suite un reste nul, et le pgcd est F2=1.
Par contre si n=0, le résultat n'est plus vrai, car théoriquement il faut faire la division de F2 par F1.

preuve de 3) On écrit l'algorithme d'Euclide avec n itérations :

a=bq1+r2, 0r2<b
b=r2q2+r3, 0r3<r2
r2=r3q3+r4, 0r3<r4
.
.
.
rn-2=rn-1qn-1+rn, 0rn<rn-1
rn-1=rnqn.
Si n=1, il y a juste la division a=bq1 ; en fait pour ce cas comme b1, c'est que bF2, et comme a2, c'est que aF3.
On va généraliser cela dans le cas n2.
Les quotients q1, q2, ..., qn-1 sont tous 1, mais qn2, car qn=1 entraîne rn=rn-1, ce qui est faux.
On peut alors faire les minorations successives suivantes : rn1=F2, puisque rn n'est pas nul
rn-12rn2F2=F3
rn-2rn-1+rnF3+F2=F4
rn-3rn-2+rn-1F4+F3=F5
.
.
.
r2r3+r4Fn-1+Fn-2=Fn
br2+r3Fn+Fn-1=Fn+1
ab+r2Fn+1+Fn=Fn+2
Et donc, pour n2, aFn+2 et bFn+1, inégalités encore vraies pour n=1 (cf ci-dessus).
Or on a vu , c'est le résultat précédent, que l'algorithme d'Euclide pour la recherche du pgcd de Fn+1 et Fn+2 (n entier naturel non nul) se fait exactement en n itrations : donc le plus petit a cherché est Fn+2, le plus petit b correspondant étant Fn+1.

preuve de 4) A partir de aFn+2 et bFn+1 (cf la démonstration ci-dessus) et du fait que pour tout n2, Fnan-2 (voir question 6 de l'exercice 1), on obtient nlna/lna et nlnb/lna+1.

Exercice 11
Parmi F0, F1, F2, F3, F4, les seuls qui soient des puissances entières de 3 sont évidemment F1=1, F2=1, et F4=3.
Montrons que si n5, Fn ne peut être une puissance entière de 3.
Si c'était le cas, puisque Fn5, on aurait Fn=3k avec k2, et donc 9 diviserait Fn ; comme 9 est la plus grande puissance de 3 qui divise 144=F12, c'est que l'on aurait pgcd(Fn,F12)=9, soit, cf le 1) de P9, Fpgcd(n,12)=9 et donc 9 serait un terme de la suite (F), ce qui esf faux.

Exercice 12
1) Preuve du théorème de Hogatt
Les entiers 1 et 2 sont bien sommes de termes distincts de la suite (F), F0 et F1 étant exclus, puisque 1=F2 et 2=F3.
On va montrer par récurrence que tout entier k tel que 1kFn, avec n3, est somme de termes distincts de la suite (F), F0 et F1 étant exclus (cet aspect sera toujours sous-entendu ci-dessous).

Donc pour tout n3, tout entier k tel que 1kFn, est somme de termes distincts de la suite (F), F0 et F1 étant exclus.
Comme limn->+Fn=+, le théorème de Hogatt est bien prouvé.

2) Preuve du théorème de Zeckendorf.
On peut songer utiliser le théorème de Hogatt et regrouper les termes consécutifs. Par exemple, F11+F12+F13=F11+F14 ; mais je touve qu'ensuite cela pose un problème pour justifier que l'on va arriver à ne plus avoir de termes consécutifs, mais je me trompe peut être.

Je vais d'abord montrer l'existence d'une Z_somme en justifiant la méthode d'obtention indiquée dans l'énoncé.
Soit e un entier naturel non nul.

Le processus va nécessairement s'arrêter car à chaque étape, l'expression entière e-F(n1)-F(n2)-...-F(nk), qui est 0, diminue strictement, donc elle finira par atteindre la valeur 0.

Reste à prouver l'unicité (à l'ordre près des termes) d'une telle somme.
Pour cela démontrons le résultat intermédiaire suivant :

Soit S une somme de termes distincts, deux à deux non consécutifs, de la suite (F), F0 et F1 exclus ; en notant Fj le plus grand de ces termes, alors on a S<Fj+1.
preuve :
On fait une récurrence sur j, qui est 2.
Prouvons maintenant que tout entier naturel non nul admet une unique (à l'ordre près) Z_somme.
Cela revient à montrer que si S et T sont deux sommes de termes distincts et non consécutifs de (F), F0 et F1 étant exclus, et si S=T alors S et T sont constituées des mêmes termes : Aprés simplification des termes communs, l'égalité S=T, devient S'=T', S' et T' étant encore deux sommes de termes distincts et non consécutifs de (F), F0 et F1 étant exclus, mais en plus, S' et T' n'ont aucun terme commun. Supposons S'0 ; donc T'0. Soit Fs le plus grand terme de S' et Ft le plus grand terme de T' : Fs et Ft étant distincts (cf la simplification faite ci-dessus), on peut supposer, quitte à échanger S et T, que Fs<Ft, soit, puisque la suite (F) est strictement croissante à partir du rang 2, Fs+1Ft.
Mais le résultat intermédiaire ci-dessus donne S'<Fs+1, donc S'<Ft ; or S'=T'Ft (puisque c'est un des termes constituant T') et donc on arrive à une contradiction.
Donc, nécessairement S'=T'=0.
Ceci prouve que les sommes S et T sont constituées des mêmes termes.
preuve du 3)
fe'=Fi avec i2 si i=2, fe'=12K, puisque K1
si i=3, fe'=22K, puisque K1
On se place maintenant dans le cas où i4.
Raisonnons par l'absurde, c'est-à-dire on suppose que fe'>2K.
Alors, dans ce cas, la Z_d de K ne peut contenir que des termes de (F) qui sont Fi-2 sinon, cette Z_d contiendrait au moins un terme de (F) qui soit >Fi-2, soit au moins un terme qui soit Fi-1, et donc on aurait KFi-1, soit 2K2Fi-1, donc fe'=Fi>2Fi-1, ce qui est impossible cf P2 et i4. La Z_d de K ne contenant que des termes de (F) qui sont Fi-2, la juxtaposition de la Z_d de e' et de la Z_d de K est la Z_d (à l'ordre près bien sûr) de e'+K=e, et dont le plus petit terme est le plus petit terme de la Z_d de K.
Donc fe est le plus petit terme de la Z_d de K, soit feK, ce qui est en contradiction avec l'hypothèse K<fe.
Ainsi, on ne peut avoir fe'>2K, c'est donc que fe'2K.

Exercice 13

1) On peut utiliser les 1) 2) 3) 4) de P3 si on se contente de vérifier les différentes décompositions ; mais voici une preuve par construction.

2Fn=Fn+Fn-1+Fn-2=Fn-2+Fn+1
3Fn=2Fn+Fn=Fn-2+Fn+Fn+1=Fn-2+Fn+2
4Fn=3Fn+Fn=Fn-2+Fn+Fn+2 (en ajoutant Fn au résultat précédent, sans autre modification, il reste une Z_somme)
5Fn=3Fn+2Fn=2Fn-2+Fn+3=Fn-4+Fn-1+Fn+3
6Fn=5Fn+Fn=Fn-4+Fn+1+Fn+3
7Fn=6Fn+Fn=Fn-4+Fn+2+Fn+3=Fn-4+Fn+4
8Fn=7Fn+Fn=Fn-4+Fn+Fn+4
9Fn=8Fn+Fn=Fn-4+2Fn+Fn+4=Fn-4+Fn-2+Fn+1+Fn+4
10Fn=7Fn+3Fn=Fn-4+Fn-2+Fn+2+Fn+4
11Fn=10Fn+Fn=Fn-4+Fn-2+Fn+Fn+2+Fn+4
12Fn=2(6Fn)=2Fn-4+2Fn+1+2Fn+3=(Fn-6+Fn-3)+(Fn-1+Fn+2)+(Fn+1+Fn+4)=Fn-6+Fn-3+Fn-1+Fn+5, puisque Fn+1+Fn+2+Fn+4=Fn+3+Fn+4=Fn+5
13Fn=12Fn+Fn=Fn-6+Fn-3+Fn+1+Fn+5
14Fn=13Fn+Fn=Fn-6+Fn-3+Fn+2+Fn+5
15Fn=14Fn+Fn=Fn-6+Fn-3+Fn+Fn+2+Fn+5

2) En utilisant les formules ci-dessus,

Exercice 14
(Fn)2+FnFn+1-(Fn+1)2= Fn(Fn+Fn+1)-(Fn+1)2= FnFn+2-(Fn+1)2=-(-1)n+1=(-1)n, d'après la relation 2) de P8.

Exercice 15

1)

2)

Exercice 16

1) La première relation est tout simplement la conséquence de k(4)=6, cf le tableau d'exemples au début de P13.
Mais le raisonnement fait pour (F) s'applique aussi à (L), cf on a le même relation de récurrence : Ln+2=Ln+1+Ln et en notant L'n le reste de la division de Ln par 4, on a encore L'n+2≡L'n+1+L'n (4),
d'où L'0=2, L'1=1, L'2=3, L'3=0, L'4=3, L'5=3, L'6=2, L'7=1.
Puisque (L'0,L'1)=(L'6,L'7) et que L'n+2≡L'n+1+L'n (4), c'est que la suite L'n est aussi de période 6, cad k(4)=6, ce qui donne la deuxième relation.

A partir du tableau donné dans l'énoncé, on vérifie immédiatement que Fn2≡Ln2 (4).
Ceci se retrouve à partir de la relation 5Fn2+4(-1)n=Ln2 (c'est la 7 de P8), puisque 5≡1 (4) et 4≡0 (4).

2) On raisonne par récurrence :

3) Pour montrer k(2e)=3×2e-1, on fait aussi une récurrence :

Remarque :
En faisant, e=2, on obtient k(4)=6, ce qui a bien été trouvé directement lors de la question 1.

Exercice 17

1) Une récurrence immédiate montre que Un est de degré n, le coefficient de Xn étant 2n.

De même, le point suivant se montre par récurrence (bien sûr sin(q) est supposé non nul) :

n étant cette fois dans N*, on en déduit que si sin((n+1)q)=0 (et q n'étant pas un multiple de p), alors Un(cos(q))=0 et donc pour tout k dans Z (exceptés les multiples de n+1) on a Un(cos(kp/(n+1)))=0.
En particulier pour k=1,2,..,n (qui ne sont pas des multiples de n+1) on obtient n racines de Un :
cos(p/(n+1)), cos(2p/(n+1)),..., cos(np/(n+1)), racines qui sont distinctes (puisque p/(n+1), 2p/(n+1), ..., np/(n+1) sont n nombres distincts dans [0;p]).
Un étant de degré n, ce sont donc ses n racines, et compte-tenu que le coefficient de Xn est 2 on obtient la factorisation souhaitée :
Un(X)=2nPk=1 n(X-cos(kp/(n+1))

2) On cherche une constante q telle que pour tout entier naturel n, non nul, on ait qn+1Un+1(-i/2)=qnUn(-i/2)+qn-1Un-1(-i/2), alors que l'on a Un+1(-i/2)=-iUn(-i/2)-Un-1(-i/2).
En multipliant les deux membres de cette égalité par -in-1, on obtient -in-1Un+1(-i/2)=inUn(-i/2)+in-1Un-1(-i/2), et coup de chance (?), on constate que -in-1=i2in-1=in+1, et donc q=i convient, c'est-à-dire la suite Wn=inUn(-i/2) est une suite de Fibonacci (puisque Wn+1=Wn+Wn-1).

3) Comme W0=1=F1, W1=i×U1(-i/2)=i×2(-i/2)=1=F2, c'est que pour tout entier naturel n, on a Wn=Fn+1 (voir P3), soit, pour n1, Fn+1=inUn(-i/2)=in×2n×Pk=1 n(-i/2-cos(kp/(n+1)) ,
d'où pour n2, Fn=(-i)n-1Pk=1 n-1(2cos(kp/n)+i).
Il suffit alors de passer au module-carré pour obtenir que pour tout n2 (Fn)2=Pk=1 n-1(1+4cos2(kp/n)).

3) La formule cos2(q)=(1+cos(2q))/2 donne tout de suite, pour tout n2, (Fn)2=Pk=1 n-1(3+2cos(2kp/n))
En posant qk=2kp/n, on a cos(qk)=cos(qn-k), d'où


Mais si n est impair E((n-1)/2)=(n-1)/2 et si n pair E((n-1)/2)=E(n/2-1/2)=n/2-1, et donc
pour n3, Fn=Pk=1 E((n-1)/2)(3+2cos(2kp/n))=Pk=1 E((n-1)/2)(1+4cos2(kp/n))

4) On va utiliser la relation (voir P8) Ln=F2n/Fn (n est 2, donc Fn0).
(Ln)2=(Pk=1 2n-1(3+2cos(2kp/(2n))))/(Pk=1 n-1(3+2cos(2kp/n))) : les facteurs correspondants à k pair du numérateur sont exactement les facteurs du dénominateur et donc
(Ln)2 est le produit des (3+2cos(kp/n)) pour k=1,3,..,2n-1, soit (Ln)2=Pk=0 n-1(3+2cos((2k+1)p/n)).
Par exemple, cela donne

(L3)2=(3+2cos(p/3))(3+2cos(3p/3))(3+2cos(5p/3))=4×1×4, et on retrouve bien L3=4.

Puisque E((2n-1)/2)=E(n-1/2)=n-1, Ln=(Pk=1 n-1(3+2cos(2kp/(2n))))/(Pk=1 E((n-1)/2)(3+2cos(2kp/n))) : là encore, les facteurs correspondants à k pair du numérateur sont exactement les facteurs du dénominateur, car on a aussi 2kn-1 kE((n-1)/2), et donc
Ln est le produit des (3+2cos(kp/n)) pour k impair de 1 à n-1 ; mais 12k+1n-1 0kn/2-1 0kE(n/2-1), d'où
Ln=Pk=0 E(n/2-1)(3+2cos((2k+1)p/n)).
Par exemple, cela donne

L4=(3+2cos(p/4))(3+2cos(3p/4))=(3+2cos(p/4))(3-2cos(p/4))=9-2=7.

L6=(3+2cos(p/6))(3+2cos(3p/6))(3+2cos(5p/6))=(3+2cos(p/6))×3×(3-2cos(p/6))=3×(9-3)=18.

Exercice 18

1) On a évidemment pk+1(q)=3pk(q)+2cos((k+1)q)pk(q), et (une vérification n'est jamais inutile), pk(0)=5k, pk(p)=5E(k/2) (car pk(p) est un produit de k facteurs valant 1 ou 5, ceux valant 5 correspondants à 3+2cos(jp) avec j pair et dans {1;2;...;k}).
On trouve, successivement :

2) Notons A=Pk=1 E((5-1)/2)(3+2cos(2kp/5) et vérifions que l'on a bien F5=A

A=p2(2p/5)=9+8cos(2p/5)+6cos(4p/5)+2cos(6p/5)
Les racines 5ièmes de 1 sont 1, ei2p/5, ei4p/5, ei6p/5 (conjuguée de ei4p/5), ei8p/5 (conjuguée de ei2p/5) et leur somme est 0, donc Comme F5=5, on a bien F5=A.
Notons A=Pk=1 E((7-1)/2)(3+2cos(2kp/7) et vérifions que l'on a bien F7=A A=p3(2p/7)=29+30cos(2p/7)+26cos(4p/7)+24cos(6p/7)+8cos(8p/7)+6cos(10p/7)+2cos(12p/7)
Les racines 7ièmes de 1 sont 1, ei2p/7, ei4p/7, ei6p/7, ei8p/7 (conjuguée de ei6p/7) ei10p/7 (conjuguée de ei4p/7), ei12p/7 (conjuguée de ei2p/7), et leur somme est 0, donc Comme F7=13, on a bien F7=A
Notons A=Pk=1 E((9-1)/2)(3+2cos(2kp/9) et vérifions que l'on a bien F9=A A=p4(2p/9)=95+120cos(2p/9)+106cos(4p/9)+102cos(6p/9)+82cos(8p/9)+48cos(10p/9)
+32cos(12p/9)+24cos(14p/9)+8cos(16p/9)+6cos(18p/9)+2cos(20p/9)
Les racines 9ièmes de 1 sont 1, ei2p/9, ei4p/9, ei6p/9, ei8p/9, ei10p/9 (conjuguée de ei8p/9), ei12p/9 (conjuguée de ei6p/9), ei14p/9 (conjuguée de ei4p/9), ei16p/9 (conjuguée de ei2p/9), et leur somme est 0, donc Comme F9=34, on a bien F9=A

Exercice 19

En posant r=51/2, l'application de la formule de Lucas-Fibonacci-Moivre ( voir P5.2),
((Ln+rFn)/2)k=(Lkn+rFkn)/2 donne tout de suite, puisque (voir preuve de P5.2) a+br=a'+b'r avec a, b, a', b' rationnels entraîne a=a' et b=b'

Examinons d'abord le cas de Lkn Puisque 5jFn2j=(5Fn2)j=(Ln2+4(-1)n+1)j (cf le 7 de P8), on voit tout de suite que Lkn=Rk,n(Ln), avec Rk,n polynôme :
Rk,n=(1/2k-1)(S02jkCk2j Xk-2j(X2+4(-1)n+1)j)

Puisque LmLn=Lm+n+(-1)nLm-n (voir le 15.6 de P8), on obtient tout de suite (on fait m=kn) la relation de récurrence Rk+1,n(X)=XRk,n(X)+(-1)n+1Rk-1,n(X)
On a évidemment R1,n(X)=X et puisque, cf la relation 7 de P8, L2n=(Ln)2+2(-1)n+1, c'est que R2,n(X)=X2+2(-1)n+1, ce qui permet de calculer facilement de proche en proche les suivants.
On va maintenant prouver, par récurrence, que la forme explicite annoncée de Rk,n est bien :

Rk,n(X)=∑r=0E(k/2)(-1)r(n+1)(Ck-rr +Ck-r-1r-1 )Xk-2r.
C'est grâce à un papier de Stanley Rabinowitz que j'ai trouvé Ck-rr +Ck-r-1r-1, à vrai dire sous la forme (k/(k-r))Ck-rr (voir énoncé), mais il semble que S.R n'ait pas vu qu'il existait aussi de telles formules pour les polynômes reliant Fkn et Fn.
Cette formule est évidemment vraie pour k=1 et k=2.
Supposons là vraie pour 1,2,...,k avec k≥2.
La relation de récurrence ci-dessus donne
Rk+1,n(X)=X[∑r=0E(k/2)(-1)r(n+1)(Ck-rr +Ck-r-1r-1)Xk-2r]
+(-1)n+1[∑r'=0E((k-1)/2)(-1)r'(n+1)(Ck-1-r'r'+Ck-1-r'-1r'-1 )Xk-1-2r']
En posant r'=r-1 dans le 2ième ∑ on obtient
Rk+1,n(X)=∑r=0E(k/2)(-1)r(n+1)(Ck-rr +Ck-r-1r-1 )Xk+1-2r
+∑r=11+E((k-1)/2)(-1)r(n+1)(Ck-rr-1 +Ck-r-1r-2 )Xk+1-2r.
On envisage deux cas :

Passons maintenant au cas de Fkn.
Cette fois le problème est que l'exposant dans la formule (voir ci-dessus au début)
Fkn=(1/2k-1)(S02j+1kCk2j+1 5jFn2j+1Lnk-2j-1)
de Ln est k-2j+1 qui n'est pas forcément pair, ce qui explique qu'on ne peut pas toujours faire disparaître Ln via la formule Ln2=(5Fn2+4(-1)n).
D'où les deux cas :


Bien entendu, le calcul des premiers polynômes Qk,n(X) est plus facile à partir des relations de récurrence suivantes.
Cf le 15.7 de P8, on a FmLn=Fm+n+(-1)nFm-n, et en faisant m=kn on obtient F(k+1)n=FknLn+(-1)n+1F(k-1)n.
Et compte-tenu que Fkn=Qk,n(Fn) si k est impair, et Fkn=LnQk,n(Fn) si k est pair, et que Ln2=(5Fn2+4(-1)n), on obtient Comme Q1,n(X)=Q2,n(X)=X, on peut en déduire facilement les suivants.
Reste à déteterminer les formes explicites de Q2k+1,n(X) et Q2k,n(X).

Commencons par le plus facile, cad par prouver que Q2k+1,n(X) n'est autre que (1/√5)R2k+1,n-1(√5X).
On va le faire en utilisant les formules donnant ces polynômes en fonction de 5X2+4(-1)n pour l'un et X2+4(-1)n+1 pour l'autre.
Q2k+1,n(X)=(1/22k)(S0jkC2k+12j+1 5jX2j+1(5X2+4(-1)n)k-j)
R2k+1,n(X)=(1/22k)(S02j2k+1C2k+12j X2k+1-2j(X2+4(-1)n+1)j)
Comme 2j≤2k+1 <=> j≤k et en posant j=k-j',
R2k+1,n(X)=(1/22k)(S0j'kC2k+12k-2j' X2j'+1(X2+4(-1)n+1)k-j').
Mais C2k+12k-2j' =C2k+12k+1-(2k-2j') =C2k+12j+1' et ainsi
R2k+1,n(X)=(1/22k)(S0jkC2k+12j+1 X2j+1(X2+4(-1)n+1)k-j), ce qui donne bien
R2k+1,n-1(√5X)=√5Q2k+1,n(X), égalité qui donne tout de suite la forme explicite de Q2k+1,n(X), celle de Rk,n(X) ayant été vue plus haut :
Q2k+1,n(X)=(1/√5)∑r=0E((2k+1)/2)(C2k+1-rr +C2k-rr-1 )(-1)rn(√5X)2k+1-2r,
et en remarquant que E((2k+1)/2)=k,
Q2k+1,n(X)=∑r=0k(C2k+1-rr +C2k-rr-1)(-1)rn5k-rX2k+1-2r.

Passons maintenant à la forme explicite de Q2k,(X).
On a vu plus haut que pour tout k≥1, (5X2+4(-1)n)Q2k,n(X)=Q2k+1,n(X)+(-1)nQ2k-1,n(X).
Le membre de droite étant impair (somme de deux polynômes impairs) de degré 2k+1, celui de Q2k+1,n, puisque Q2k-1,n est de degré 2k-1, c'est que Q2k,n(X) est impair de degré 2k+1-2=2k-1.
On a donc Q2k,n(X)=∑r=0k-1(-1)rn5k-r-1ak,rX2k-1-2r, les coefficients ak,r étant à déterminer (il est évident qu'ils sont entiers, vu les deux relations de récurrence ci-dessus, et vu que Q1,n(X)=Q2,n(X)=X).
De la forme explicite de Q2k+1,n(X) vue ci-dessus, on déduit que
d=Q2k+1,n(X)+(-1)nQ2k-1,n(X)=∑r=0kθk,r(-1)rn5k-rX2k+1-2r+(-1)nr=0kθk-1,r(-1)rn5k-1-rX2k-1-2r
avec θk,r=C2k+1-rr +C2k-rr-1.
Dans le premier ∑ on sort le terme correspondant à r=0 et dans le ∑r=1k restant on change r en r+1, d'où
d=θk,05kX2k+1+
r=0k-1θk,r+1(-1)(r+1)n5k-r-1X2k-1-2r+(-1)nr=0kθk-1,r(-1)rn5k-1-rX2k-1-2r
=5kX2k+1+∑r=0k-1βk,r(-1)(r+1)n5k-r-1X2k-1-2r,
avec, pour 0≤r≤k-1, βk,rk,r+1k-1,r=C2k-rr+1 +2C2k-r-1r +C2k-r-2r-1.
Et en posant βk,-1=1, on obtient finalement
(5X2+4(-1)n)Q2k,n(X)=∑r=-1k-1βk,r(-1)(r+1)n5k-r-1X2k-1-2r.

Pour obtenir les coefficients ak,r intervenant dans Q2k,n il n'y a plus qu'à identifier.

Pour déterminer ces ak,r, il nous préciser βk,r=C2k-rr+1 +2C2k-r-1r +C2k-r-2r-1.
βk,0=C2k1 +2C2k-10 =2k+2
βk,1=C2k-12 +2C2k-21 +C2k-30 =(2k-1)(k-1)+2(2k-2)+1=2k2+k-2
Cf la relation Cab =(a/b)Ca-1b-1,
pour r≥1 on a
C2k-rr+1 =((2k-r)/(r+1))((2k-r-1)/r)C2k-r-2r-1
C2k-r-1r =((2k-r-1)/r)C2k-r-2r-1
et βk,r=((2k-r)(2k-r-1)/((r+1)r)+2(2k-r-1)/r+1)C2k-r-2r-1, soit
βk,r=((4k2+2k-2r-2)/((r+1)r))C2k-r-2r-1
On est maintenant en mesure de prouver par récurrence que pour k≥0, ak,r=C2k-r-1r (voir à la remarque 1 ci-dessous comment je suis arrivé à conjecturer cette formule) On a donc justifié la forme explicite de Q2k,n donnée dans l'énoncé :
Q2k,n(X)=∑r=0k-1(-1)rn5k-r-1C2k-r-1r X2k-1-2r

Remarque 1 : voilà comment je suis arrivé à conjecturer que ak,r=C2k-r-1r.
A partir de ak,0=1 et ak,r+1k,r-4ak,r, j'ai calculé les ak,r suivants :
ak,1k,0-4ak,0=2k+2-4=2(k-1)
ak,2k,1-4ak,1=2k2+k-2-4(2k-2)=2k2-7k+6=(k-2)(2k-3)
ak,3k,2-4ak,2=((4k2+2k-6)/6)(2k-4)-4(k-2)(2k-3)=(k-2)(k-3)(4k-10)/3
je ne vois toujours rien..., navré
ak,4k,3-4ak,3=((4k2+2k-8)/12)C2k-52 -4(k-2)(k-3)(4k-10)/3
ak,4=(k-3)(2k-5)[(2k2+k-4)/6-4(k-2)×2/3]=(k-3)(k-4)(2k-5)(2k-7)/6 et là je vois que c'est en fait (2k-6)(2k-8)(2k-5)(2k-7)/24=C2k-54 !

Remarque 2 :
Je ne sais si elle présente un intérêt, mais étant "tombé" dessus je conserve la relation suivante :
en remplacant X par 2/√5 dans la relation
(5X2+4(-1)n)Q2k,n(X)=∑r=-1k-1βk,r(-1)(r+1)n5k-r-1X2k-1-2r, on obtient (en supposant n impair)
r=-1k-1(-1)r+1βk,r22k-1-2r=0, soit ∑r=-1k-1(-1)-rβk,r22k-2r=0 et en multipliant par (-1)k
r=-1k-1βk,r(-4)k-r=0.
Comme βk,k-1=4k, on a aussi érire ∑r=-1k-2βk,r(-4)k-r=-4k×(-4)
et on obtient l'identité k=∑r=-1k-2βk,r(-4)k-r-2.
On peut l'obtenir aussi à partir de ak,r+1k,r-4ak,r et de ak,0=1 : on calcule les ak,i successifs en fonction des βk,j, cela jusqu'à ak,k-1=4k.

Terminons en démontrant la remarque de l'énoncé de P15, à savoir qu'il n'existe pas des réels an, bn, cn, à valeur absolue indépendantes de n, tels que pour tout entier naturel n, F2n=anFn2+bnFn+cn.

Exercice 20

Cf P15, pour k impair, Fk=Qk,n(Fn) avec Qk,n polynôme impair, de degré k, de coefficient de tête 5(k-1)/2, et le coefficient de X est k(-1)(k-1)n/2.
Par exemple,
Q3,n=5X3+3(-1)nX
Q5,n=25X5+(-1)n25X3+5X.
Donc, pour k impair, le coefficient de X dans Qk,n est, au signe près, k.
Et comme Fkn=Qk,n(Fn), si pour p≥1, kp divise Fn, c'est que forcément kp+1 divise Fkn, puisque, kp+1 divise kFn et Fns pour s≥2.
Mais k divise Fn0, donc par récurrence, on peut dire que pour tout entier p≥1, kp divise Fn0kp-1
On vérifie facilement que

ce qui donne les exemples cités dans l'énoncé.

Remarque : n0 est en fait ce qui a été noté g(k) à 1)g) de P13.

Exercice 21

Pour k donné 2, on veut trouver des nombres rationnels ai, i décrivant I un sous-ensemble fini de Z, tels que pour tout entier naturel, SiIaiFn+ik=Fkn.
Compte-tenu de la formule de Binet, cette relation s'écrit
(akn-bkn)/51/2=5-k/2SiIai(Sd=0;k(-1)dCkd (ak-dbd)n+i).
Pour cela il suffit que les trois conditions suivantes soient réunies :

D'où en posant Pk(X)=SiIaiXi (c'est une fonction rationnelle), il suffit pour répondre au problème de choisir Pk de façon à ce qu'il vérifie les trois conditions

si k=2, on peut prendre P2(X)=X-1/X, ce qui donne l'identité bien connue F2n=Fn+12-Fn-12

En effet
P2(a2)=a2-b2=51/2F2=51/2
P2(b2)=b2-a2=-51/2
P2(ab)=P(-1)=0

Remarque : ce choix de P2 n'est pas le seul possible. Il suffit de multiplier ce choix par une fraction rationnelle F telle que F(a2)=F(b2)=1, les conditions C1, C2, C3 restant manifestement vérifiées.
Par exemple si on prend F(X)=1+(X-a2)(X-b2)=1+X2-L2X+(ab)2=X2-3X+2, on obtient P2(X)=X3-3X2+X+3-2/X, ce qui donne l'identité F2n=Fn+32-3Fn+22+Fn+12+3Fn2-2Fn-12, qui est tout même plus "compliquée" que F2n=Fn+12-Fn-12.
A noter que la combinaison de ces deux relations donne que pour tout n, Fn+32-3Fn+22+3Fn2-Fn-12=0

Passons au cas k>3. On pose Uk(X)=Pd=1,k-1(X-ak-dbd). : Pk vérifie la condition C6 si les k-1 zéros de Uk sont zéros de Pk.

Preuve de P17, cad du résutat de John H.E.Cohn

Dans tout ce qui suit, un entier est (ou n'est pas) un carré signifie évidemment que c'est (ou n'est pas) le carré d'un entier.

Toutes les relations données à P17 (CO1 à CO11) sont valables pour des indices négatifs, même si cela n'a pas été explicitement démontré (utiliser P5.3).

Je commence par un lemme qui n'apparaît pas explicitement dans le papier de Cohn, mais son résultat est utilisé plusieurs fois.
Lemme :
Si k est un entier pair non divisible par 3, et si a est un entier non nul tel que pgcd (Lk,a)=1
alors Lk est impair et il n'existe pas d'entier x tel que Lk divise x2+a2.

preuve :

Cf CO5 et puisque 3 ne divise pas k, Lk est impair.

Supposons qu'il existe x dans N tel que Lk divise x2+a2.
Soit p un nombre premier divisant Lk : on a donc x2≡-a2 (p).
Comme p est forcément impair, Lk l'étant, et p ne divisant pas a (donc p ne divise pas -a2), puisque a et Lk sont premiers entre eux, on peut dire que -a2 est résidu de p.
Donc -1 aussi résidu de p, sinon, -a2×-1=a2 ne serait pas résidu de p, ce qui est évidemment faux, a2 étant un carré (non divisible par p).
Et puisque -1 est résidu de p, cf le rappel de l'énoncé, c'est que p≡1 (4) ; et comme cela est vrai pour tout p premier divisant Lk, c'est qu'on a aussi Lk≡1 (4).
Mais puisque k est pair et non divisible par 3, on peut appliquer CO7 : Lk≡3 (4), ce qui donne une contradiction.

Preuve du théorème 1 : Ln est un carré si et seulement si n=1 ou 3

cas n pair
Cf CO3, Ln=Ln/22±2
Si on avait Ln=x2 avec x dans N alors on aurait (x-Ln/2)(x+Ln/2)=±2.
Mais x-Ln/2 et x+Ln/2 ont une somme paire, donc sont de même parité ; et comme ils sont non nuls, c'est que leur valeur absolue est ≥2, donc |(x-Ln/2)(x+Ln/2)|≥4, d'où contradiction.
Donc si n est pair, Ln n'est pas un carré.

cas n impair et n≡ 1 (4)
si n=1, L1=1 est effectivement un carré

si n≠1, alors n=1+4K avec K dans Z* ; on écrit 4K sous la forme 2×3r×k avec k pair et 3 ne divise pas k (cette dernière condition impose k≠0).
En faisant m=1 et p=3rk dans CO10, on obtient que Lp divise L1+2p+(-1)pL1=Ln+1.
Mais Cf CO11, et puisque 3r est impair, Lk divise Lp, donc Lk divise Ln+1.
D'où si Ln=x2 avec x dans N, on aurait Lk qui divise x2+12, ce qui est impossible cf le lemme (l'hypothèse requise sur k est bien vérifiée ainsi que celle sur a=1 et Lk puisque 1 et Lk sont bien premiers entre eux).
Donc si n est impair avec n≡1 (4), Ln est un carré uniquement si n=1 : L1=1.
Note :
ce type de raisonnement avec utilisation du lemme va être répété cinq autres fois.

cas n impair et n≡ 3 (4)
si n=3, L3=4 est effectivement un carré

si n≠3, alors n=3+4K avec K dans Z* ; on écrit 4K sous la forme 2×3r×k avec k pair et 3 ne divise pas k (cette dernière condition impose k≠0).
En faisant m=3 et p=3rk dans CO10, on obtient que Lp divise L3+2p+(-1)pL3=Ln+4.
Mais Cf CO11, et puisque 3r est impair, Lk divise Lp, donc Lk divise Ln+4.
D'où si Ln=x2 avec x dans N, on aurait Lk qui divise x2+22, ce qui est impossible cf le lemme (l'hypothèse requise sur k est bien vérifiée ainsi que celle sur a=2 et Lk, puisque Lk étant impair, cf CO5, il est premier avec 2).
Donc si n est impair avec n≡3 (4), Ln est un carré uniquement si n=3 : L3=4.

Preuve du théorème 2 : Ln est 2 fois un carré si et seulement si n=0 ou -6 ou 6

cas n impair
Si Ln est impair, évidemment il n'est pas le double d'un carré

Supposons maintenant Ln pair.
Cf CO5, ceci équivaut à 3 divise n, cad n≡0 ou 3 ou 6 ou 9 (12).
Mais comme n est impair, cela se réduit à n≡3 ou 9 (12).
Par ailleurs, cf CO8, Lm+12≡Lm (8), ce qui entraîne que pour tout k dans Z, Lm+12k≡Lm (8).
Or n=3+12k ou n=9+12k, donc
Ln≡L3=4 (8) ou Ln≡L9=76≡4 (8) ; cad on a toujours Ln≡4 (8).
Ceci va permettre de montrer que Ln ne peut être le double d'un carré.
En effet, s'il existait x dans N tel que Ln=2x2, on aurait x2≡2 (4) ;
or, modulo 4, 02≡0, 12≡1, 22≡0 ,32≡1, cad on n'a jamais x2≡2 (4).
Donc si n est impair, Ln n'est pas le double d'un carré.

Cas n pair et n≡0 (4)
si n=0, L0=2 est le double d'un carré

si n≠0, alors n=4K avec K dans Z* ; on écrit 4K sous la forme 2×3r×k avec k pair et 3 ne divise pas k.
En faisant m=0, p=3rk dans CO10, on obtient que Lp divise L2p+(-1)pL0=Ln+2.
Mais cf CO11, et puisque 3r est impair, Lk divise Lp, donc Lk divise Ln+2, et ainsi Lk divise 2Ln+4.
D'où si Ln=2x2 avec x dans N, Lk divise (2x)2+22, ce qui est impossible cf le lemme (l'hypothèse requise sur k est bien vérifiée ainsi que celle sur a=2 et Lk, puisque Lk étant impair, cf CO5, il est premier avec 2).
Donc pour n pair, n≡0 (4), Ln=2x2 uniquement pour n=0 : L0=2

Reste à voir le cas n pair et n≡2 (4) : en fait ce cas se subdivise en deux cas n≡2 (8) et n≡6 (8).
Cas n pair et n≡6 (8)
si n=6, L6=18 est le double d'un carré

si n≠6, alors n=6+8K avec K dans Z* ; on écrit 8K sous la forme 2×3r×k avec 4 divise k et 3 ne divise pas k.
En faisant m=6, p=3rk dans CO10, on obtient que Lp divise L6+2p+(-1)pL6=Ln+18.
Mais cf CO11, et puisque 3r est impair, Lk divise Lp, donc Lk divise Ln+18, et ainsi Lk divise 2Ln+36.
D'où si Ln=2x2 avec x dans N, Lk divise (2x)2+62 : là aussi on va utiliser le lemme pour conclure.
Mais s'il est immédiat de constater que l'hypothèse requise sur k est bien vérifiée, il reste à s'assurer que a=6 et Lk sont premiers entre eux, cad que 2 et 3 ne divisent pas Lk.
Lk étant impair, cf CO5, il n'est pas divisible par 2 ; et puisque 4 divise k, 4 ne divise pas k-2, donc cf CO6, 3 ne divise pas Lk.
On peut donc appliquer le lemme : il n'existe pas un entier x tel que Lk divise (2x)2+62.
Donc pour n pair, n≡6 (8), Ln=2x2 uniquement pour n=6 : L6=18

Cas n pair et n≡2 (8).
On a alors -n≡6 (8), et comme, cf CO9, L-n=(-1)nLn, soit L-n=Ln puisque n est pair, cela entraîne
Ln=2x2 <=> L-n=2x2 et -n≡6 (8) <=> (cf cas précédent) -n=6.
Donc pour n pair, n≡2 (8), Ln=2x2 uniquement pour n=-6 : L-6=L6=18.

Preuve du théorème 3 : Fn est un carré si et seulement si n=0 ou -1 ou 1 ou 2 ou 12


Cas n impair et n≡1 (4)
si n=1, F1=1 est un carré

si n≠1, alors n=1+4K avec K dans Z* ; on écrit 4K sous la forme 2×3r×k avec 2 divise k et 3 ne divise pas k.
En faisant m=1, p=3rk dans CO10, on obtient que Lp divise F1+2p+(-1)pF1=Fn+1.
Mais cf CO11, et puisque 3r est impair, Lk divise Lp, donc Lk divise Fn+1.
D'où si Fn=x2 avec x dans N, Lk divise x2+1, ce qui est impossible cf le lemme (l'hypothèse sur k est bien vérifiée ainsi que celle sur a=1 et Lk, puisque 1 et Lk sont bien premiers entre eux).
Donc pour n impair, n≡1 (4), Fn=x2 uniquement pour n=1 : F1=1

Cas n impair et n≡3 (4)
On a alors -n≡1 (4), et comme, cf CO9, F-n=(-1)n-1Fn, soit F-n=Fn puisque n est impair, cela entraîne
Fn=x2 <=> F-n=x2 et -n≡1 (4) <=> (cf cas précédent) -n=1.
Donc pour n impair, n≡3 (4), Fn=x2 uniquement pour n=-1 : F-1=F1=1.

Le cas n pair se subdivise en deux cas, selon que 3 divise ou pas n/2.
Cas n pair et 3 divise n/2
Cf CO1, Fn=Ln/2Fn/2.
Cf CO4, pgcd(Ln/2,Fn/2)=2, donc Ln/2=2Y, Fn/2=2Z, avec Y et Z deux entiers premiers entre eux.
On considère leur décomposition en nombres premiers : Y=∏piαi, Z=∏qjβj ; tout nombre premier pi est distinct de tout nombre premier qj.
Si Fn est le carré de l'entier x, alors x2=4YZ=22∏piαi ∏qjβj et nécessairement tout αi est pair ainsi que tout βi, cad Y et Z sont des carrés.
Donc, nécessairement, Ln/2 est le double d'un carré, ce qui équivaut, cf le théorème 2, à n/2=0 ou n/2=±6 ; ces deux possibilités sont bien divisible par 3, donc soit n=0 ou n=-12 ou n=12.
Réciproquement, F0=0 est bien un carré, F12=144 aussi, mais pas F-12=-144.
Donc pour n pair et 3 divise n/2, Fn=x2 uniquement pour n=0 ou n=12 : F0=0, F12=144

Cas n pair et 3 ne divise pas n/2
Cf CO1, Fn=Ln/2Fn/2.
Cf CO4, pgcd(Ln/2,Fn/2)=1, donc Ln/2 et Fn/2 sont deux entiers premiers entre eux.
On considère leur décomposition en nombres premiers : Ln/2=∏piαi, Fn/2=∏qjβj ; tout nombre premier pi est distinct de tout nombre premier qj.
Si Fn est le carré de l'entier x, alors x2=∏piαi ∏qjβj et nécessairement tout αi est pair ainsi que tout βi.
Donc, nécessairement, Ln/2 et Fn/2 sont des carrés, ce qui équivaut pour Ln/2, cf le théorème 1, à n/2=1 ou n/2=3, soit, puisque 3 ne doit pas diviser n/2, n=2.
Réciproquement, F2=1 est bien un carré.
Donc pour n pair et 3 ne divise pas n/2, Fn=x2 uniquement pour n=2 : F2=1

Preuve du théorème 4 : Fn est 2 fois un carré si et seulement si n=0 ou -3 ou 3 ou 6

Cas n impair et n≡3 (4)
si n=3, F3=2 est le double d'un carré

si n≠3, alors n=3+4K avec K dans Z* ; on écrit 4K sous la forme 2×3r×k avec 2 divise k et 3 ne divise pas k.
En faisant m=3, p=3rk dans CO10, on obtient que Lp divise F3+2p+(-1)pF3=Fn+2.
Mais cf CO11, et puisque 3r est impair, Lk divise Lp, donc Lk divise Fn+2, donc aussi 2Fn+22.
D'où si Fn=2x2 avec x dans N, Lk divise (2x)2+22, ce qui est impossible cf le lemme (l'hypothèse sur k est bien vérifiée ainsi que celle sur a=2 et Lk, puisque 2 et Lk sont bien premiers entre eux, Lk étant impair, cf CO5).
Donc pour n impair, n≡3 (4), Fn=2x2 uniquement pour n=3 : F3=2

Cas n impair et n≡1 (4)
On a alors -n≡3 (4), et comme, cf CO9, F-n=(-1)n-1Fn, soit F-n=Fn puisque n est impair, cela entraîne
Fn=2x2 <=> F-n=2x2 et -n≡3 (4) <=> (cf cas précédent) -n=3.
Donc pour n impair, n≡1 (4), Fn=2x2 uniquement pour n=-3 : F-3=F3=2.

Le cas n pair se subdivise en deux cas, selon que 3 divise ou pas n/2.
Cas n pair et 3 divise n/2
Cf CO1, Fn=Ln/2Fn/2.
Cf CO4, pgcd(Ln/2,Fn/2)=2, donc Ln/2=2Y, Fn/2=2Z, avec Y et Z deux entiers premiers entre eux.
On considère leur décomposition en nombres premiers : Y=∏piαi, Z=∏qjβj ; tout nombre premier pi est distinct de tout nombre premier qj.
Si Fn est le double du carré de l'entier x, alors x2=2YZ=2∏piαi ∏qjβj, et ainsi, nécessairement, un des pi ou un des qj est 2, avec un exposant impair et tous les autres pi et qj ont un exposant pair.
D'où les deux cas


Donc pour n pair et 3 divise n/2, Fn=2x2 uniquement pour n=0 et n=6 : F0=0, F6=8

Cas n pair et 3 ne divise pas divise n/2
Cf CO1, Fn=Ln/2Fn/2.
Cf CO4, pgcd(Ln/2,Fn/2)=1, donc Ln/2 et Fn/2 sont premiers entre eux.
Fn=2x2 entraîne que Ln/2=2y2 et Fn/2=z2 ou Ln/2=y2 et Fn/2=2z2.


Donc pour n pair et 3 ne divise pas n/2, Fn n'est pas le double d'un carré.