OliForum Matematico

Tutti noi conosciamo la sequenza di Fibonacci: $ F_0 = 0 $, $ F_1 = 1 $, $ F_n = F_{n-1}+F_{n-2} $ per gli n interi maggiori o uguali a 2.

Dimostrare che $ MCD(F_h, F_k) = F_{MCD(h,k)} $ per ogni coppia h, k di interi non negativi, o, se volete fare gli sboroni, che la sequenza di Fibonacci è una sequenza di Mersenne.

Buon $ lavoro^3 $

LEMMA. $ mcd(F_n,F_{n-1})=1 $.

Per applicazione della definizione: $ mcd(F_n,F_{n-1})=mcd(F_{n-1}+F_{n-2},F_{n-1})=mcd(F_{n-1},F_{n-2})= $$ ...=mcd(F_2,F_1)=1 $.


Si dimostra facilmente che per ogni coppia di interi non negativi k,a si ha $ F_k=F_a F_{k-a+1} + F_{a-1} F_{k-a} $ (volendo non pensare, si sostituisce la formula chiusa e si fanno i - modesti - conti)

Allora $ mcd(F_k, F_h)=mcd(F_h F_{k-h+1}+F_{h-1}F_{k-h},F_h)= $$ mcd(F_{h-1}F_{k-h},F_h) $. D'altra parte abbiamo visto che due fibonacci consecutivi sono coprimi, dunque $ =mcd(F_{k-h},F_h) $.

Adesso supponiamo wlog $ k \geq h $.
Procediamo quindi per induzione: per k=1 o 2 la tesi è banale; supponendo di averla provata fino a k, dimostriamola per k+1. Sia r il rappresentante privilegiato di k+1 modulo h. Allora per quanto dimostrato $ mcd(F_{k+1},F_h)=mcd(F_r,F_h)=mcd(F_h,F_r)= $$ F_{mcd(h,r)}=F_{mcd(k+1,h)} $ poichè $ k \geq h \geq r $ (se per caso h=k+1, la tesi è infatti immediatamente ovvia)

La cosa è quindi vera per induzione.

$ Ciao^3 $

darkcrystal ha scritto:$ mcd(F_k, F_h)= $ [...] $ =mcd(F_{k-h},F_h) $

A questo punto si conclude applicando l'algoritmo euclideo per il MCD agli indici dei Fibonacci...

Dimostrazione alternativa:

Lemma: Sia $ m $ un intero positivo dato e $ T $ il minimo intero positivo per cui $ m|F_T $. Allora $ T|h $ se e solo se $ m|F_h $.

E' quasi come dire che i Fibonacci modulo $ m $ sono periodici di periodo $ T $. [Perche' "quasi"? Chi vede la differenza?]

Se prendete $ m = (h,k) $, dimostrate che $ F_{(h,k)} | \left( F_h, F_k \right) $.

Se invece prendete $ m = \left( F_h, F_k \right) $, dimostrate che $ \left( F_h, F_k \right) | F_{(h,k)} $.[]

Lascio a voi i dettagli.

Il_Russo ha scritto:

darkcrystal ha scritto:$ mcd(F_k, F_h)= $ [...] $ =mcd(F_{k-h},F_h) $

A questo punto si conclude applicando l'algoritmo euclideo per il MCD agli indici dei Fibonacci...

Si, ci avevo pensato, ma non so perchè non mi piace, mi sembra di barare

Ma è un simpatico corollario di questo !!!

Oltre a fare spam, questo post serve principalmente a fare pubblicità a quel simpatico problema, che kirill (vista la sua voglia di $ \mbox{lavorare}^3 $) potrebbe anche provare a risolvere....

ciau!