Successione di Fibonacci

Da Wikipedia, l'enciclopedia libera.

Il volo dei numeri di Mario Merz

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

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

Curioso anche notare come, salendo via via per la sequenza, questo rapporto risulti alternatamente 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'inverso 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}}$ .

Tale formula, di rara bellezza ed eleganza, porta il nome di 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] Successione di Fibonacci generica

Una successione di Fibonacci può anche non cominciare necessariamente con due 1. Questa succesione è detta di Fibonacci generica, 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.

[modifica] Curiosità

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

Gli strumenti musicali sono costruiti seguendo le proporzioni della successione di Fibonacci. Nella foto è evidenziata la struttura di un violino

Molti degli "avvistamenti" della serie di Fibonacci sono un po' tirati per i capelli: 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.

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.

[modifica] Implementazione Informatica

[modifica] Versione ricorsiva

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. 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 fibor(int i)
 {
  return i <= 1 ? i : fibor(i-1) + fibor(i-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 fiboi(int i)
 {
   long f0 = 0L, f1 = 1L, temp;
   int j;
   
   if(!i)
     return 0;
   
   for(j = 2;j <= i;j++) 
   {
     temp = 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.

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];
}

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

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

F(1000)=
434665576869374564356885276750406258025646605173717804
024817290895365554179490518904038798400792551692959225
930803226347752096896232398733224711616429964409065331
87938298969649928516003704476137795166849228875

[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

Estratto da "http://it.wikipedia.org../../../s/u/c/Successione_di_Fibonacci_8316.html"

Categorie: Combinatoria | Successioni di interi

We provide Linux to the World