Successione di Fibonacci

[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...

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]

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...

Comunque conoscendo n si può fare tutto, ma questo è un fatto che tu conosci già vero?

[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]

$ 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 ), 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]

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]

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...

[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 ...

[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]

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...