Upload
ngomien
View
213
Download
0
Embed Size (px)
Citation preview
Fibonacciou comment se faufiler à travers les marteaux-pilons
Jean-François Burnol, 26 mars 2011
Cher Hervé,je reprends au bond ton approche aux propriétés de divisibilité des
nombres de Fibonacci. Évidemment un minimum de théorie des corpsde nombres algébriques et de théorie de Galois rendrait tout cela asseztransparent mais je vais tenter une approche un peu sur le côté. Tu asdéfini :
α =1 +√5
2
β =1 –√5
2
Il est utile d’introduire la matrice
A =
(
0 1
1 1
)
En effet α et β en sont les valeurs propres, α +β = 1 = Tr A et αβ = –1 = det A.Le THÉORÈME DE CAYLEY-HAMILTON affirme que
A2 – (TrA)A + (det A)I = A2 – A – I = 0 ,
et ce marteau-pilon-écrase-mouche sera rapidement confirmé par le cal-culateur intrépide. Autrement dit
A2 = A + I,donc : An+2 = An+1 + An
ce qui ressemble assez furieusement à la récurrence de Fibonacci, surtoutsi on passe aux traces :
Tr An+2 = Tr An+1 + Tr An
Donc la suite (tn = Tr An) vérifie la même récurrence que la suite de Fibo-nacci. Calculons les premières valeurs :
A2 =
(
1 1
1 2
)
, A3 =
(
1 2
2 3
)
, A4 =
(
2 3
3 5
)
, A5 =
(
3 5
5 8
)
, A6 =
(
5 8
8 13
)
, . . .
1
C’est assez clair ! on a, et la preuve par récurrence est immédiate, atten-tion seulement aux indices : 1
An =
(
Fn–1 FnFn Fn+1
)
, donc tn = Fn–1 + Fn+1 = αn + βn
On voit ainsi que les quantités symétriques αn + βn sont des nombres en-tiers, ce qui suffit pour ton texte.
En effet tu y considérais, avec un certain d ≥ 0 :∑
0≤j≤p
(αd)j(βd)p–j
Supposons j < 12p, alors on combine le terme avec j et celui avec p – j ce qui
donne
αdjβd(p–j) + αd(p–j)βdj = αdjβdj(
(βd)p–2j + (αd)p–2j)
= ±td(p–2j) ∈ Z
Et si p est pair, le terme avec j = 12p vaut ±1. Donc ta somme qui represen-
tait un quotient de nombres de Fibonacci est bien un nombre entier.Cela dit en passant, cette somme a aussi une interprétation d’algèbre
linéaire. D’abord on forme Ad et ensuite on doit prendre son produit ten-soriel symétrique p fois avec elle-même : il s’agit de transférer l’actionnaturelle de la matrice Ad sur les formes linéaires homogènes uX + vY (es-pace de dimension 2) à l’action sur les polynômes homogènes de degré p :u0X
p + u1Xp–1Y + · · · + upYp (espace de dimension p + 1). Mais bon je deviens
trop marteau-pilon là (pas pour Hervé, mais pour les innocents agrégatifstout terrorisés.)
J’en viens maintenant à l’affirmation
(Fn , Fm) = F(n,m) [A]
Cela ressemble fort à un théorème que nous avons vu dans nos leçonsd’algèbre, à propos des polynômes cyclotomiques :
(Xn , Xm) = X(n,m) avec Xn = Xn – 1 [B]
Comme de plus
Fn =αn – βn
α – β
1. pour que la formule soit valable pour n = 0 on posera F–1 = 1.
2
j’ai pensé qu’on pourrait essayer de s’inspirer de [B] pour prouver [A]. Ilsuffit de montrer :
n > m =⇒ (Fn , Fm) = (Fn–m , Fm)
car on fait alors une récurrence (généralisée) sur la hauteur n + m (ou surmax(n,m)). Écrivons pour cela, comme dans la preuve de [B] :
αn – βn = (αm – βm)αn–m + βm(αn–m – βn–m)
Cela donne :Fn = α
n–mFm + βmFn–m [C]
Si maintenant d > 0 est un entier qui divise à la fois Fm et Fn–m il enrésulte que 1
dFn ∈ Z[α,β] = Z[α, 1 – α] = Z[α] est un polynôme à coefficients
entiers en α. Mais comme α2 = α + 1, il existe par récurrence pour tout nune expression αn = un + vnα, avec un, vn ∈ Z. En fait, il faut :
(
un+1vn+1
)
=
(
0 1
1 1
) (
unvn
)
c’est-à-dire, en fait :(
unvn
)
= An(
u0v0
)
=
(
Fn–1 FnFn Fn+1
) (
1
0
)
=
(
Fn–1Fn
)
Au final nous voyons que 1dFn admet une écriture λ + μα avec λ, μ ∈ Z. Si
l’on avait μ , 0 on pourrait en déduire :
α ∈ Q,donc aussi :√5 ∈ Q
Or cela est faux ! Donc μ = 0, donc d divise Fn !Ainsi tout diviseur d commun à Fm et Fn–m divise Fn. Et par ailleurs en
écrivant [C] sous la forme équivalente :
αmFn – αnFm = (–1)mFn–m [D]
on peut faire le même raisonnement avec un entier d divisant à la fois Fnet Fm. Nécessairement cet entier divise aussi Fn–m.
Conclusion : (Fn , Fm) = (Fn–m , Fm), et ensuite [A] par récurrence. J’ai en-vie de revenir un peu en arrière pour commenter et exploiter un peu plusnos relations (la deuxième se prouvant comme la première) :
αn = Fn–1 + Fnα
3
βn = Fn–1 + Fnβ
Il est bien clair que comme on savait déjà Fn–1+Fn+1 = αn+βn, et que Hervé
nous avait dit que αFn –βFn = αn –βn on doit pouvoir en éliminant βn par lasomme des deux confirmer le résultat. Voyons : Fn–1+(Fn+Fn–1)+(2α–1)Fn =2αn. Humm. . . ça marche !
Bon au final notre formule magique [C] peut aussi s’écrire :
Fn = (Fn–m–1 + αFn–m)Fm + (Fm–1 + Fm(1 – α))Fn–m
soit, en regroupant les termes (et avec Fm–1 + Fm = Fm+1) :
Fn = Fn–m–1Fm + Fm+1Fn–m + α(Fn–mFm – FmFn–m)
ah ? eh bien la nature est bien faite !
Fn = Fn–m–1Fm + Fm+1Fn–m [E]
Ahmais bien sûr c’était évident ! Je suis prêt à parier que vos livres favorisbalancent cette relation à la figure du taupin stupéfié ! Évidemment unefois qu’on a cela comme point de départ les choses deviennent faciles,plus besoin de passer par l’ouverture à des domaines mathématiques plusvastes !
Bon je suis peut-être mauvais joueur. Peut-être aurais-je dû avant deme lancer dans cette grande cavalcade avoir l’idée d’écrire
An = An–mAm(
Fn–1 FnFn Fn+1
)
=
(
Fn–m–1 Fn–mFn–m Fn–m+1
) (
Fm–1 FmFm Fm+1
)
On retrouve notre formule [E] (et une autre d’ailleurs mais en fait c’est lamême avec m remplacé par m + 1). Mais on avait aussi exprimé Fm vial’équation [D]. Est-ce que ça vaut le coup de recommencer les calculs ? jene crois pas, suffit de définir les Fn pour n < 0 en s’assurant que la formulepour An restera toujours valable. Comme α–1 = –β, β–1 = –α, il est clair qu’ilfaut poser F–n = (–1)n–1Fn. L’équation [E] sera alors valable pour tous les netm entiers relatifs. Il est bien clair que cette relation [E] ne peut que jouerun rôle crucial dans l’étude des propriétés des nombres de Fibonacci !
Références
[1] Hervé QUEFFÉLEC, Fibonacci et suites récurrentes, manuscrit, 25mars 2011.
4