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 $
Fibonacci & Mersenne - i misteri del MCD
Fibonacci & Mersenne - i misteri del MCD
Presidente della commissione EATO per le IGO
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
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 $
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 $
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
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.
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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Si, ci avevo pensato, ma non so perchè non mi piace, mi sembra di barareIl_Russo ha scritto:A questo punto si conclude applicando l'algoritmo euclideo per il MCD agli indici dei Fibonacci...darkcrystal ha scritto:$ mcd(F_k, F_h)= $ [...] $ =mcd(F_{k-h},F_h) $
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
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!
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!
"Sei la Barbara della situazione!" (Tap)