Successione di Fibonacci
Successione di Fibonacci
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....
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....
-
- 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
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...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??
Comunque conoscendo n si può fare tutto, ma questo è un fatto che tu conosci già vero?
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} $
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} $
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.
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.
mmm....EvaristeG ha scritto:Allora ... se la derivazione della formula è corretta, probabilmente hai sbagliato tu i conti con excel...
è 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...
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 ...
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 ...
Re: Successione di Fibonacci
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....
$ F_n=F_{2n}\sqrt{\frac{1}{2+\sqrt{5F_{2n}^2+4}}} $
quella per $ n $ dispari non mi viene ancora....
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...
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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]