Successione di Fibonacci

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Stex19
Messaggi: 139
Iscritto il: 26 mar 2008, 15:12
Località: Genova

Successione di Fibonacci

Messaggio da Stex19 »

salve.
Sto cercando di ricavare una formula tale che, dato un numero di fibonacci F(n), possa ricavare F(2n), anche se probabilmente esiste già una cosa del genere... :roll:

ma la domanda è questa:
è possibile che abbia trovato una formula che vada bene per ogni n<150 (per ora ho fatto calcoli fino a 150) tranne che per n=116 e n=147??


p.s. è il mio primo post, se ho sbagliato sezione scusate....
pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Re: Successione di Fibonacci

Messaggio da pic88 »

Stex19 ha scritto: ma la domanda è questa:
è possibile che abbia trovato una formula che vada bene per ogni n<150 (per ora ho fatto calcoli fino a 150) tranne che per n=116 e n=147??
Di sicuro esiste una funzione che fa quella roba lì, anche un polinomio di grado abbastanza alto lo può fare, quindi magari se dici la formula che hai trovato... :roll:

Comunque conoscendo n si può fare tutto, ma questo è un fatto che tu conosci già vero?
carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop »

Molto divertente...

Io sono arrivato a qualcosa del genere: $ \displaystyle F(2n) = F(n) \sqrt{5 F(n)^2 + 4 (-1)^n} $

L'idea di base è lavorare con la forma matriciale dei numeri di Fibonacci (http://en.wikipedia.org/wiki/Fibonacci_ ... atrix_form).
Data $ A=\left(\begin{array}{ccc}0&1\\1&1\end{array}\right) $
$ \left(\begin{array}{ccc}F(n)\\F(n+1)\end{array}\right)=A^n \left(\begin{array}{ccc}F(0)\\F(1)\end{array}\right)=A^n \left(\begin{array}{ccc}0\\1\end{array}\right) $
Da cui con qualche osservazione si può arrivare a :$ A^n=\left(\begin{array}{ccc}F(n-1)&F(n)\\F(n)&F(n+1)\end{array}\right) $
Facendo il denominatore ad entrambi i lati: $ (-1)^n=F(n+1)F(n-1)-F(n)^2 $ (nota come Identità di Cassini)

Possiamo anche scrivere:
$ A^{2n}=A^nA^n= $$ \left(\begin{array}{ccc}F(n-1)&F(n)\\F(n)&F(n+1)\end{array}\right)^2 $$ \displaystyle= $$ \left(\begin{array}{ccc}{F(n-1)^2+F(n)^2}&{F(n)F(n-1)+F(n)F(n+1)}\\{F(n)F(n-1)+F(n)F(n+1)}&{F(n)^2+F(n+1)^2}\end{array}\right) $

Quindi $ F(2n)=\left(\begin{array}{ccc}{F(n-1)^2+F(n)^2}\\{F(n)F(n-1)+F(n)F(n+1)}\\\end{array}\right)\left(\begin{array}{ccc}{0}\\{1}\end{array}\right) $$ =F(n)F(n-1)+F(n)F(n+1) $

Combinando quest'ultima espressione, l'identità di Cassini e la definizione di successione di Fibonacci $ \displaystyle F(n+1)=F(n)+F(n-1) $
si dovrebbe appunto ottenere $ F(2n) = F(n) \sqrt{5 F(n)^2 + 4 (-1)^n} $
Stex19
Messaggi: 139
Iscritto il: 26 mar 2008, 15:12
Località: Genova

Messaggio da Stex19 »

carlop ha scritto: $ F(2n) = F(n) \sqrt{5 F(n)^2 + 4 (-1)^n} $
è prprio quello che è venuto a me (facendo un altro ragionamento e dopo milardi di calcoli :oops: ), ma mi sembra che per alcune non si verifichi....
ho calcolato con excel le vari F(n) e F(2n) e per certivalori sembra diverso... :?
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG »

Allora ... se la derivazione della formula è corretta, probabilmente hai sbagliato tu i conti con excel...
Cmq altri due modi per arrivare in fondo sono questi:
1) $ F(n)=\dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}2\right)^n $$ -\dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}2\right)^n $
questo vale per ogni n ... ora, chiamiamo $ \phi=(1+\sqrt{5})/2 $ e notiamo che $ (1-\sqrt{5}/2=1-\phi=-1/\phi $; allora
$ F(2n)=\dfrac{\phi^{2n}-(-\phi)^{-2n}}{\sqrt{5}}= $$ \dfrac{(\phi^n-(-\phi)^{-n})(\phi^n+(-\phi)^{-n})}{\sqrt{5}} $
e da qui si portano avanti i conti.
2) Si può dimostrare per induzione che
$ F(n)=F(k)F(n-h)+F(h)F(n-k) $
per $ 1\leq h,k\leq n-1 $ e da qui si ritorna alla formula che carlop ricavava calcolando le iterate della matrice A.
Stex19
Messaggi: 139
Iscritto il: 26 mar 2008, 15:12
Località: Genova

Messaggio da Stex19 »

EvaristeG ha scritto:Allora ... se la derivazione della formula è corretta, probabilmente hai sbagliato tu i conti con excel...
mmm....
è possibile che a cifre elevate (es. cifre con fattori $ 10^{35} $) excel arrotondi alcuni valori??
cmq quello che mi interessava sapere era se quellaformula era giusta, visto che è 2 settimane che mi scervello per capire se è giusta o no... :roll:
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG »

eh beh ... sopra a 10^20 non credo che excel sia affidabile, senza impostazioni opportune.
Cmq ti ho offerto altri due metodi per arrivare a dimostrare quella formula ... prova a farlo in uno di questi o con quello suggerito da carlop ... così potrai riverificare la formula. Certo non ho voglia di mettermi a fare i conti ... :D
Stex19
Messaggi: 139
Iscritto il: 26 mar 2008, 15:12
Località: Genova

Re: Successione di Fibonacci

Messaggio da Stex19 »

ora ho trovato anche questa, però vale solo per $ n $ pari....

$ F_n=F_{2n}\sqrt{\frac{1}{2+\sqrt{5F_{2n}^2+4}}} $

quella per $ n $ dispari non mi viene ancora.... :?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

Il 99% dei programmi per computer (Excel incluso) lavora con numeri a doppia precisione, che vuol dire che l'accuratezza garantita su ogni singola operazione è di una parte su 10^16. Poi man mano che si fanno conti gli errori si accumulano e quindi l'accuratezza dei risultati peggiora. Se si fanno operazioni "pericolose", come sottrazioni tra due numeri molto vicini, va ancora peggio.
Se vuoi risultati esatti con un numero maggiore di cifre decimali, devi usare programmi specializzati come Mathematica o librerie specializzate come GNU GMP. Oppure programmare in Fortran, e tanti auguri ;)

Se la cosa vi interessa, poi, il problema di calcolare (in modo esatto!) un numero di Fibonacci "grande" nel modo più veloce possibile ha qualche sviluppo interessante...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Rispondi