Fibonacci - jf.burnol.free.frjf.burnol.free.fr/agregfibonacci.pdf · Fibonacci ou comment se...

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