Successione di Fibonacci

Da Wikipedia, l'enciclopedia libera.

Il volo dei numeri di Mario Merz, un'installazione luminosa sulla Mole Antonelliana, rappresenta la successione di Fibonacci

La successione di Fibonacci è una sequenza di numeri interi naturali definibile assegnando i valori dei due primi termini, F₀:= 0 ed F₁:= 1, e chiedendo che per ogni successivo sia F_n := F_n-1 + F_n-2. Il termine F₀ viene aggiunto nel caso si voglia fare iniziare la successione con 0; storicamente il primo termine della successione è F₁:= 1.

La sequenza prende il nome dal matematico pisano del XIII secolo Leonardo Fibonacci e i termini di questa successione sono chiamati numeri di Fibonacci. L'intento di Fibonacci era quello di trovare una legge che descrivesse la crescita di una popolazione di conigli. Assumendo che: la prima coppia diventi fertile al compimento del primo mese e dia alla luce una nuova coppia al compimento del secondo mese; le nuove coppie nate si comportino in modo analogo; le coppie fertili, dal secondo mese di vita, diano alla luce una coppia di figli al mese; avremo che se partiamo con una singola coppia dopo un mese una coppia di conigli sarà fertile, e dopo due mesi due coppie di cui una sola fertile, nel mese seguente avremo 2+1=3 coppie perché solo la coppia fertile ha partorito, di queste tre ora saranno due le coppie fertili quindi nel mese seguente ci saranno 3+2=5 coppie, in questo modo il numero di coppie di conigli di ogni mese descrive la successione dei numeri di Fibonacci.

I primi 41 numeri di Fibonacci sono:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 (=F₁₀),
89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 (=F₂₀),
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040 (=F₃₀),
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155 (=F₄₀)

Nella OEIS di Neil Sloane la successione di Fibonacci ha la sigla A000045. I numeri di Fibonacci godono di una gamma stupefacente di proprietà, si incontrano nei modelli matematici di svariati fenomeni e sono utilizzabili per molti procedimenti computazionali; essi inoltre posseggono varie generalizzazioni interessanti. A questi argomenti viene espressamente dedicato un periodico scientifico, The Fibonacci Quarterly.

[modifica] Proprietà

Nelle formule che seguono talora scriveremo F(n) invece di F_n.

La successione di Fibonacci possiede moltissime proprietà di grande interesse. Certamente la proprietà principale, e maggiormente utile nelle varie scienze, è quella per cui il rapporto F_n / F_n-1 al tendere di n all'infinito tende al numero algebrico irrazionale chiamato sezione aurea o numero di Fidia. Quindi:

$\lim_{n \to \infty}{F_n \over F_{n-1}}=\,\phi\,$

dove

$\,\phi={1+\sqrt 5 \over 2}=1,6180339887...\,$ .

Curioso anche notare come, proseguendo via via per la sequenza, il rapporto risulti alternativamente maggiore e minore della costante limite.

Naturalmente il rapporto tra un numero di Fibonacci e il suo successivo tende al reciproco della sezione aurea $1/\phi = 0,6180339887...\,$ .

Conviene anche ricordare che:

a) $\phi - 1 = 1/\phi\,$

b) $1 - \phi = -1/\phi = {1-\sqrt 5 \over 2}$

in accordo con la definizione di sezione aurea come il numero positivo tale che $\phi = {1 + 1/\phi}\,$ , equazione che, quando vincolata alla condizione $\phi > 0\,$ , ammette l'unica soluzione $\phi = {1+\sqrt 5 \over 2}$ .

Si noti poi come l'opposto del reciproco del numero di Fidia $-1/\phi\,$ che compare nella b) costituisca la seconda soluzione, a segno negativo, dell'equazione algebrica riportata nella definizione. Esso espone proprietà altrettanto interessanti di quelle del suo omologo positivo.

Ragionamenti analoghi possono essere applicati per ottenere altri rapporti irrazionali costanti; per esempio dividendo ogni numero per il secondo successivo si ottiene 0.382 e dividendo ogni numero per il terzo successivo si ottiene 0.236 , mentre dividendo ogni numero per il secondo precedente si ottiene 2.618 e dividendo ogni numero per il terzo precedente si ottiene 4.236.

Questi sei rapporti (0,236, 0,382, 0,618, 1, 1,618, 2,618, 4,236) sono inoltre molto utilizzati nella teoria delle onde di Elliott, argomento molto importante dell'analisi tecnica dei mercati finanziari.

Altra proprietà interessante è che se un qualsiasi numero della successione è elevato al quadrato, questo è uguale al prodotto tra il numero che lo precede e quello che lo segue, aumentato o diminuito di una unità: per esempio $5^2=25 = 3\cdot 8 +1$ oppure $3^2=9 = 2\cdot 5-1$ . Si trova anche che l'n-simo numero di Fibonacci si può esprimere con la formula:

$F\left(n\right) = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}} = {\phi^n - (-\phi)^{-n} \over \sqrt{5}}$ .

Questa elegante formula prende il nome da Jacques Binet, che la ricavò nel 1843; tuttavia essa era già nota nel XVIII secolo ad Eulero, Abraham De Moivre e Daniel Bernoulli.

Talora risulta comodo servirsi della successione bilatera costituita da numeri interi F_n:= 0 definiti per n intero qualsiasi aggiungendo alle precedenti le definizioni $F_{-n} := (-1)^{n+1} F_n \quad \mathrm{per} \quad n = 1, 2, ...$ .

A partire dai numeri di Fibonacci e dalla sezione aurea si possono definire alcune funzioni speciali: coseno iperbolico di Fibonacci, cotangente iperbolica di Fibonacci, seno iperbolico di Fibonacci, tangente iperbolica di Fibonacci.

[modifica] Altre proprietà

Altre proprietà minori della sequenza di Fibonacci sono le seguenti:

dati quattro numeri di Fibonacci consecutivi, il prodotto del primo col quarto è sempre pari al prodotto del secondo col terzo aumentato o diminuito di 1;
se si prende la sequenza dei quadrati dei numeri di Fibonacci, e si costruisce una sequenza sommando a due a due i numeri della prima sequenza, la sequenza risultante è costituita da tutti e soli i numeri di Fibonacci di posto dispari;
data la sequenza dei numeri di Fibonacci di posto dispari, se si costruisce la sequenza ottenuta sottraendo a due a due i numeri adiacenti della prima sequenza, si ottiene la sequenza dei numeri di Fibonacci di posto pari;
ogni numero di Fibonacci corrisponde alla somma dei numeri che lo precedono eccetto l'ultimo, aumentata di 1.
Il quadrato di ogni numero e il prodotto dei due numeri adiacenti ad esso differiscono, in modulo, di un'unità, in particolare... F_n² = F_n-1*F_n+1-(-1)ⁿ

[modifica] Successione di Fibonacci generica

Una successione di Fibonacci può anche non cominciare necessariamente con due 1. Questa successione è detta successione di Fibonacci generica o generalizzata. Ogni successione generica di Fibonacci rispetta però una singolare caratteristica, la somma dei primi 10 elementi sarà sempre uguale a 11 volte il settimo elemento. La dimostrazione è molto semplice: elenchiamo i primi 10 elementi in questo modo:

1° elemento: m

2° elemento: n

3° elemento: m + n

4° elemento: m + 2n

5° elemento: 2m + 3n

6° elemento: 3m + 5n

7° elemento: 5m + 8n

8° elemento: 8m + 13n

9° elemento: 13m + 21n

10° elemento: 21m + 34n

Sommando tutti i dieci elementi, si otterrà 55m + 88n che è proprio uguale a 11 volte il settimo elemento.

Ogni successione generalizzata conserva la proprietà che il rapporto tra due numeri consecutivi tende alla sezione aurea. Una particolare successione di Fibonacci generalizzata, quella ottenuta ponendo m=2 e n=1, è detta successione di Lucas, dal matematico francese Édouard Lucas.

[modifica] Curiosità

La sezione «Curiosità» è sconsigliata dalle linee guida di Wikipedia.
La voce può essere migliorata integrando i contenuti rilevanti nel corpo della voce e rimuovendo quelli inappropriati.

Immagine:Fibonacci fiori.jpg

Il numero di petali in un fiore è spesso un numero di Fibonacci

Immagine:Fibonacci violino.gif

Gli strumenti musicali sono costruiti seguendo le proporzioni della successione di Fibonacci. Nell'immagine è evidenziata la struttura di un violino

Molti degli "avvistamenti" della serie di Fibonacci sono un po' forzati: lo rivelano Gael Mariani e Martin Scott dell'Università di Warwick, con un articolo su New Scientist del settembre 2005.

Per motivi legati allo sviluppo dei fiori, il numero di petali di molti di essi è un numero di Fibonacci. Per esempio il giglio ha 3 petali, i ranuncoli ne hanno 5, la cicoria 21, la margherita spesso 34 o 55; la testa dei girasoli è costituita da due serie di spirali, una in un senso ed una in un altro. Il numero di spirali di senso diverso differisce per 21 e 34, 34 e 55, 55 e 89, o 89 e 144 semi e lo stesso avviene per le pigne, per le conchiglie, per l'ananas.

Il nostro cervello ha una particolare attitudine a riconoscere nelle onde sonore la serie di Fibonacci, ed è per questo motivo che nel mondo della musica vi è una forte ricorrenza di questi numeri; basti pensare ad un pianoforte che presenta ottave da otto tasti bianchi e 5 neri che generano quindi 13 note; inoltre la prima, la terza e la quinta creano la base maggiore di tutti gli accordi e tra di loro vi è una separazione di 2 toni. Non è quindi una coincidenza che molti strumenti musicali siano costruiti seguendo le proporzioni della serie di Fibonacci; tant'è che il famoso Stradivari, noto per i suoi proverbiali violini, per il calcolo del foro centrale utilizzò la logica del matematico toscano^{[citazione necessaria]}.

La Successione di Fibonacci è rappresentata in un'installazione luminosa di Mario Merz (Il volo dei numeri), che caratterizza una delle fiancate della Mole Antonelliana di Torino.

La Successione di Fibonacci è presente anche a Barcellona, Spagna, nell'area della Barceloneta, grazie ad una installazione luminosa nell'area pedonale; oltre a riportare i numeri della sequenza - in finestrelle illuminate e incastonate nel cemento-, ne riproduce idealmente le caratteristiche ponendo i numeri ad una distanza fedele alla formulazione della successione.

La Successione di Fibonacci è inoltre rappresentata anche a Napoli in una spirale luminosa che ne contiene i numeri, all'interno della stazione "Vanvitelli" della Linea 1 della Metropolitana, e più precisamente sul soffitto che sovrasta le scale mobili quando, superate le obliteratrici, si scende all'interno della stazione vera e propria.

[modifica] Implementazione Informatica

Esistono diversi algoritmi per il calcolo dei numeri di Fibonacci, che vengono spesso presentati come esempi nei corsi introduttivi all'informatica per spiegare la ricorsione o come esempi di soluzioni di diversa complessità algoritmica per uno stesso problema.

[modifica] Implementazione Java

[modifica] Versione ricorsiva

Una prima risoluzione data al problema è una versione basata sulla ricorsione (dunque fortemente intuitiva, in accordo con la definizione stessa della serie di Fibonacci):

/* Versione ricorsiva */
 long fibonacci (int n) {
     if (n < 2) {
         return n;
     }
     return fibonacci (n - 1) + fibonacci (n - 2);
 }

Questa implementazione, tuttavia, viene eseguita in un tempo O(φⁿ), ossia in tempo esponenziale. L'occupazione di spazio è invece O(n).

[modifica] Versione iterativa

La versione iterativa è molto più efficiente in quanto è caratterizzata da complessità O(n) e occupazione di spazio O(1):

/* Versione iterativa */
 long fibonacci (int n) {
     /* Casi base. La "L" indica al compilatore che il numero è di tipo long int. */
     long f0 = 0L;
     long f1 = 1L;
     long temp;
     int i;
 
     if (n == 0) {
         return 0L;
     }
 
     /* L'iterazione parte da 2 e arriva fino a n.
      * Nel ciclo f0 e f1 portano avanti i valori calcolati, temp fa da variabile
      * temporanea per permettere lo scambio di valori. */
     for (i = 2; i <= n; i++) {
         temp = f1;
         f1 = f1 + f0;
         f0 = temp;
     }
 
     return f1;
 }

[modifica] Versione a complessità logaritmica

Esiste un implementazione che permette di calcolare un numero di Fibonacci in tempo logaritmico (a patto che si possa considerare costante il tempo di calcolo della moltiplicazione). Essa sfrutta le proprietà delle matrici e calcola il numero come potenza della matrice

$a= \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}.$

Infatti si ha che

$a^2=F(3)= \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix},$

$a^3=F(4)= \begin{pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix},$

$a^4=F(5)= \begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix},$

e così via. L'espressione generica è

$a^{n-1}= \begin{pmatrix} F(n) & F(n-1) \\ F(n-1) & F(n-2) \end{pmatrix}.$

L'algoritmo si riduce quindi al calcolo della potenza di una matrice. Essa può essere calcolata per moltiplicazioni successive in tempo $O (n)$ , per esempio

$a^8=a\cdot a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a,$

o per potenze successive in tempo $O (log(n))$

$a 8 = ((a 2) 2) 2 .$

L'implementazione è ovvia nel caso di elevazioni a potenze di due che presentano sempre elevazioni al quadrato. Nel caso di numeri che non sono potenze di due si moltiplica la matrice per $a$ e si procede come se fosse una potenza di due. Ad esempio:

$\begin{align} a^{13}&=a\cdot a^{12},\\ a^{12}&=(a^6)^2,\\ a^6&=(a^3)^2,\\ a^3&=(a\cdot a^2), \end{align}$

quindi $a 13 = a (((a (a 2)) 2) 2)$ .

Considerato il fatto che la matrice contiene sempre due termini uguali, nell'implementazione si può usare un vettore di tre elementi. Per elevare la matrice a potenza invece di moltiplicarla effettivamente per $a$ si può calcolare solo il primo elemento: gli altri si ottengono con uno shift. Per esempio:

$b=a^n=\begin{pmatrix} b_1 & b_2 \\ b_2 & b_3 \end{pmatrix}$

allora

$b\cdot a=\begin{pmatrix} b_1+b_2 & b_1 \\ b_1 & b_2 \end{pmatrix}.$

In questo modo si riduce ulteriormente la complessità computazionale.

[modifica] Implementazione C

L'implementazione in C è la seguente:

void potenza(int n, unsigned int* matrice){
    unsigned int a,b,c; 
    if (n<=1) return;
    potenza(n/2,matrice);
    a = matrice[0]; b = matrice[1]; c = matrice[2];
    matrice[0] = a*a + b*b;
    matrice[1] = a*b + b*c;
    matrice[2] = b*b + c*c;
    if (n%2>0) {
       a = matrice[0]; b = matrice[1]; c = matrice[2];
       matrice[0] = a + b;
       matrice[1] = a;
       matrice[2] = b;
    }
};
 
unsigned int fibonacci(int n){
    if (n<1) return 0;
    if (n<3) return 1;
    unsigned int matrice[3] = {1,1,0};
    potenza(n-1,matrice);
    return matrice[0];
}

[modifica] Implementazione Prolog

L'implementazione non ottimizzata in Prolog:

fibonacci(1,1).
 fibonacci(2,1).
 fibonacci(N,R):-N1 is N-1,N2 is N-2,fibonacci(N1,R1),fibonacci(N2,R2),R is R1+R2.

In questa versione si fornisce in uscita una lista di tutti i numeri della serie da 0 fino a quello richiesto. Questa implementazione permette di non richiamare ricorsivamente due volte la serie, ma di usare il valore della chiamata precedente per calcolare il successivo riducendo così la complessità.

fib(2,[1,0]):-!.
 fib(N,[E,H1,H2|T]):- N1 is N-1,fib(N1,[H1,H2|T]),E is H1 +H2.

[modifica] Implementazione Ruby

L'implementazione in Ruby è la seguente:

def potenza(n,matrice)
    a,b,c=0,0,0
    return if(n<=1)
    potenza(n/2,matrice)
    a=matrice[0];b=matrice[1];c=matrice[2]
    matrice[0]=a*a+b*b
    matrice[1]=a*b+b*c
    matrice[2]=b*b+c*c
    if (n%2>0)
       a=matrice[0];b=matrice[1];c=matrice[2]
       matrice[0]=a+b
       matrice[1]=a
       matrice[2]=b
    end
end
 
def fibonacci(n)
    return 0 if(n<1)
    return 1 if(n<3)
    matrice = [1,1,0]
    potenza(n-1,matrice);
    return matrice[0];
end

[modifica] Implementazione Python

L'implementazione in Python è la seguente:

def potenza(n, a,b,c):
    if n<=1: return a,b,c
    a,b,c = potenza(n/2, a,b,c)
    a,b,c = a*a+b*b, a*b+b*c, b*b+c*c
    if n%2==0: return a,b,c
    return a+b, a, b
 
def fibonacci(n):
    if n==0: return 0
    if n<=2: return 1
    return potenza(n-1, 1,1,0)[0]

L'implementazione in linguaggi che supportano la precisione arbitraria (come Python, Ruby, Matlab, Scilab etc) permette di calcolare $F (n)$ per $n$ molto grandi senza andare in overflow.

F(1000)=
434665576869374564356885276750406258025646605173717804
024817290895365554179490518904038798400792551692959225
930803226347752096896232398733224711616429964409065331
87938298969649928516003704476137795166849228875

[modifica] Bibliografia

(IT) Marcel Danesi, Labirinti, quadrati magici e paradossi logici. I dieci più grandi. Dedalo, 2006. ISBN 8822062930
(IT) Paolo Camagni, Algoritmi e basi della programmazione. Hoepli, 2003. ISBN 8820336014
(IT) Rob Eastaway, Probabilità, numeri e code. La matematica nascosta nella vita. Dedalo, 2003. ISBN 8822062639
(IT) Rita Laganà, Marco Righi, Francesco Romani, Informatica. Concetti e sperimentazioni. Apogeo, 2007. ISBN 8850324936
(IT) Adam Drozdek, Algoritmi e strutture dati in Java. Apogeo, 2001. ISBN 8873038956
(IT) Gianclaudio Floria, Andrea Terzaghi, Giocare e vincere con Excel. FAG, 2006. ISBN 8882335291
(IT) Daniele Marsero, Of game. UNI, 2006. ISBN 8888859403
(IT) Peter Higgins, Divertirsi con la matematica. Curiosità e stranezze del mondo dei numeri. Dedalo, 2001. ISBN 8822062167
(IT) Michael Schneider, Judith Gersting, Informatica. Apogeo, 2007. ISBN 8850323832
(IT) Joseph Mayo, C#. Apogeo, 2002. ISBN 8850320116
(EN) Thomas Koshy, Fibonacci and Lucas Numbers with Applications. Wiley, 2001. ISBN 0471399698
(EN) Leland Wilkinson, The Grammar of Graphics. Springer, 2005. ISBN 0387245448

[modifica] Voci correlate

[modifica] Bibliografia e riferimenti

(EN) "Not so Fibonacci", New Scientist, n. 251, 24 settembre 2005, pagina 24.

[modifica] Collegamenti esterni

(EN) Voce di MathWorld
(EN) The Golden Section: Phi
(EN) Computing Fibonacci numbers on a Turing Machine
(EN) The Fibonacci Quarterly — periodico contenente risultati di ricerche concernenti lo studio dei numeri di Fibonacci.
(EN) The Fibonacci Series
(EN) Fibonacci Calculator

Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica