Fibonacci 2 PDF
Fibonacci 2 PDF
Fibonacci 2 PDF
http://alain.pichereau.pages.perso-orange.fr
[email protected]
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 2) Définition
3) Opérations
historique générale ; cas
sur les suites de 4) Formule de Binet
Spirale de particuliers des suites
Fibonacci
Fibonacci (F) et (L)
11) Sur
l'écriture d'un
9) Une fomule entier naturel
10) Pgcd et suites (F), 12) Equations
donnant Fn+1 en sous forme
(L) ; algorithme diophantiennes et
fonction de Fn et d'une somme de
d'Euclide Fibonacci
du nombre d'or termes de la
suite (F)
Z_somme
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 année si, commençant 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 u n-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 :
Page 3 sur 84
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 un/2, la longueur de la spirale de Fibonacci, arrêtée au nième
carré (compris) est (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).
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).
Page 4 sur 84
n -6 -5 -4 -3 -2 -1
Fn -8 5 -3 2 -1 1
Ln 18 -11 7 -4 3 -1
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
n 15 16 17 18 19 20 21 22 23 24 25
Fn 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025
Ln 1364 2207 3571 5778 9349 15127 24476 39603 64079 103682 167761
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 1 : 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!!
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.
Remarque 2 : bien entendu les suites de Fibonacci sont un cas particulier des suites récurrentes linéaires
d'ordre 2, c'est-à-dire des suites de la forme u n+2=Aun+1+Bun où A et B sont des constantes (A=B=1 pour
Fibonacci).
En fait pour ces suites on peut obtenir de nombreux résultats généralisants ceux sur les suites de Fibonacci
(u0=0, u1=1) et de Lucas (u0=2, u1=A) : voir mon étude sur ces suites : on verra notamment au 1.2) du VI
une formule sommatoire de Ln qui me semble inédite et qui n'est qu'un cas particulier des suites
un+2=Aun+1+Bun
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).
cad, si (u) est une suite de Fibonacci, k un entier naturel quelconque, la suite (v) définie par v n=un+k
pour tout entier naturel n, est de Fibonacci.
Page 5 sur 84
4) Une suite de Fibonacci multipliée par une constante est une suite de Fibonacci.
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 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.
P4->Soit (u) une suite de Fibonacci. En notant le nombre d'or ( est la racine positive de x2-x-1=0
cad =(1+5)/2=2cos(/5) et l'autre racine de cette équation est =(1-5)/2), pour tout entier naturel
n on a :
Page 6 sur 84
• v0=a+b= (1/5)(-u0=u0.
• v1=a+b=(1/5)(-u1=u1.
• vn-1+vn-2=a(n-2(+1))+ b(n-2(+1))= an+bn=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 an+bn, 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, u n=an+bn, où et 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 a+b=u1.
En fait les suites de Fibonacci sont un cas particulier des suites (u) telles que pour tout n≥0,
un=Aun-1+Bun-2, avec A et B deux constantes réelles (A=1, B=1 redonne les suites de Fibonacci).
Si A2+4B≠0, une telle suite s'écrit aussi un=aαn+bβn, mais cette fois α et β sont les racines de x2-Ax-B=0.
Par exemple, si u0=0, u1=1, les termes suivants de la suite (u) sont
A, A2+B, A3+2AB, A4+3A2B+B2, A5+4A3B+3AB2,...
Chose "étonnante", si A>0 et B>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(A5+4A3B+3AB2,A3+2AB)=A
vérification :
pgcd(A5+4A3B+3AB2,A3+2AB)=Apgcd(A 4+4A2B+3B2,A2+2B)
Soit d un diviseur (entier >0) commun à A4+4A2B+3B2 et A2+2B :
il divise A4+4A2B+3B2-(A2+2B)2=-B2.
Si d≠1, alors d admet un diviseur premier m, lequel divise B2 donc B, donc m divise
(A2+2B)-2B=A2, donc m divise aussi A, ce qui est en contradiction avec le fait que A et B sont
premiers entre eux.
Donc on n'a pas d≠1, et ainsi d=1, ce qui donne pgcd(A4+4A2B+3B2,A2+2B)=1.
La preuve générale se fait comme pour la suite de Fibonacci (1.2 de P10) : voir cette preuve générale dans
mon étude sur ces suites un=Aun-1+Bun-2, le lien est indiqué dans la remarque 2 de P2 ci-dessus.
Page 7 sur 84
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 :
01
A=
11
.
On a donc, pour tout entier naturel n, Xn=AnX0, et donc pour obtenir X n, 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
| -X 1 |
=X2-X-1
| 1 1-X |
.
Les deux valeurs propres de A sont donc et , de vecteurs propres associés t( 1 ) et t( 1 ) 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
0
D=
0
.
On a donc An=PDnP-1, et comme
-1
P-1=1/(-)
- 1
Et comme ( un un+1 )=( u0 u1 )An (on a transposé l'égalité X n=AnX0), c'est que
un=1/(-)(u0(n-1-n-1)+u1(n-n)), ce qui donne, puisque -=5 et =-1
un=(1/(5))((-u0+u1)n+(u0-u1)n).
Note : dans le cas de la suite (F), un=Fn=(n-n)/5 (cet aspect sera développé à P5.2) et donc
Fn-1 Fn
An= =FnA+Fn-1I
Fn Fn+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.
4)
a) (u) étant une suite de Fibonacci quelconque, montrer que pour tout entier naturel k, pour tout entier
naturel nk, un+k=0jk Ckj un-j
Note : on convient que C00 =1 (pour le cas k=0).
Autre cas particulier, pour tout entier naturel n, u2n=0jn Cnj uj.
Vérifier pour u8, cette dernière formule dans le cas u0=0, u1=1, cad si (u)=(F).
b)
On généralise le résultat du a) aux suites (u) vérifiant la relation de récurrence un+2=Aun+1+Bun pour tout
n≥0, A et B étant deux constantes complexes.
On a alors, pour tout k≥0, tout n≥k, en convenant que C00 =1, A0=1, B0=1,
un+k=0jk Ckj Ak-jBjun-j.
On vérifie évidemment que A=B=1 redonne le 4.1).
Déduire de cette formule que si A et B sont entiers, si k est un nombre premier et n≥k, alors k divise
un+k-Aun+k-Bun-k.
On verra à la question 10 de cet exercice des précisions sur cette division dans le cas où la suite (u) est la
suite (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.
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
Page 9 sur 84
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
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>n-2 (si n=2, on a l'égalité : F2=1=0) ;
en déduire que limn->+Fn=+
e) montrer que pour tout entier naturel n1, n=Fn+Fn-1 ; cette relation est-elle encore vraie si on
remplace par ?
montrer que pour tout entier naturel n, Fn=(1/5)(n-n) (on retrouvera cette formule à P5.2)
Appliquer cette formule pour n=1 à 8 et vérifier alors que la somme des termes du triangle de
Pascal situés 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.
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 :
Page 10 sur 84
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
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
816
A= | 3 5 7 |
492
alors
u8 u1 u 6
B= | u3 u5 u7 |
u4 u9 u 2
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. Certains mettent 0≤p≤k, mais comme F0=0, ce n'est pas vraiment utile.
(Aide : utiliser la matrice A de la remarque 2 de P4 et élever à la puissance k la relation An=FnA+Fn-1I
ou ... utiliser Binet et αn=αFn+Fn-1 et idem avec β).
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.
Page 11 sur 84
Remarque 2 : 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)
En particulier 10 divise Fn+10-Fn+5-Fn, cad Fn+10 et Fn+5+Fn ont même chiffre des unités.
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?
11)
Soit (s) la suite définie par sn+2=-sn+1+sn pour tout n≥0. Cette suite n'est pas une suite de Fibonacci,
puisque le coefficient de sn+1 n'est pas 1.
Montrer que pour tout n≥0, sn+1=(-1)n(-s0Fn+s1Fn+1).
vers la solution...chercher avant de cliquer
P5.1->
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 , mais en oscillant autour de ce nombre d'or ; du moins, à partir d'un
certain rang assurant que le rapport (un+1/un-)/ (-(b/a)5(/)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 u n+1/un- est alors 5
(/)n et
pour n=7 on obtient (21/13-)/(5(/)7)=0,9988151...., ce qui donne 21/13-<0, soit F8/F7=21/13<, et
pour n=8 on obtient (34/21-)/(5(/)8)=1,000453..., soit cette fois F9/F8=34/21>.
Page 12 sur 84
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=-u0, et comme n'est pas rationnel cela conduit à u0=u1=0, donc contradiction)
P5.2->
5.2.1)
Ce qui donne pour les suites (F) et (L) 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.
5.2.2) Application des formules sommatoires pour déterminer, modulo n (avec n premier), Ln et Fn.
cad lorsqu'on utilise la théorie des résidus, le nombre premier 2 est exclu.
Par contre F5=5 qui n'est pas ≡ ±1 (5).
◦ si n est premier impair distinct de 5 alors
n divise Fn-1 ou Fn+1
De façon plus précise, toujours si n est premier impair distinct de 5
si 5 est un carré modulo n, on a Fn+1≡1 (n) et Fn-1≡0 (n)
si 5 n'est pas un carré modulo n, on a Fn+1≡0 (n)
On a donc toujours (n premier impair), F n-(5/n)≡0 (n) (car, par ailleurs, si n=5, (5/n)=0 et
F5=5)
Note :
Fn-1 et Fn+1 sont premiers entre eux (voir par exemple une des relations du 4) de P8), et à ce
titre le seul entier positif qui les divise simultanément est 1.
Exemples :
◾ F3=2≡-1 (3) puisque aucun des nombres 02, 12, 22 n'est congru à 5 modulo 3
◾ F7=13≡-1 (7) car 5 n'est pas un carré modulo 7 puisque aucun des nombres 02, 12, 22, 32
n'est congru à 5 modulo 7 (inutile d'examiner 4 2 car 42≡(-3)2 (7), etc... ) ou parceque 7≡2
(5) (voir critère ci-dessous).
◾ 5 est un carré modulo 11 puisque 5≡42 (11) ou (voir critère ci-dessous) parce que 11≡1
(5) ; on vérifie que F11=89≡1 (11) et 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 0 2, 12, 22, 32, 42, 52, 62 n'est
congru à 5 modulo 13 ou parceque 13≡3 (5) ; on vérifie que F13=233≡-1 (13) et 13
divise F13+1=377=13×29.
Un moyen rapide pour savoir si 5 est ou pas un carré modulo p (nombre premier impair distinct de 5)
est d'utiliser le résultat suivant :
5 est un carré modulo p <=> p≡±1 (5)
5 n'est pas un carré modulo p <=> p≡±2 (5)
Note : 5 est un carré (12) modulo 2 mais 2 n'est pas congru à ±1 modulo 5 et 5 est un carré (52)
modulo 5 mais 5 n'est pas congru à ±1 modulo 5.
Remarque 1
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 qui seront vues au 15) de P8.
P5.3->
Page 14 sur 84
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->
◦ F2n=(2/5)sinh(2n)
◦ F2n+1=(2/5)cosh((2n+1))
◦ L2n=2cosh(2n)
◦ L2n+1=2sinh((2n+1))
◦ F2n/L2n=tanh(2n)/5
◦ L2n+1/F2n+1=5tanh((2n+1))
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|<||=1/, G(x)=n=0+unxn.
En particulier
Remarque :
si b=0, cad si un=an avec a0, la fonction génératrice est u0/(1-x) pour |x|<1/.
si a=0, cad si un=bn avec b0, la fonction génératrice est u0/(1-x) pour |x|<.
k=0nukxk= (u0+(u1-u0)x-un+1xn+1-unxn+2)/(1-x-x2)
Page 15 sur 84
Remarque : si x=- ou -, 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
4) n étant un entier naturel, un réel quelconque, exprimer (sans formule sommatoire) en fonction de Ln,
Ln+1 et les deux expressions suivantes
• k=0nLkcos(k)
• k=0nLksin(k)
vers la solution...chercher avant de cliquer
Exercice 4
1) Montrer que n=1+Fn/2n=2
P7-> Quelques relations linéaires entre les suites de Fibonacci (F) et (L).
1) pour tout entier naturel n, F n+Ln=2Fn+1
Remarque 1 :
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
Remarque 2 : 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.
Page 16 sur 84
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.
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)=(u0-u1)(-u0+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 se généralise à toute suite de Fibonacci, un+2=un+1+un, qui s'écrit un=aαn+bβn (a et b
dépendent de u0 et de u1 : voir P14): un2-un-1un+1=(-1)n×5×ab.
Elle s'obtient sans difficulté à partir de la formule de Binet pour un ci-dessus, et si a=-b=1/sqrt(5) on
retrouve la formule ci-dessus pour (F) et si a=b=1 on obtient, pour la suite de Lucas Ln2-Ln-1Ln+1=
(-1)n×5
La formule de Cassini pour la suite (F) (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.
cette relation combinée avec celle de Cassini (voir 2) ci-dessus) donne Fn+12-Fn-1Fn+3=(-1)n-1 et donc
Fn-1 et Fn+1 sont premiers entre eux
par exemple : F52-F3F7=(-1)3, cad 52-2×13=-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)
Page 17 sur 84
Remarque : on déduit tout de suite de cette formule que Fn et Fn+2 sont premiers entre eux. Voir
aussi P10.
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 (L n)21 (5), ce qui est cohérent avec la relation de congruence
du 4) ci-dessus.
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 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.
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.
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.
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)
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
◾ en remplacant n par 2p, on obtient FmL2p=Fm+2p+Fm-2p, qui donne pour p≥1 et m≥2p+2
la Z_somme de FmL2p (voir P11, exercice 13)
◾ 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 façon
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)
◦ 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
5FpFqFr=Fp+q+r+(-1)p+1F-p+q+r+(-1)q+1Fp-q+r+(-1)r+1Fp+q-r
Cas particuliers :
◦ p=q=r donne 5Fp3=F3p+3(-1)p+1Fp (déjà obtenue au 15.7 via le cas m=2n)
Page 20 sur 84
Application à une formule de Stanley Rabinowitz donnée dans son article de 1997 intitulé
Algorithmic summation of reciprocals of products of Fibonacci numbers.
(-1)n/(Fn+aFn+bFn+c)=A/Fn+a+B/Fn+b+C/Fn+c
avec
A=(-1)a/(Fb-aFc-a)+(-1)b/(Fc-bFa-b)+(-1)c/(Fa-cFb-c)
◾ U=(-1)nFa-bFb-cFc-a
◾ V1=(-1)b+1Fb-cFn+bFn+c
◾ V2=(-1)c+1Fc-aFn+aFn+c
◾ V3=(-1)a+1Fa-bFn+aFn+b
Et on applique quatre fois la formule de linéarisation d'un produit de trois termes de la suite
(F) ; pour U c'est instantané vu le cas particulier p+q+r=0 vu ci-dessus.
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.
En effet,
pour n≥1 impair 1/(1+(-1)n+1/αn)=1/(1+1/αn)<1
pour n≥1 pair 1/(1+(-1)n+1/αn)=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+......... ).
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.
En effet,
∑n≥11/F2n=√5(∑n≥11/(α2n-β2n)), 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.
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-), 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
◦ n=1+ (-1)n-1/(FnFn+1)=-1=(√5-1)/2
4) Montrer que
• n=1+ 1/(F2nF2n+2)=-1=(3-5)/2
• n=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).
Remarque : d'après un document sur les nombres de Ribenboim Paulo, les sommes suivantes ne sont pas
des nombres rationnels :
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.
Page 22 sur 84
1) q étant un entier naturel non nul, montrer que k=1+ (F(2q))/(F(2q+k))=1/(e), 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.
Remarque 1 : d'après le document de Ribenboim cité ci-dessus, cette relation a été obtenue par Good en
1974 et Hoggat en 1976.
P9->
1) nN-{0;1}, Fn+1=E((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+1Fn (puisque limn->+Fn+1/Fn=, cf voir P5.1) ; on peut d'ailleurs retrouver cette limite à partir
de cette relation.
On a aussi
application :
on retrouve (voir exercice 1 ou relation 2 de P8) que Fn et Fn+1 sont premiers entre eux car
Page 23 sur 84
Remarque 2 : (F) n'est pas la seule suite d'entiers à vérifier cette propriété : voir remarque 1 de
P4.
1.4) Réciproque du 1.3) : 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.
On notera que Fn2 divise Fm (donc Fn divise Fm) implique bien n divise m.
L'équivalence est fausse pour n=2 et m impair car alors Fn2=1 divise Fm et nFn=2 ne divise pas m.
1.5) Si n est distinct de 4 et si F n 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).
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
Page 24 sur 84
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.
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.
Page 25 sur 84
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/ln+1,lna/ln) ; ce min est égal à lnb/ln+1b<a/.
Remarque 1 : cf par exemple la revue APMEP n°445, le mathématicien français 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 :
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 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.
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.
• 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)
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).
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
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.
Page 27 sur 84
Remarque 2 : cette propriété sera à la base de l'élaboration d'une stratégie gagnante dans le jeu de Nim-
Fibonacci.
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.
Z_somme de kFn
k s
pour ns
1 Fn 2
2 Fn-2+Fn+1 4
3 Fn-2+Fn+2 4
4 Fn-2+Fn+Fn+2 4
5 Fn-4+Fn-1+Fn+3 6
6 Fn-4+Fn+1+Fn+3 6
7 Fn-4+Fn+4 6
8 Fn-4+Fn+Fn+4 6
9 Fn-4+Fn-2+Fn+1+Fn+4 6
10 Fn-4+Fn-2+Fn+2+Fn+4 6
11 Fn-4+Fn-2+Fn+Fn+2+Fn+4 6
12 Fn-6+Fn-3+Fn-1+Fn+5 8
13 Fn-6+Fn-3+Fn+1+Fn+5 8
14 Fn-6+Fn-3+Fn+2+Fn+5 8
15 Fn-6+Fn-3+Fn+Fn+2+Fn+5 8
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.
Commentaire sur le tableau ci-dessus : on observe dans ce tableau qu'à chaque fois que la Z_somme de
kFn est constitué de deux termes, alors k est un terme de la suite de Lucas d'indice pair.
En effet k=2=L0, k=3=L2 et k=7=L4 : en fait ceci correspond à la formule Fn-2p+Fn+2p=L2pFn (voir 15.7 de
P8), qui donne donc pour p≥1,n≥2p+2 la Z_somme de L2pFn.
On peut alors se poser la question de savoir si le fait que kFn a une Z_somme composée de deux termes
(pour n≥n0) implique que k est un terme de la suite de Lucas d'indice pair. En fait c'est faux car 6F 4=F5+F7
et 6≠ L2p (on notera, voir tableau, que la Z_somme de 6Fn est constituée de trois termes que si n≥6).
Par contre, si on cherche deux entiers distincts a et b et non consécutifs tels que pour tout n≥0 on ait
kFn=Fa+n+Fb+n, alors effectivement k=L2p!
En effet :
n=0 donne alors Fa+Fb=0, or d'après F-n=(-1)n+1Fn, cela n'est possible que si a=-b=2p≥2 ou {a;b}={-2;-1}
Page 28 sur 84
(ce qui est exclu car a et b ne doivent pas être consécutifs) ou {a;b}={-2;1}.
Compte-tenu que n=1 implique k=Fa+1+Fb+1
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).
• tous les couples solutions, dans N×N, de l'équation x2-5y2=4 sont les couples (L2n,F2n) pour n
dans N
• tous les couples solutions, dans N×N, de l'équation x2-5y2=-4 sont les couples (L2n+1,F2n+1) pour
n dans N
Exercice 14 : vérifier que pour tout n ≥0, les couples (Fn,Fn+1) sont effectivement solutions de l'équation
diophantienne |x2+xy-y2|=1 ;
Page 29 sur 84
Pour une réciproque (Théorème de Lucas,1876), je renvoie le lecteur à la preuve proposée par le numéro
28 de la revue Quadrature (Avril, Mai Juin 1997) ; cette preuve passe par la recherche des éléments
inversibles de l'anneau {x+y ; xZ ; yZ}.
Complément : on pose P(x,y)=y(2-(x2+xy-y2)2), soit
P(x,y)=-x4y-2x3y2+x2y3+2xy4-y5+2y.
Montrer que lorsque x décrit l'ensemble des entiers relatifs et y l'ensemble des entiers naturels, les valeurs
positives ou nulles prises par P(x,y) sont exactement toutes les valeurs prises par la suite (F).
Aide : il n'y a pas beaucoup d'entiers dont le carré est inférieur à 2.
Note : P(1,-2)=46 n'est pas un Fn.
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 :
n 0 1 2 3 4 5 6 7 8 9 10 11 12
Fn 0 1 1 2 3 5 8 13 21 34 55 89 144
F'n
0 1 1 0 1 1 0 1 1 0 1 1 0
pour m=2
F'n
0 1 1 2 0 2 2 1 0 1 1 2 0
pour m=3
F'n
0 1 1 2 3 1 0 1 1 2 3 1 0
pour m=4
F'n
0 1 1 2 3 0 3 3 1 4 0 4 4
pour m=5
F'n
0 1 1 2 3 5 2 1 3 4 1 5 0
pour m=6
Il semble, dans les cas m=2, 3, 4, que les suites (F') soient périodiques à partir du rang 0, 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).
• 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 à partir du rang 0 : 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).
Page 30 sur 84
01
A=
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 F g(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, donc
g(m) est la période d'apparition de 0 dans la suite de Fibonacci modulo m
et k(m)/g(m)=1 ou 2 ou 4 (on pourra voir dans la revue Quadrature n°101 la caractérisation de
ces 3 possibilités)
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 5, alors
p divise Fp-1 ou Fp+1, et donc g(p)≤p+1.
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 ≥1 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-après pour le cas particulier k(2e).
Page 31 sur 84
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 16 :
valeurs de n modulo 6 0 1 2 3 4 5
valeurs de Fn modulo 4 0 1 1 2 3 1
valeurs de Ln modulo 4 2 1 3 0 3 3
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)
Aide :
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(/5))(1+4cos2(2/5))(1+4cos2(3/5))(1+4cos2(4/5))
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.
• U0(X)=1
• U1(X)=2X
• pour tout entier naturel n, non nul, Un+1(X)=2XUn(X)-Un-1(X)
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!
4) Montrer que pour tout entier naturel n3, Fn=k=1 E((n-1)/2)(1+4cos2(k/n))=k=1 E((n-1)/2)(3+2cos(2k/n))
Exercice 18 : le but de cet exercice est de "vérifier", pour les petites valeurs de n, la formule
Fn=k=1 E((n-1)/2)(3+2cos(2k/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.
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.
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.
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 vérifiant la
relation de récurrence :
• Rk+1,n(X)=XRk,n(X)+(-1)n+1Rk-1,n(X).
Page 33 sur 84
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,
• 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 ∑)
• 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
Pour tout entier k≥0, Q2k+1,n et Q2k,n sont des polynômes impairs, à coefficients entiers (leur valeur
absolue ne dépend pas de n).
Les formules explicites de Q2k+1,n et Q2k,n sont les suivantes :
Remarque 1 : 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, L n ne divise pas Lkn : L3=4 ne divise pas L2×3=18.
Remarque 2 : 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
Exemples
F69=F3×23=Q3,23(F23)=5F233-3F23
F69=5×286573-3×28657
F69=117669030460994.
F70=F5×14=Q5,14(F14)=25F145+25F143+5F14
F70=25×3775+25×2773+5×377
F70=190392490709135.
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
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.
P17-> Sur les termes carrés dans les suites (L) et (F).
n étant un entier relatif (voir P2, P5.3)
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 détailler un papier de John H.E Cohn qui donne une preuve plus courte que
celle de 1964.
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) : L n 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 x 2 -a, cad
a≡x2 (p), cad a congru à x2 modulo p.
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 :
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
Page 37 sur 84
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
1) Soit (u) une suite de Fibonacci quelconque ; d'après la foumule de Binet vue à P4, (u)=a(e)+b(f), les suites
(e) et (f) étant définies par en=n et fn=n, 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
a+b=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).
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.
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.
u2=u1+u0
u4=u3+u2
.
.
u2n+2=u2n+1+u2n
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).
Page 38 sur 84
On a donc montré par récurrence que si on a u 0=0 ou u0=u1 la relation u02+...+un2=unun+1 est vraie pour tout
n≥0.
En faisant n=k, la formule précédente donne u2k=0jk Ckj uk-j. Et comme Ckj =Ckk-j, en posant k-j=i on obtient
u2k=0ik 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.
b)
On peut aussi utiliser la formule de Binet, mais pour que l'équation caractéristique x2-Ax-B=0 ait deux racines
distinctes il faut A2+4B≠0 ; cependant même s'il y a une racine double, le résultat est vrai (voir une preuve
dans mon papier sur suites (AB)).
Notons ici r et s les solutions distinctes de l'équation caractéristique (avec A2+4B≠0) et donc un=arn+bsn, a et b
obtenus via u0=a+b et u1=ar+bs.
• si A≠0 et B≠0 :
le membre de droite de l'égalité à démontrer est alors
D=Σ0≤j≤kCkjAk-jBj(arn-j+bsn-j)
D=Ak-nBn[Σ0≤j≤kCkjAn-jBj-n(arn-j+bsn-j]
D=Ak-nBn[aΣ0≤j≤kCkjBj-n(Ar)n-j+bΣ0≤j≤kCkjBj-n(As)n-j]
D=Ak-nBn[a(Ar/B)nΣ0≤j≤kCkj(B/(Ar))j+b(As/B)nΣ0≤j≤kCkj(B/(As)j]
D=Ak-nBn[a(Ar/B)n(1+B/(Ar))k+b(As/B)n(1+B/(As))k]
Mais 1+B/(Ar)=r/A et 1+B/(As)=s/A (car r et s sont racines de l'équation caractéristique), donc
D=Ak-nBn[a(A/B)nrn+k/Ak+b(A/B)nsn+k/Ak]
Et finalement D=arn+k+bsn+k=un+k
• si A≠0 et B=0 :
le membre de droite de l'égalité à démontrer est D=Akun
mais, par définition de la suite (u) on a u n+2=Aun+1, soit pour n≥1, un=An-1u1
donc D=AkAn-1u1=un+k
• si A=0 et B≠0 :
le membre de l'égalité à démontrer est D=Bkun-k
mais, par définition de la suite (u) on a u n+2=Bun, donc u2n=Bnu0 et u2n+1=Bnu1
◦ si n-k est pair, n+k est aussi pair et D=BkB(n-k)/2u0=B(n+k)/2u0=un+k
◦ si n-k est impair, n+k est aussi impair et D=BkB(n-k-1)/2u0=B(n+k-1)/2u0=un+k
D'après la relation qui vient d'être prouvée, un+k=Akun+k+Bkun-k+E où E est une somme d'entiers, chacun
divisible par Ckj avec j≠0 et j≠k, donc ces coefficients binomiaux sont divisibles par k, puisque k est
premier : donc k divise un+k-(Akun+k+Bkun-k).
Mais d'après le théorème de Fermat, k divise Ak-A et Bk-B, et finalement k divise un+k-Aun+k-Bun-k.
Page 39 sur 84
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.
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 E n : 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)
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.
Page 40 sur 84
3)
◦ les coefficients a et b des diverses relations de la forme Fn=aFn-i+bFn-i-1 obtenues ci-dessus sont
des termes de la suite de Fibonacci Fn!
En fait ceci correspond au 6) de P3 où on a vu que
Fn+p=Fp-1Fn+FpFn+1, ce qui donne en changeant n en n-p
Fn=FpFn-p+1+Fp-1Fn-p.
Par exemple p=6 donne Fn=F6Fn-5+F5Fn-6=8Fn-5+5Fn-6
◦ pour tous les entiers m considérés ci-dessus ( 2 à 10) le critère de divisibilité de Fn par m est de la
forme g(m) divise n, et on vérifie que ce g(m) n'est autre que le plus entier p non nul tel que m
divise Fp :
plus petit entier p critère de divisibilité
m
tel que m divise Fp de Fn par m
2 3 3 divise n
3 4 4 divise n
4 6 6 divise n
5 5 5 divise n
6 12 12 divise n
7 8 8 divise n
8 6 6 divise n
9 12 12 divise n
10 15 15 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
Page 41 sur 84
4) On a aussi Ln=2Ln-2+Ln-3, donc Ln et Ln-3 ont même parité et comme parmi L 0=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 > n-2.
6e)
On va procéder, là aussi, par récurrence pour prouver que pour tout entier naturel non nul on a n=Fn+Fn-1.
(On peut aussi utiliser le 1) de P3).
La relation est encore vraie si on remplace par , puisque de même que +1=2, on a +1=2.
Par différence membre à membre des deux relations n=Fn+Fn-1 et n=Fn+Fn-1, on obtient tout de suite
Fn=(1/5)(n-n).
6f)
Page 42 sur 84
• cas n impair
s=Cn-10 +Cn-21 +...+Cn-1-((n-1)/2-1)(n-1)/2-1 +C(n-1)/2(n-1)/2 +
Cn0 +Cn-11 +Cn-12+ ...+Cn-(n-1)/2(n-1)/2
s=Cn0 +Cn1 +Cn-12 +... +Cn-(n-1)/2+1(n-1)/2 +C(n-1)/2(n-1)/2
s=Cn+10 +Cn+1-11 +Cn+1-22 +...+Cn+1-(n-1)/2(n-1)/2 +Cn+1-(n+1)/2(n+1)/2 =Gn+2.
• cas n pair
s=Cn-10 +Cn-21 +...+Cn-1-(n-2)/2(n-2)/2 +
Cn0 +Cn-11 +Cn-12 + ...+Cn-(n/2-1)n/2-1 +Cn-n/2n/2
s=Cn0 +Cn1 +Cn-12+... +Cn/2+1n/2
s=Cn+10 +Cn+1-11 +Cn+1-22 +...+Cn+1-n/2n/2 =Gn+2.
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 et sur son dernier terme) :
• n=1 : F1=C00 =1
• n=2 : F2=C10 =1
• n=3 : F3=C20 +C11 =1+1=2
• n=4 : F4=C30 +C21 =1+2=3
• n=5 : F5=C40 +C31 +C22 =1+3+1=5
• n=6 : F6=C50 +C41 +C32 =1+4+3=8
• n=7 : F7=C60 +C51 +C42 +C33 =1+5+6+1=13.
• n=8 : F8=C70 +C61 +C52 +C43 =1+6+10+4=21
6g)
Une récurrence facile donne le résultat : notons pour tout entier naturel n1, Sn=0in(-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=1in2n-iFi-1.
7a) On a u0=2030=1
• u1=1×7=7 (le seul li qui donne un nombre entier est ici l11=7).
• u1=7×13/7=13 (l10=13/7 est le seul li qui donne ici un entier)
• u2=13×19/13=19 (l7=19/13 est le seul li qui donne ici un entier)
• u3=19×1/19=1 (l8=1/19 est le seul li qui donne ici un entier)
Donc la suite (u) est périodique : 1, 7, 13, 19, 1, 7, 13, 19, 1.....
• u1=2a3b×(5×7/2)=2a-13b×5×7
• On multiplie par 11/(2×7) puis, juste après, par 5×7/11, cela a-1 fois, et 2a-13b×5×7 devient 3b5a7
(car la multiplication par 11/(2×7) diminue de 1 l'exposant de 2 et la maultiplication par 5×7/2 augmente
de 1 l'exposant de 5)
si a=1, cette étape n'existe pas, u1 étant égal alors à 3b×5a7
• On multiplie 3b5a7 par 13/7 et on obtient 3b5a13
• On multiplie par 17/(3×13) puis, juste après, par (2×5×13)/17, cela b fois, et 3 b5a13 devient 2b5a+b13
(car la multiplication par 17/(3×13) diminue de 1 l'exposant de 3 et la multiplication par (2×5×13)/17
augmente de 1 l'exposant de 2 et celui de 5)
• On multiplie 2b5a+b13 par 19/13 et on obtient 2b5a+b19
• On multiplie par 23/(5×19) puis, juste après, par 3×19/23, cela a+b fois, et 2 b5a+b19 devient 2b3a+b19
(car la multiplication par 23/(5×19) diminue de 1 l'exposant de 5, et la multiplication par 3×19/23
augmente de 1 l'exposant de 3)
• On multiplie 2b3a+b19 par 1/19 et on obtient 2b3a+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.
8)
b) Pour calculer S1 et S2 dans le cas particulier demandé (s=15), il y a deux méthodes possibles :
• 1ère méthode : on utilise la formule générale obtenue ci-dessus, mais en fait cela donne des calculs assez
longs et "délicats". Les voici.
K=-1-13+3-9-5-1+7--3+11=-+3-(1-2+4-6+8-10+12)
K=-+3-(1+14)/(1+2).
Page 44 sur 84
Comme (voir question 6 de cet exercice) n=Fn+Fn-1 et n=Fn+Fn-1, et aussi /(1+2)=-1/r et /(1+2)
=1/r,
on obtient
K=+1+(234+377)/r et K'=+1-(234+377)/r.
Ce qui donne
S1=S2=3((-u0+u1)/r)3(610+377)+3((u0-u1)/r)3(610+377)+(-u0+u1)/r)(u0-u1)/r)2
(+1+234/r+377/r)+(-u0+u1)/r)2(u0-u1)/r)(+1-234/r-377/r).
• 2ième méthode :
Cf P3, un=u0Fn-1+u1Fn et donc
.
13u0+21u1 u1 5u0+8u1
B= | u0+2u1 3u0+5u1 8u0+13u1 |
2u0+3u1 21u0+34u1 u0+u1
Fn-1 Fn
An= =FnA+Fn-1I
Fn Fn+1
avec
A= 0 1
Page 45 sur 84
11
n
On élève alors à la puissance k la relation A =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
• Fn=Fn
• F2n=2FnFn-1+Fn2=Fn(Fn+2Fn-1), qui n'est autre, cf P7, que FnLn
• F3n=3FnFn-12+3Fn2Fn-1+2Fn3
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
hypothèse.
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=0jpCpj un-j, soit en changeant n en n+p,
pour tout entier naturel n, un+2p=0jkCpj un+p-j.
Or, cf un résultat d'arithmétique, 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
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
d) On peut effectivement remplacer p par pr, avec r dans N, pour les résultats 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 :
• pour le a) c'est encore vrai car la démonstration proposée fonctionne encore telle quelle
• pour le b) cela résulte du résultat suivant :
p divise Cpr j pour j=1,2,...,pr-1, la preuve pouvant se faire à partir du cas r=1 : dans Z/pZ[X], on a
Page 46 sur 84
r r
(1+X)p=1+Xp, puis par des élévations sucessives à la puissance p, on obtient (1+X)p =1+Xp , et on
identifie les coefficients des deux polynômes.
La démonstration du b) fonctionne alors elle aussi encore parfaitement... en remplacant partout p par pr.
11)
Pour n=0, n=1 la formule sn+1=(-1)n(-s0Fn+s1Fn+1) est effectivement vraie, puisque s1=1×s1 et s2=-1×(-s0+s1).
Si on la suppose vraie jusqu'au rang n≥1,
alors de sn+2=-sn+1+sn on déduit, puisque par hypothèse de récurrence la formule est supposée vraie aux rangs n
et n-1,
sn+2=-(-1)n(-s0Fn+s1Fn+1)+(-1)n-1(-s0Fn-1+s1Fn)
sn+2=(-1)n+1(-s0Fn+s1Fn+1-s0Fn-1+s1Fn+1)
sn+2=(-1)n+1(-s0(Fn+Fn-1)+s1(Fn+Fn+1))
sn+2=(-1)n+1(-s0Fn+1+s1Fn+2) et la formule est vraie au rang n+1.
Remarque : le résultat tient au fait que l'équation caractéristique de la suite (s) est x2+x-1=0 et donc a pour
racines - et - alors que l'équation caractéristique de la suite (F) est x2-x-1=0 dont les racines sont et .
Exercice 2
1)
preuve de P5.1
On a un=an+bn.
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=(an+1+bn+1) /(an+bn)= (a+bn) /(a+bn) ; comme |/|<1, limn->un+1/un=a/a=.
Précisons la vitesse de convergence :
-un+1/un=-(an+1+bn+1)/(an+bn)
=(bn-bn+1)/(an+bn)
=bn(-)/(an+bn)
=b(/)n(-)/(a+b(/)n).
Comme le dénominateur de la dernière expression tend vers a, c'est qu'un équivalent de -un+1/un est
(b/a)(-)(/)n ; comme -=5, c'est que cet équivalent est bien (b/a)5(/)n.
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-(/)n ; comme |/|<0.382, pour tout n1 on a |/|n<0.382, donc
-0.382<(/)n<0.382, ce qui donne vn>0 pour tout n1, et un+1 converge vers en oscillant à partir du
rang 1 (ici u0=0).
On peut le vérifier sur la suite (F) : F2/F1=1<, F3/F2=2>, F4/F3=3/2<,...
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+(/)n, et l'encadrement ci-dessus donne, pour tout n1, (/)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 dès le rang 0.
On peut le vérifier pour la suite (L) : L1/L0=1/2<, L2/L1=3>, L3/L2=4/3<,...
Pour ce qui est de limn->+un+k/un=k, 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 lorsque n tend vers + ; si k=0 le résultat est trivial.
preuve de P5.2.1
Pour prouver que pour tout entier naturel n non nul, Fn=(1/2n-1)0p(n-1)/25pCn2p+1, il suffit d'appliquer deux fois
la formule du binôme dans Fn=(1/5)(n-n) :
Fn=(1/5)(1/2n)(0knCnk (5)k- 0knCnk (-1)k(5)k) : on voit tout de suite que les termes de chaque
correspondants à k pair (il y en a que si n est non nul) s'éliminent, et ceux correspondants à k impair s'ajoutent :
Quant aux formules dites de Moivre, la preuve est évidente, les membres de droite et de gauche étant égaux à
kn pour la 1ière formule et égaux à kn pour la 2ième.
• F3n=(3Fn(Ln)2+5(Fn)3)/4
• L3n=(15Ln(Fn)2+(Ln)3)/4
Page 48 sur 84
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.
preuve de P5.2.2
Pour n premier, les valeurs modulo n de Fn et Ln s'obtiennent en utilisant les formules sommatoires vues au
5.2.1 et 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.
Pour Fn≡±1 (n), une preuve rapide consister à utiliser la relation 7 de P8, qui donne pour n impair, 5Fn2-4=Ln2.
On en déduit alors pour n premier impair que 5Fn2≡4+1≡5 (n), puisque Ln≡1 (n), et ainsi n divise 5(Fn2-1) ;
comme en plus n, qui est premier, est distinct de 5, c'est que n divise le facteur Fn2-1, donc divise Fn-1 ou Fn+1,
soit Fn≡±1 (n).
Mais ainsi, on ne sait pas différentier les cas Fn≡1 (n) et Fn≡-1 (n).
Pour cela on utilise les résultats rappelés sur les résidus qui donnent (rappel : n est premier distinct de 2 et 5) :
• 5(n-1)/2≡(5/n) (n)
• (5/n)=1 si 5 est un carré modulo n, sinon (5/n)=-1.
Et comme on a vu plus haut que Fn≡5(n-1)/2 (n), on obtient les résultats annoncés.
d'après la formule de Cassini (voir 2) de P8), Fn2-Fn-1Fn+1=(-1)n-1, et comme on a vu que Fn2≡1 (n), c'est
que Fn-1Fn+1≡0 (n) et donc n divise Fn-1Fn+1, donc n divise l'un des facteurs.
Mais avec cette méthode on ne sait pas différentier les cas n divise Fn-1 et n divise Fn+1.
Pour cela on va utiliser la formule sommatoire vue pour Fn, mais appliquée à Fn+1.
Fn+1=(1/2n)∑0≤k≤n/2 5kCn+12k+1.
On a d'ailleurs vu au début de la preuve de ce P5.2.2, que pour n premier, Fn≡5(n-1)/2 (n), cela par utilisation de
si n est premier, alors n divise Cni pour 1≤i≤n-1 et an-1≡1 (n) si n ne divise pas a (petit théorème de
Fermat).
On va encore utiliser ces résultats en remarquant que (n-i+1)Cn+1i =(n+1)Cni, et donc
pour 1≤i≤n-1, n divise Cni, donc divise (n-i+1)Cn+1i.
Mais si i≥2, n-i+1<n, donc n-i+1 n'est pas divisible par n, et comme n est premier c'est que
pour 2≤i≤n-1, n divise Cn+1i.
Donc, modulo n, dans le ∑ donnant Fn+1,
seuls les termes correspondants à k=0 (2k+1=1) et k=(n-1)/2 (2k+1=n) vont "rester" :
∑0≤k≤n/2 5kCn+12k+1 ≡ 50(n+1)+5(n-1)/2Cn+1n (n).
Mais n+1≡1 (n) et Cn+1n =Cn+11 =n+1≡1 (n), d'où
Page 49 sur 84
2nFn+1≡1+5(n-1)/2 (n).
Et d'après la théorie des résidus, 5(n-1)/2≡(5/n) (n) avec (5/n) le symbole de Legendre.
Ainsi, 2nFn+1≡1+(5/n) (n).
D'où, si 5 n'est pas un carré modulo n, (5/n)=-1 (cela par définition du symbole de Legendre, puisque par
ailleurs n ne divise pas 5)
et ainsi 2nFn+1≡0 (p), et comme n est impair donc premier avec 2, donc avec 2n, Fn+1≡0 (n) ; ici il n'est pas
nécessaire d'utiliser le fait que 2n≡2 (n), d'après Fermat.
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=an+bn 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(n-n)+u0(n-n))/r.
Donc, en changeant n en -n et compte-tenu que =-1,
u-n=(-1)n(u1(n-n)+u0(n+1-n+1))/r,
ce qui donne (-1)n+1u-n=un+(u0/r)(n+1-n+1-n+n),
soit (-1)n+1u-n=un+(u0/r)(n(-)-n(-)),
et comme -=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(n+n)=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.
preuve de P5.4
Puisque =e, =-1/=-e-.
F2n=(1/5)(2n-2n)=(1/5)(e2n-(-1)2ne-2n)
=(1/5)(e2n-e-2n)=(2/5)sinh(2n)
F2n+1=(1/5)(2n+1-2n+1)
=(1/5)(e(2n+1)-(-1)2n+1e-(2n+1))
=(1/5)(e(2n+1)+e-(2n+1))
=(2/5)cosh((2n+1))
Les résultats relatifs à L2n et L2n+1 s'obtiennent de façon identique à partir de Ln=n+n.
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=(an+bn)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=, donc limn->+|un+1/un|= et ainsi le rayon de convergence
de cette série est 1/=||.
Pour |x|<|| on a
Page 50 sur 84
• G(x)=u0+u1x+u2x2+u3x3+...
• -xG(x)=-u0x-u1x2-u2x3-u3x4-...
• -x2G(x)=-u0x2-u1x3-u2x4-u3x5-...
En ajoutant membres à membres ces trois égalités on obtient (1-x-x 2)G(x)=u0+(u1-u0)x+0x2+0x3+..., et donc
G(x)=(u0+(u1-u0)x)/(1-x-x2) (pour |x|<||, 1-x-x2 est non nul, puisque cette expression ne s'annule que pour
et , dont les valeurs absolues ne sont pas strictement inférieures à ||).
Un autre moyen de déterminer G(x) est d'utiliser la formule de Binet : u nxn=a(x)n+b(x)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/||=|| et
1/||= ; le plus petit de ces rayons de convergence est || qui est donc le rayon de convergence de la série
somme, et on a alors pour |x|<||,
G(x)=a/(1-x)+b/(1-x)=(a+b-(b+a)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
-b-a=b(-1)+a(-1)= a+b-(a+b)=u1-u0.
Dans le cas b=0, a0, vn=a(x)n est une série géométrique de raison x et donc de rayon de convergence
1/||=|| et de somme G(x)=a/(1-x)=u0/(1-x).
Dans le cas a=0, b0, vn=b(x)n est une série géométrique de raison x et donc de rayon de convergence
1/||= et de somme G(x)=b/(1-x)=u0/(1-x).
Pour retrouver P6.1, on suppose |x|<||=1/ (donc x est bien différent de - et de -) et on fait tendre n vers
l'infini dans la relation qui vient dêtre trouvée.
Cf Binet,unxn=a(x)n+b(x)n, et puisque |x|<1, |x|<||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 u n+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=-.
On obtient alors (voir P4 pour a et b)
u0+(u1-u0)(-)+(-1)n(a2n+2+b()n+1)-(-1)n(a2n+2+b()n2)
=u0+(u1-u0)(-)-b-b2, puisque =-1
=a+(a+b)-b2, puisque u0=a+b et u1-u0=a(-1)+b(-1)=-a-b
=a+a(-1)=0
3) En posant r=1/5, on a F2nxn=r(2x)n-(2x)n), différence de deux suites géométriques, qui convergent toutes
les deux si et seulement si |2x|<1 et |2x|<1, ce qui équivaut à |x|<2, puisque =-1, ||<.
Donc, pour |x|<2, H(x)=n=0+F2nxn=r(1/(1-2x)-1/(1-2x)), ce qui donne, puisque
Page 51 sur 84
2+2=(+)2-2=1+2=3 et 2-2=(-)(+)=1/r,
H(x)=x/(1-3x+x2).
F2n+1xn=r((2x)n-(2x)n),
d'où, pour |x|<2, K(x)=n=0+F2n+1xn=r(/(1-2x)-/(1-2x))=r(-+(-)x)/(1-3x+x2), soit
K(x)=(1-x)/(1-3x+x2).
(Fn)2xn=(1/5)((2x)n+(2x)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|<2 (min des trois rayons de convergence),
d'où, pour x<||2,
L(x)=n=0+(Fn)2xn=(1/5)(1/(1-2x)+1/(1-2x)-2/(1+x))=(1/5)((2-3x)/(1-3x+x2)-2/(1+x)), soit
L(x)=(x-x2)/((1+x)(1-3x+x2)).
4) On remplace dans la relation P6.2, uk par Lk et x par ei (quantité bien différente de - et - pour tout réel )
et on obtient, en posant A=k=0nLkcos(k) et B=k=0nLksin(k),
A+iB=U/V avec
• U=2-ei-Ln+1ei(n+1)-Lnei(n+2)
• V=1-ei-e2i
• A=(1/(3-2cos(2))(3-2cos()-2cos(2)+Ln+1(cos((n-1))+cos(n)-cos((n+1))
+Ln(cos(n)+cos((n+1))-cos((n+2)))
• B=(1/(3-2cos(2))(2sin(2)+Ln+1(sin((n-1))+sin(n)-sin((n+1))
+Ln(sin(n)+sin((n+1))-sin((n+2)))
Quelques vérifications :
si =0 alors
◦ A=-1+Ln+1+Ln=-1+Ln+2, en accord avec la question 3) de l'exercice 1
◦ B=0, ce qui est normal puisque dans ce cas B est une somme de termes tous nuls
si n=1
◦ A=(1/(3-2cos(2)))(3-2cos()-2cos(2)+3(1+cos()-cos(2))+(cos()+cos(2)-cos(3)))
A=(1/(3-2cos(2)))(6+2cos()-4cos(2)-cos(3))
Mais cos(3)=cos(2)cos()-sin(2)sin() et sin(2)sin()=2sin2()cos()=(1-cos(2)cos(), et
donc
A=(1/(3-2cos(2)))(6+3cos()-4cos(2)-2cos(2)cos()
=(1/(3-2cos(2)))(2(3-2cos(2))+cos()(3-2cos(2))
=2+cos()=L0+L1cos()!
Page 52 sur 84
◦ B=(1/(3-2cos(2)))(2sin(2)+3(sin()-sin(2))+(sin()+sin(2)-sin(3)))
B=(1/(3-2cos(2)))(4sin()-sin(3))
Là encore, on transforme sin(3) en sin(2)cos()+cos(2)sin(),
puis sin(2)cos()=2sin()(1+cos(2))/2, ce qui donne
B=(1/(3-2cos(2)))(3sin()-2sin()cos(2))=sin()=L0+L1sin()!
Exercice 4
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 : n=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.
4)
Ln=αn+(-1)n/αn, d'où L2n+1=α2n+1-1/α2n+1.
Donc le membre de gauche de l'égalité à démontrer est
S=n=0+(-1)n(αx)2n+1/(2n+1)-n=0+(-1)n(x/α)2n+1/(2n+1)=arctan(αx)-arctan(x/α).
D'où tan(S)=((αx)-(x/α))/(1+(αx)(x/α))=x/(1+x 2).
arctan(x/(1+x2)) et S ayant même tangente, arctan(x/(1+x2))=S+kπ, avec k dans Z : reste à prouver que pour
tout x tel que |x|<1 on a bien k=0.
Pour 1>x≥0,
g=arctan(x/(1+x2)) est dans [0;π/2[ ; de même arctan(αx) et arctan(x/α) sont dans [0;π/2[, donc leur différence,
soit S, est dans ]-π/2 ; π/2[.
Donc S+π est dans ]π/2 ; 3π/2[, donc g≠S+π ; de même g≠S+kπ pour k≥1,
et S-π est dans ]-3π/2 ; -π/2[, donc g≠S-π ; de même g≠S+kπ pour k≤-1.
Donc pour 1>x≥0, on a S=arctan(x/(1+x2)) et comme ces deux expressions sont impaires, elles sont égales
pour tout x tel que |x|<1.
5) 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 n=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=k=6+Fk/10k+1 à
0,011235=k=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.
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.
Exercice 6
1) On utilise la formule de Binet : un=an+bn, avec a=(-u0+u1)/5 et b=(u0-u1)/5.
(un)2=a22n+b22n+2ab(-1)n, car =-1.
un-1un+1=a22n+b22n+abn-1n+1+ abn+1n-1, d'où
(un)2-un-1un+1=2ab(-1)n-ab()n-1(2+2) ; mais 2+2=(+)2-2=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.
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 L n-1 et Ln. Cependant ils sont bien premiers entre eux, cf exercice 1.
3) Fn=(1/5)(n-n) donne
(Fn)2+(Fn+1)2=(1/5)(2n+ 2n-2()n+ 2n+2+2n+2-2()n+1)
=(1/5)(2n(1+2)+ 2n(1+2))=(1/5)(2n (2+)+2n(2+)),
=(1/5)(2n(5+5)/2+2n(5-5)/2)=1/(5)(2n(5+1)/2+2n(5-1)/2)
=(1/5) (2n+1-2n+1)=F2n+1.
Par exemple (F3)2+(F4)2=F7, ce qu'on vérifie puisque F3=2, F4=3 et F7=13.
Page 54 sur 84
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.
(Ln)2=2n+2n+2()n=L2n+2(-1)n
(Fn)2=(1/5)(2n+2n-2()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).
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é.
• la relation est vraie pour p=1 (car Fn+1=Fn+1) et pour p=2 (car Fn+2=Fn+1+Fn)
• supposons la relation vraie pour 1,2,...,p (avec p2) :
Fn+p+1=Fn+p+Fn+p-1=(Fn+1Fp+FnFp-1)+(Fn+1Fp-1+FnFp-2), cela par application de l'hypothèse de récurrence.
Fn+p+1=(Fp+Fp-1)Fn+1+(Fp-1+Fp-2)Fn=Fn+1Fp+1+FnFp, et la relation est bien vraie au rang p+1.
12) Pour la relation d'Ocagne, on fixe p et on fait un récurrence sur n, à partir de n=p :
• c'est bien vrai pour n=p, car le membre de gauche est 0 qui est bien (-1)pFp-p
• supposons la formule vraie jusqu'au rang n (p) :
Fn+1Fp+1-FpFn+2= FnFp+1+Fn-1Fp+1-FpFn+1-FpFn
= (FnFp+1-FpFn+1)+(Fn-1Fp+1-FpFn)
=(-1)pFn-p+(-1)pFn-1-p=(1)pFn+1-p : la propriété est vraie au rang n+1.
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...
15) Les deux premières relations sont des applications immédiates de la formule de Binet :
FmLn+LmFn=(1/5)((m-m)(n+n)+(m+m)(n-n))=(1/5)(2m+n-2m+n)=2Fm+n
5FmFn+LmLn=(m-m)(n-n)+(m+m)(n+n))=2m+n+2m+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 :
Page 56 sur 84
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.
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/|2=2<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 n=kN (-1)n-1/(unun+1)=C(vk-VN+1) ; en faisant tendre N vers
+ on obtient
n=k+ (-1)n-1/(unun+1)=(1/((u0)2-(u1)2+u0u1))(uk+1/uk-).
1)b
Pour la suite (F), on a F0=0, F1=1, k=1 et ainsi n=1+ (-1)n-1/(FnFn+1)=-(F2/F1-)=-1.
Pour la suite (L), on a L0=2, L1=1, k=0 et ainsi n=0+ (-1)n-1/(LnLn+1)=(1/5)(L1/L0-)=(1-2)/10.
=1+1/(1+1/(1+1/(1+1/(1+1/(...))))
• P0/Q0=1/1
• P1/Q1=1+1/1=2/1
• P2/Q2=1+1/(1+1/1)=3/2
• P3/Q3=1+1/(1+1/(1+1/1))=5/3
• etc
• Pn=Pn-1+Pn-2
• Qn=Qn-1+Qn-2
Page 57 sur 84
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) =1+n=1+ (-1)n-1/(QnQn-1), et donc
=1+n=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 lorsque n tend vers +, cela en oscillant
autour de : comme Pn/Qn=Fn+2/Fn+1, on retrouve alors la remarque 2 de P5.1
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
k=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 e, avec e=2q, d'après le 3) de P5.1.
Ce qui donne bien k=1+ (F(2q))/(F(2q+k))=1/(e).
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
k=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,
k=1+ 1/(F(2k))=2-1/=2+=(5-5)/2
Exercice 9
1) Posons dn=(Fn+1)-(Fn+1+1). On a :
dn=(/5)(n-n)+-(1/5)(n+1-n+1)-1= (1/5)(-n-1+5+n+1-5) ; or =-1, donc
dn=(1/5)(5-5+n-1+n+1)=-1+(1/5)n-1(1+2).
Mais (1+2)/5=(2+)/5=(5-5)/(25)=-, ce qui donne
dn=--n, cela pour tout entier naturel n.
En fait, puisque 3=-0,23606..., et que ||<1, c'est que n3, on a |n|<0,237 et ainsi pour n3,
dn]--0,237;-+0,237[[0;1[.
Finalement pour n2, (Fn+1)=Fn+1+1+dn avec dn[0;1[ : donc E((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[.
• soit n est pair, donc Fn<n/5 (cf la formule de Binet et n>0) et ainsi n/5]Fn;Fn+0,28[
• soit n est impair, donc Fn>n/5 (cf la formule de Binet et n<0) et ainsi n/5]Fn-0,28;Fn[
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
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).
cela, en faisant une récurrence simultanée pour les deux relations et en utilisant la relation 10) de P8.
(*) donnera alors tout de suite l'implication nFn divise m => Fn2 divise Fm.
Et pour montrer l'implication réciproque, après avoir remarqué que n divise m, réutiliser (*), puis utiliser le 2)
de P8 pour conclure.
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
Page 60 sur 84
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.
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).
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).
• Cas 1 : si p=0 :
◦ pgcd(Ln,L0)=1 si 3 divise n
◦ pgcd(Ln,L0)=2 si 3 ne divise pas n
Note : n=pgcd(n,0), cf n≠0
• Cas 2 : si n≥p>0 et p divise n avec n/p impair :
pgcd(Ln,Lp)=Lp=Lpgcd(n,p)
• Cas 3 : si n≥p>0 et p ne divise pas n ou p divise n et n/p est pair (donc forcément, n>p) :
alors
pgcd(Ln,Lp)=pgcd(Lp,Ln1)
n et n1 ont même parité
Si p est pair (donc p≥2) de valuation v en 2 ( donc v≥1), cad p=2vp', p' impair, alors
n a pour valuation v en 2 <=> n1 a pour valuation v en 2
• preuve du cas 1
L0=2 et Ln est pair si et seulement si 3 divise n (voir question 6)c de l'exercice 1)
• preuve du cas 2
Cf Q2 de l'exercice 2, p|n et n/p impair entraîne que Lp divise Ln, donc pgcd(Ln,Lp)=Lp et p est
évidemment le pgcd de n et p.
• preuve du cas 3
n=q(2p)+r avec 0≤r≤2p-1.
Si 0≤r≤p-1, on prend n1=r , donc n1≡n (2p) avec 0≤n1≤p-1.
Si p≤r≤2p-1 on a 1≤2p-r≤p ; mais 2p-r=p implique r=p et donc n=(2q+1)p ce qui est contraire à
l'hypothèse.
Donc 1≤2p-r≤p-1 et alors on prend n1=2p-r, et on a n1≡-n (2p) avec 0≤n1≤p-1.
Cf la relation de congruence entre n1 et n, les diviseurs communs à n et p sont les diviseurs communs à
n1 et p, ce qui prouve que pgcd(n,p)=pgcd(n 1,p).
Et c'est toujours cette relation de congruence qui permet de dire, cf les relations établies ci-dessus, que
pgcd(Ln,Lp)=pgcd(Ln1,Lp).
Enfin cette relation n1≡±n (2p) prouve que n et n1 ont même parité.
Cas où p est pair, de valuation v(≥1) :
si n a aussi v comme valuation en 2, alors, évidemment (cf toujours la relation de congruence) 2v
divise n1, mais si 2v+1 divisait n1 alors, 2v+1 divisant 2×p, 2v+1 diviserait aussi n≡±n1 (2p), ce qui
est exclu, et donc n1 a aussi v comme valuation en 2.
De même, on montre que si n1 a aussi v (≥1) comme valuation en 2, n a aussi v comme valuation
en 2.
• on applique Lemme(n,p) :
si les cas 1 et 2 ne sont pas réalisés alors
il existe n1 tel que (notamment) 0≤n1<p avec
pgcd(n,p)=pgcd(p,n1) et pgcd(Ln,Lp)=pgcd(Lp,Ln1)
• on applique Lemme(p,n1) :
si les cas 1 et 2 ne sont pas réalisés alors
il existe p1 tel que (notamment) 0≤p1<n1 avec
pgcd(p,n1)=pgcd(n1,p1) et pgcd(Lp,Ln1)=pgcd(Ln1,Lp1)
• on applique lemme(n1,p1) :
etc
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>n 1>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=2 an' et p=2bp' avec a,
b, n', m' entiers naturels, n' et m' impairs.
• Si on arrive au cas 2, c'est que pgcd(Ln,Lp)=pgcd(Lk',Lk), avec k'≥k>0 et k divise k' avec k'/k impair,
donc k et k' ont la même parité.
Alors
◦ soit k et k' sont impairs, et vu que la parité pour les arguments du lemme se conserve au cours du
lemme (lorsqu'on passe par le cas 3), c'est que n et p sont impairs, donc a=b=0
◦ soit k et k' sont pairs, avec la même valuation (≥1) en 2, et vu que cette valuation en 2 pour les
arguments du lemme se conserve au cours du lemme (lorsqu'on passe par le cas 3), c'est que n et p
ont même valuation en 2 : a=b≥1
Donc, si on arrive au cas 2, c'est que a=b.
• Si a=b
◦ soit a=b=0, donc n et p sont impairs, donc au cours des applications successives du lemme (qui
passent toutes par le cas 3, avant la dernière arrivant au cas 1 ou au cas 2) les arguments du lemme
vont rester impairs, donc aucun ne sera nul, et on ne pourra arriver au cas 1
◦ soit a=b≥1, donc n et p ont même valuation v=a=b (≥1) en 2, donc au cours des applications
successives du lemme (qui passent toutes par le cas 3, avant la dernière arrivant au cas 1 ou au cas
2) les arguments du lemme vont garder cette valuation v, donc seront toujours ≥2 et on ne pourra
arriver au cas 1
Donc, a=b implique que l'on arrive au cas 2.
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
Conséquences :
1) pour n≥1 et p≥1,
Page 63 sur 84
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(L n,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.
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.
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.
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.
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
Page 64 sur 84
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)
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 :
• la relation Fn+1Ln-FnLn+1=2(-1)n, cf 12) de P8, montre aussi tout de suite que tout diviseur commun à Fn
et à Ln divise 2.
• ou, cf P7, pgcd(Fn,Ln)=pgcd(Fn,2Fn+1-Fn)=pgcd(Fn,2Fn+1) ;
or Fn et Fn+1 sont premiers entre eux, donc il existe u et v (dans Z) tels que uFn+ vFn+1=1 (Bezout), et en
multipliant par 2 on voit que pgcd(Fn,Ln) divise 2 donc est égal à 1 ou 2.
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 :
Deux exemples (k=2, k=3 ont été vus au début de cette preuve)
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.
a=bq1+r2, 0r2<b
b=r2q2+r3, 0r3<r2
Page 66 sur 84
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 :
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 F n+1 et Fn+2 (n
entier naturel non nul) se fait exactement en n itérations : 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 n, Fnn-2
(voir question 6 de l'exercice 1), on obtient nlna/ln et nlnb/ln+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é.
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.
• soit F(n1), le plus grand terme de (F), autre que F0 et que F1, tel que F(n1)e ; on a évidemment n12
Note : l'existence de ce plus grand terme ne pose pas de problème, puisque e1 et F2=1.
si e=F(n1), on a obtenu une Z_somme de e et c'est fini
sinon, n14, en effet :
◦ si n1=2, alors c'est que F2=1 est le plus grand terme de (F) qui soit e, donc e=1 et alors F(n1)=e,
ce qui est exclu
◦ si n1=3, alors c'est que F3=2 est le plus grand terme de (F) qui soit e, donc e=2 et alors F(n1)=e,
ce qui est exclu
• soit F(n2), le plus grand terme de (F), autre que F0 et que F1, tel que F(n2)e-F(n1) ; on a évidemment
n22, mais aussi F(n2)F(n1-2), cad F(n2) et F(n1) ne sont pas consécutifs :
en effet, si on avait F(n2)>F(n1-2), alors on aurait n2>n1-2 (puisque la suite F est strictement croissante à
partir du rang 2 et n1-2 et n2 sont 2 ), donc n2n1-1, et ainsi F(n2)F(n1-1) ;
donc eF(n2)+F(n1)F(n1)+F(n1-1)=F(n1+1)>F(n1) et ainsi F(n1) ne serait pas le plus grand terme de (F)
qui soit e
si e=F(n1)+F(n2) on a obtenu une Z_somme de e et c'est fini
sinon, n24, en effet :
◦ si n2=2, alors c'est que F2=1 est le plus grand terme de (F) qui soit e-F(n1), donc e-F(n1)=1 et
alors F(n2)=e-F(n1), ce qui est exclu
◦ si n1=3, alors c'est que F3=2 est le plus grand terme de (F) qui soit e-F(n1), donc e-F(n1)=2 et
alors F(n2)=e-F(n1), ce qui est exclu
• soit F(n3), le plus grand terme de (F), autre que F0 et que F1, tel que F(n3)e-F(n1)-F(n2) ; on a
évidemment n32, mais aussi F(n3)F(n2-2), cad F(n3) et F(n2) ne sont pas consécutifs :
en effet, si on avait F(n3)>F(n2-2), alors on aurait n3>n2-2 (puisque la suite F est strictement croissante à
partir du rang 2 et et n2-2 et n3 sont 2), donc n3n2-1 et ainsi F(n3)F(n2-1) ;
donc e-F(n1)F(n3)+F(n2)F(n2)+F(n2-1)=F(n2+1)>F(n2) et ainsi F(n2) ne serait pas le plus grand terme
de (F) qui soit e-F(n1)
Mais on a aussi F(n3) et F(n1) qui ne sont pas consécutifs puisque F(n2)F(n1-2), F(n3)F(n2-2) et F
(n2-2)<F(n2), ce qui fait que F(n3)<F(n1-2).
si e=F(n1)+F(n2)+F(n3) on a obtenu une Z_somme de e et c'est fini
sinon
"etc"
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.
◦ si j=2, S ne peut contenir que F2=1, soit S=F2<F3 : la propriété est vraie pour j=2.
Page 68 sur 84
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
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
Page 69 sur 84
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
• pour p et q 4,
(2Fp)*(3Fq)=(Fp-2+Fp+1)*(Fq-2+Fq+2)
=Fp+q-4+Fp+q+Fp+q-1+Fp+q+3
=Fp+q-4+Fp+q+1+Fp+q+3=6Fp+q=6(Fp*Fq)
• pour p4, q6,
(3Fp)*(5Fq)=(Fp-2+Fp+2)*(Fq-4+Fq-1+Fq+3)
=Fp+q-6+Fp+q-3+Fp+q+1+Fp+q-2+Fp+q+1+Fp+q+5 ;
mais 2Fp+q+1=Fp+q-1+Fp+q+2 et Fp+q-1+Fp+q-2=Fp+q, et donc
(3Fp)*(5Fq)=Fp+q-6+Fp+q-3+Fp+q+Fp+q+2+Fp+q+5=15Fp+q=15(Fp*Fq)
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)
Montrons maintenant que la suite (F') est périodique à partir du rang 0, ce k en étant une période,
c'est-à-dire pour tout entier n≥0 on a F'n+k=F'n :
Remarque : voici une autre preuve du fait qu'il existe k dans N * tel que F'k=0 et F'k+1=1 (ce qui équivaut
à pour tout n dans N, on a F'n+k=F'n).
On a vu à la remarque 2 de l'énoncé (suivi de la preuve) de P4, que si A est la matrice symétrique
01
A=
11
alors (cela se retrouve tout de suite par une récurrence immédiate)
Fk-1 Fk
Ak =
Fk Fk+1
En fait A peut être considérée comme un élément de l'anneau M(2,m) des matrices 2×2 à coefficients
dans Z/mZ ; anneau de cardinal m4.
Dans cet anneau on a alors
F'k+1-F'k F'k
Ak =
F'k F'k+1
A est donc dans le groupe U(M(2,m)) des éléments inversibles de M(2,m), groupe fini et ainsi A a un
ordre k : c'est-à-dire il existe un plus petit k dans N* tel que Ak=I (matrice identité 2×2).
L'écriture de Ak montre clairement que Ak=I F'k=0 et F'k+1=1, et donc l'ordre de A est le plus petit k
tel que F'k=0 et F'k+1=1 : c'est donc (voir le d) ci-dessus) k(m)!
On en déduit que k(m)2 (puisque AI) et surtout que k(m) divise card(U(M(2,m))).
• e) La 1ière équivalence a été prouvée ci-dessus.
Montrons maintenant, k étant dans N*, que l'on a l'équivalence suivante : pour tout dans N, F'n+k=F'n k
(m) divise k.
Si k=qk(m) (q entier naturel non nul) on a évidemment F'n+k=F'n pour tout n dans N.
Réciroquement, supposons que F'n+k=F'n pour tout n dans N, avec k entier naturel non nul.
La division euclidienne donne k=qk(m)+r avec 0r<k(m), et donc pour tout entier naturel n on a
F'n+qk(m)+r=F'n, soit F'n+r=F'n, et donc si r0, r est une période de (F') qui est <k(m), ce qui est en
contradiction avec la définition de k(m).
Donc r=0, cad k(m) divise k.
• f) Puisque k(m) est la période de (F'), pour tout n dans N, F'qk(m)=F'0 ; mais F'0=0 et donc pour tout q
dans N, F'qk(m)=0, soit Fqk(m) est nul modulo m, donc m divise Fqk(m).
Autre façon : m divise Fk(m) (puisque F'k(m)=0), et par ailleurs (voir P10) pgcd(Fqk(m),Fk(m))=Fpgcd(qk(m),k
(m))=Fk(m), donc m divise Fqk(m)
• h) :
si p=2, c'est évident car 2 divise F3=2 et g(2)=3≤3
si p≠2, alors p étant premier impair distinct de 5, d'après P5.2.2, p divise effectivement Fp-1 ou Fp+1,
selon que 5 soit un carré modulo p ou pas.
2)
multiple de M.
De g(pin_i) divise M, cad M=qg(pin_i) on tire (d'après P13.1.g) FM0 (pin_i), donc FM0 (m),
puisque les pin_i sont premiers entre eux, et d'après P13.1.g, M est un multiple de g(m), et comme
g(m) est un multiple de M, on a g(m)=M.
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).
Les deux congruences ci-dessus sont bien encore vraies si on remplace e par e+1.
Donc, voir 1e de P13, k(2e+1) divise 3×2e ; et, voir 2b de P13, k(2e) divisant k(2e+1), c'est que
3×2e-1 divise k(2e+1).
Ceci entraîne que k(2e+1)=q×3×2e-1 et 3×2e=q'k(2e+1) avec q et q' dans N, d'où
3×2e=qq'×3×2e-1, soit qq'=2 et q=1 ou 2 ; donc k(2e+1)=3×2e-1 ou k(2e+1)=3×2e.
Mais si k(2e+1) était égal à 3×2e-1, cf 1.d de P13, on aurait F(3×2e-1+1)1 (2e+1) ; or e2,
donc e+13 et cf Q1, F(3×2e-1+1)1+2e (2e+1), donc contradiction puisque 1 et 1+2e ne sont
pas égaux modulo 2e+1.
La seule possibilité est donc k(2e+1)=3×2e, et la relation est vraie pour e+1.
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() est supposé non nul) :
n étant cette fois dans N*, on en déduit que si sin((n+1))=0 (et n'étant pas un multiple de ), alors
Un(cos())=0 et donc pour tout k dans Z (exceptés les multiples de n+1) on a U n(cos(k/(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(/(n+1)), cos(2/(n+1)),..., cos(n/(n+1)), racines qui sont distinctes
(puisque /(n+1), 2/(n+1), ..., n/(n+1) sont n nombres distincts dans [0;]).
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)=2nk=1 n(X-cos(k/(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) ; en
fait puisque W0=1=F1 et W1=i×2(-i/2)=1=F2, c'est que pour tout n≥0, on a Wn=Fn+1 (voir P3).
3) Puisque pour tout entier naturel n, on a Wn=Fn+1 (voir Q2), c'est que pour n1,
Fn+1=inUn(-i/2)=in×2n×k=1 n(-i/2-cos(k/(n+1)) ,
d'où pour n2, Fn=(-i)n-1k=1 n-1(2cos(k/n)+i).
Il suffit alors de passer au module-carré pour obtenir que pour tout n2 (Fn)2=k=1 n-1(1+4cos2(k/n)).
3) La formule cos2()=(1+cos(2))/2 donne tout de suite, pour tout n2, (Fn)2=k=1 n-1(3+2cos(2k/n))
En posant k=2k/n, on a cos(k)=cos(n-k), d'où
◦ si n est pair ( pour n=2, le produit ne contient qu'un seul terme : 3+2cos(2/2)=1 ; on se limitera
donc au cas n4)
cos(1)=cos(n-1), cos(2)=cos(n-2),..., cos(n/2-1)=cos(n-(n/2-1))=cos(n/2+1) ; cette fois, "entre" cos
(n/2-1) et cos(n/2+1) il manque cos(n/2), mais cos(n/2)=cos()=-1 et 3+2cos(cos(n/2)=1,
et donc, Fn=k=1 n/2-1(3+2cos(2k/n))
L4=(3+2cos(/4))(3+2cos(3/4))=(3+2cos(/4))(3-2cos(/4))=9-2=7.
L6=(3+2cos(/6))(3+2cos(3/6))(3+2cos(5/6))=(3+2cos(/6))×3×(3-2cos(/6))=3×(9-3)=18.
Exercice 18
◦ p2()=9+8cos()+6cos(2)+2cos(3)
◦ p3()=29+30cos()+26cos(2)+24cos(3)+8cos(4)+6cos(5)+2cos(6)
◦ p4()=95+120cos()+106cos(2)+102cos(3)+82cos(4)+48cos(5)
+32cos(6)+24cos(7)+8cos(8)+6cos(9)+2cos(10)
A=p2(2/5)=9+8cos(2/5)+6cos(4/5)+2cos(6/5)
Les racines 5ièmes de 1 sont 1, ei2/5, ei4/5, ei6/5 (conjuguée de ei4/5), ei8/5 (conjuguée de ei2/5) et
leur somme est 0, donc
◾ cos(4/5)=cos(6/5), ce qui donne A=9+8cos(2/5)+8cos(4/5)
◾ 1+2cos(2/5)+2cos(4/5)=0, ce qui donne A=9-4=5
Comme F5=5, on a bien F5=A.
Notons A=k=1 E((7-1)/2)(3+2cos(2k/7) et vérifions que l'on a bien F7=A
A=p3(2/7)=29+30cos(2/7)+26cos(4/7)+24cos(6/7)+8cos(8/7)+6cos(10/7)+2cos(12/7)
Les racines 7ièmes de 1 sont 1, ei2/7, ei4/7, ei6/7, ei8/7 (conjuguée de ei6/7) ei10/7 (conjuguée de
ei4/7), ei12/7 (conjuguée de ei2/7), et leur somme est 0, donc
◾ cos(2/7)=cos(12/7), cos(4/7)=cos(10/7), cos(6/7)=cos(8/7), ce qui donne
A=29+32cos(2/7)+32cos(4/7)+32cos(6/7)
Page 75 sur 84
Exercice 19
◦ Fkn=(1/2k-1)(02j+1kCk2j+1 5jFn2j+1Lnk-2j-1)
◦ Lkn=(1/2k-1)(02jkCk2j 5jFn2jLnk-2j)
Note : cette formule a déjà été utilisée lors de la question 2 de l'exercice 2.
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)(02jkCk2j 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, L 2n=(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 :
◾ si k=2p
E(k/2)=p et 1+E((k-1)/2)=1+E(p-1/2)=p
Rk+1,n(X)=(Ck0 +Ck-1-1 )Xk+1
+∑r=1E((k+1)/2)((Ck-rr +Ck-rr-1 )+(Ck-r-1r-1 +Ck-r-1r-2 ))(-1)r(n+1)Xk+1-2r
Page 76 sur 84
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
◦ 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)=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 5X 2+4(-1)n pour l'un et
X2+4(-1)n+1 pour l'autre.
Q2k+1,n(X)=(1/22k)(0jkC2k+12j+1 5jX2j+1(5X2+4(-1)n)k-j)
R2k+1,n(X)=(1/22k)(02j2k+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)(0j'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)(0jkC2k+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.
Page 77 sur 84
Pour obtenir les coefficients ak,r intervenant dans Q2k,n il n'y a plus qu'à identifier.
◦ l'identification des termes de degré 2k+1 donne 5×5k+1×ak,0=βk,-15k, soit ak,0=1 et le coefficient de
X2k-1 de Q2k,n est 5k.
◦ l'identification des termes de degré 1 donne 4(-1)n(-1)(k-1)n50ak,k-1=(-1)kn50βk,k-1, soit 4ak,k-1=βk,k-1.
Mais βk,k-1=Ck+1k +2Ckk-1 +Ck-1k-2 =k+1+2k+k-1=4k d'où ak,k-1=k et le coefficient de X dans Q2n,k
est (-1)(k-1)nk.
◦ Et pour les termes de degrés intermédiaires cad 2k-1-2r pour r=0, 1,..., k-2, on obtient
5(-1)(r+1)n5k-(r+1)-1ak,r+1+4(-1)n(-1)rn5k-r-1ak,r=βk,r(-1)(r+1)n5k-r-1, ce qui donne
ak,r+1=βk,r-4ak,r.
Remarquons que cette relation de récurrence permet de retrouver tout de suite que tous les ak,r sont
entiers puisque par ailleurs ak,0=1.
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)
◦ c'est vrai pour r=0, cf on a vu que ak,0=1
◦ c'est vrai pour r=1, car en faisant r=0 dans ak,r+1=βk,r-4ak,r, on obtient ak,1=2k+2-4=C2k-21
◦ supposons que pour r≥1 on ait effectivement ak,r=C2k-r-1r.
Alors, ak,r+1=((4k2+2k-2r-2)/((r+1)r))C2k-r-2r-1 -4C2k-r-1r
ak,r+1=((4k2+2k-2r-2)/((r+1)r))-4(2k-r-1)/r)C2k-r-2r-1
ak,r+1=((4k2-(8r+6)k+4r2+6r+2)/((r+1)r))C2k-r-2r-1
le discriminant du numérateur de la fraction ci-dessus est 4, donc ses racines sont (2r+1)/2 et r+1,
d'où
ak,r+1=C2k-r-2r-1 (2k-2r-1)(2k-2r-2)/((r+1)r)=C2k-r-2r+1 =C2k-(r+1)-1r+1, et la formule est bien vraie au
rang r+1.
Donc pour tout r tel que 0≤r≤k-1, on a ak,r=C2k-r-1r
On retrouve bien ak,k-1=Ckk-1 =k trouvé par identification directe des termes en X (voir plus haut).
Page 78 sur 84
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+1=βk,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
D'après le 2) de P15, pour k impair (donc ≥1), Qk,n est impair et de degré k et son coefficient de X est, au
signe près, k.
Comme (voir toujours le 2) de P15), pour k impair on a Fkn=Qk,n(Fn), c'est que
Fkn=eFn3+±kFn, avec e un entier (dépendant de n).
D'où, si pour p≥1, kp divise Fn, alors
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, iIaiFn+ik=Fkn.
Compte-tenu de la formule de Binet, cette relation s'écrit
(kn-kn)/51/2=5-k/2iIai(d=0;k(-1)dCkd (k-dd)n+i).
Pour cela il suffit que les trois conditions suivantes soient réunies :
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(2)=2-2=51/2F2=51/2
P2(2)=2-2=-51/2
P2()=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(2)=F(2)=1, les conditions C1, C2, C3 restant manifestement vérifiées.
Par exemple si on prend F(X)=1+(X-2)(X-2)=1+X2-L2X+()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)=d=1,k-1(X-k-dd). : Pk vérifie la condition C6 si les k-1 zéros de
Uk sont zéros de Pk.
Exemples :
◦ Pour k pair, k=2p, détermination "d'une" fonction rationnelle Pk vérifiant les conditions C4,
C5, C6
Si k=2, on a trouvé ci-dessus une possibilité pour P2 : on supposera donc maintenant k4.
Uk(X)=(X-(-1)k/2)i=1,p-1(X-k-ii)(X-ik-i)
Uk(X)=(X-(-1)k/2)Xp-1i=1,p-1(X+1/X-(-1)iLk-2i), car cette fois (-1)k=1.
Uk(X) et Vk=(X-(-1)k/2)i=1,p-1(X+1/X-(-1)iLk-2i) ayant les mêmes 2p-1=k-1 zéros, Pk vérifiera C6
si Pk=T×Vk, avec T polynôme.
C4 et C5 seront vérifiées si en outre T(k)Vk(k)=-T(k)Vk(k)=5(k-1)/2
Or, puisque Lk=k+k=k+(-1/)k=k+1/k=k+(-1/)k=k+1/k, on a Vk(k)/(k-(-1)k/2)=Vk(k)/
(k-(-1)k/2)=i=1,p-1(Lk-(-1)iLk-2i) : cette valeur commune sera notée wk
Il faut donc que T(k)(k-(-1)k/2)wk=-T(k)(k-(-1)k/2)wk=5(k-1)/2.
Ceci implique que par T(X)(X-(-1)k/2) les images de k et k sont opposées. Or c'est le cas de
X-1/X (car ici k est pair, donc k=1/k et alors k-1/k=-(k-1/k).
D'où l'idée de prendre T tel que T(X)(X-(-1)k/2)=c(X-1/X), avec c une constante réelle.
C4 et C5 seront alors vérifiées si c(k-1/k)=5(k-1)/2/wk, soit c=5k/2-1/(Fkwk).
Donc pour k pair, k4, un choix possible de Pk est
Pk=(5k/2-1/(Fkwk))(X-1/X)i=1,p-1(X+1/X-(-1)iLk-2i).
Exemples :
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 :
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-L n/2)(x+Ln/2)|≥4, d'où contradiction.
Donc si n est pair, Ln n'est pas 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.
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.
Page 82 sur 84
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.
cas n impair
Si Ln est impair, évidemment il n'est pas 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 L k, 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
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
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
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
Page 84 sur 84
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 x 2=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
◾ soit c'est un pi qui est égal à 2, et Y=2y2 et Z=z2, avec y et z dans N (et premiers entre eux),
donc Ln/2=(2y)2 et cf le théorème 1, cela équivaut à n/2=1 ou n/2=3 ; cf on est dans le cas 3
divise n/2, la seule possibilité est n=6, qui convient effectivement car F6=8 est le double
d'un carré.
◾ soit c'est un qi qui est égal à 2 et Y=y2 et Z=2z2 avec y et z dans N, donc Ln/2=2y2 et cf le
théorème 2, n/2=0 ou n/2=±6, soit n=0 ou n=±12 : dans les trois cas on a bien 3 divise n/2.
Réciproquement, F0=0 est le double d'un carré, mais F-12 et F12 qui sont égaux à 144 ne sont
pas le double d'un carré.
Bien entendu, dans ce cas on pouvait utiliser l'aspect Z=2z2 qui donne Fn/2=(2z)2, ce qui
équivaut, cf le th 3, à n/2 =0 ou ±1 ou 2 ou 12 ; comme 3 divise n/2, les seules possibilités
sont n=0 qui convient et n=24 qui ne convient pas : F24=F12L12=144×322=25×32×7×23.
Donc pour n pair et 3 divise n/2, Fn=2x2 uniquement pour n=0 et n=6 : F0=0, F6=8
◾ le 1er cas, cf le th 2, entraîne que n/2=0 ou ±6 : or 3 ne divise pas n/2, donc aucune valeur
de n ne convient dans ce cas
◾ le 2ième cas, cf le th 1, entraîne que n/2=1 ou 3 ; comme 3 ne divise pas n/2, la seule
possibilité est n=2 qui ne convient pas car F2=1≠2x2
Donc pour n pair et 3 ne divise pas n/2, Fn n'est pas le double d'un carré.