Il matematico pisano Leonardo Fibonacci fu ricordato soprattutto per via della sua sequenza divenuta ormai celeberrima. Nella seconda metà del diciannovesimo secolo, un matematico francese di nome Edouard Lucas riprese lo studio di tale sequenza utilizzando come valori di partenza 2 e 1. Questa versione dei numeri fu conosciuta come la sequenza di Lucas. Quest'ultimo fu colui che rese i numeri di Fibonacci noti a tutti. Johannes Kepler notò poi che facendo il rapporto fra due numeri di Fibonacci consecutivi, esso si avvicinava sempre più a 1,61803, valore noto anche con il nome di rapporto aureo.

La serie di Fibonacci è una successione di interi definita a partire dalla coppia 1, 1 in cui l'elemento successivo è calcolato come somma degli ultimi due.
Una definizione più formale è:

Fib(0) = 1
Fib(1) = 1
Fib(n) = Fib(n-1)+Fib(n-2) se n>1

il valore della funzione Fib è definito in termini della funzione stessa. Funzioni di questo tipo sono dette ricorsive e vengono definite da equazioni dette ricorrenti o alle differenze.
Proviamo a calcolare i primi numeri della serie a partire dalla definizione informale, in cui costruiamo l'elemento successivo per somma degli ultimi due, iniziando dalla coppia 1, 1:

1 (primo numero iniziale)
1 (secondo numero iniziale)
2 = 1+ 1 (somma degli ultimi due)
3 = 2 +1 ( .... come sopra ... )
5 = 3 + 2
8 = 5 + 3 ( .... come sopra ... )
...
Applichiamo invece la definizione ricorsiva per calcolare Fib(4), ovvero il quinto elemento della successione (osservazione: il primo elemento è Fib(0) )

Fib(4) =
Fib(3) + Fib(2) =
Fib(2)+Fib(1) + Fib(1) + Fib(0)=
Fib(1) + Fib(0) + 1 + 1 + 1=
1 + 1 + 1 + 1 + 1=
5

Anche che la definizione ricorsiva, sebbene più compatta, è computazionalmente svantaggiosa rispetto alla definizione informale, presentata in forma iterativa. In altri termini, il calcolo dell'n-mo elemento della successione genera un albero di computazioni dell'ordine del quadrato di n. Ciò significa che per calcolare Fib(4) abbiamo impiegato circa sedici operazioni.

Col metodo esplicito l'ordine delle computazioni è di n, in quanto per calcolare Fib(n) dobbiamo generare tutti e soli i valori degli elementi precedenti.
Il vantaggio della formulazione mediante equazioni alle ricorrenze consiste nella facoltà di trovare, con un metodo generalizzato per le equazioni alle ricorrenze (brevemente esposto nel seguito), una formulazione esplicita per il valore di Fib(n):

ove è il valore del Rapporto Aureo, pari a

Si osservi che la formula esplicita proposta è semplificata, producendo una serie di Fibonacci a partire dalla coppia 0, 1.

I numeri di Fibonacci hanno una innumerevole gamma di applicazione, soprattutto in matematica ma anche in altre aree, quali la biologia, l'architettura, l'economia e l'informatica

[Sommario] [Successivo : Le proprietà matematiche della serie ]