In matematica, la successione di Fibonacci (detta anche successione aurea) è una successione di numeri interi in cui ciascun numero è la somma dei due precedenti, eccetto i primi due che sono, per definizione, 0 e 1. Questa successione, indicata con o con , è definita ricorsivamente: partendo dai primi due elementi, e , ogni altro elemento della successione sarà dato dalla relazione:
Gli elementi sono anche detti numeri di Fibonacci. I primi termini della successione di Fibonacci, che prende il nome dal matematico pisano del XIII secolo Leonardo Fibonacci, sono:
Storia Nel 1202 il matematico pisano Leonardo Fibonacci pubblicò il Liber abbaci, un trattato di aritmetica e algebra con il quale voleva introdurre in Europa il sistema numerico decimale indo-arabico e i principali metodi di calcolo ad esso relativi. All'interno del trattato portò diversi problemi aritmetici con relativa soluzione. Uno di questi riguardava la crescita di una popolazione di conigli.
Assumendo per ipotesi che: si disponga di una coppia di conigli appena nati questa 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 in poi diano alla luce una coppia di figli al mese; si verifica quanto segue: dopo un mese una coppia di conigli sarà fertile, dopo due mesi ci saranno due coppie di cui una sola fertile, nel mese seguente, terzo mese dal momento iniziale, ci saranno coppie perché solo la coppia fertile avrà generato; di queste tre, due saranno le coppie fertili, quindi nel mese seguente (quarto mese dal momento iniziale) ci saranno coppie
In principio Al termine del primo mese Al termine del secondo mese Al termine del terzo mese Al termine del quarto mese Al termine del quinto mese Al termine del sesto mese Al termine del settimo mese Al termine dell'ottavo mese Al termine del nono mese Al termine del decimo mese Al termine dell'undicesimo mese Al termine del dodicesimo mese Coppie di conigli 1 1 2 3 5 8 13 21 34 55 89 144 233
In questo esempio, il numero di coppie di conigli di ogni mese esprime la successione di Fibonacci.
Proprietà Il rapporto , per tendente all'infinito, tende al numero algebrico irrazionale chiamato sezione aurea o numero di Fidia. In termini matematici:
dove
Infatti, se poniamo risulta
da cui segue che , ossia . Tale equazione ha per soluzioni , ma perché la successione di Fibonacci è definitivamente crescente: perciò
Il rapporto tra un numero di Fibonacci e il suo successivo tende al reciproco della sezione aurea
Per valgono le seguenti relazioni: a) b)
L'-esimo numero di Fibonacci si può esprimere con la formula:
Questa elegante formula è nota come formula di Binet. Jacques Binet la dimostrò nel 1843, tuttavia essa era già nota nel XVIII secolo a Eulero, Abraham de Moivre e Daniel Bernoulli. Questa espressione per può essere calcolata per mezzo della trasformata zeta.
Talora risulta comodo servirsi della successione bilatera, cioè una successione definita sugli interi invece che sui naturali, costituita da numeri interi aggiungendo ai precedenti i termini per di cui alcuni termini sono:
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.
Proprietà di una qualunque successione definita come quella di Fibonacci Dati due numeri Naturali qualunque e con e costruita, analogamente a quella di Fibonacci, la successione:
, , , ...,
allora
Dimostrazione
Ogni numero della successione è la somma dei due precedenti che a sua volta sono la somma dei due precedenti, di fatto (un po’ come per i coniglietti di Fibonacci) ogni è esprimibie come somma di un certo numero di volte più un certo numero di volte .
= 1 +1 = + = = 2 + 1 = + = = 3 + 2 = + = = 5 + 3
dove è l'ennesimo numero di Fibonacci con , , , ...
Quindi:
Mediante la seguente formula di Binet:
e facendo una serie di passaggi algebrici, si ottiene
Relazioni con il triangolo di Tartaglia e i coefficienti binomiali Il triangolo di Tartaglia è una famosa rappresentazione dei coefficienti binomiali che si ottengono dallo sviluppo del binomio di Newton , dove è una riga del triangolo:
Per mostrare che esiste una relazione tra il triangolo e i numeri di Fibonacci, riscriviamo i numeri del triangolo nel seguente modo:
A partire dalla prima linea rossa in alto, se si sommano i numeri attraversati da ogni linea, si ottiene la successione di Fibonacci.
La relazione con i coefficienti binomiali è:
Numeri di Fibonacci e fattori comuni Se , allora , cioè ogni multiplo di individua un numero di Fibonacci multiplo di .
Visivamente, si può costruire una tabella mettendo "x" se non è un divisore di :
i 3 4 5 6 7 8 9 10 11 12 F(i) 2 3 5 8 13 21 34 55 89 144 F(3)=2 x x x x x x F(4)=3 x x x x x x x F(5)=5 x x x x x x x x
Da cui si vede che è un fattore di per ogni , è un fattore di per ogni , è un fattore di per ogni , e così via.
La dimostrazione segue dai coefficienti binomiali
Numeri di Fibonacci vicini Due numeri di Fibonacci consecutivi non hanno fattori comuni, cioè sono coprimi.
Infatti, sia e per qualche , in cui è un divisore comune. Si ha , cioè anche ha come divisore e, proseguendo il ragionamento per i termini precedenti , si arriva che anche ha come divisore, quindi
Numeri di Fibonacci primi Dato che è divisibile per e , se un numero è primo, anche è primo, fatta eccezione per .
Non è vero il contrario. Infatti ad esempio è primo, mentre non è primo.
Il più grande numero di Fibonacci primo noto è stato segnalato in aprile 2001 da David Broadbent e Bouk de Water.
La successione di numeri indice dei numeri primi di Fibonacci è la sequenza A001605.
Teorema di Carmichael e fattori primi caratteristici Per ogni , esiste un fattore primo del numero di Fibonacci che non è mai apparso come fattore dei numeri di Fibonacci , con
Questo teorema è noto come teorema di Carmichael. Per si hanno i seguenti casi particolari:
(non ha fattori primi);
(non ha fattori primi);
, che ha solo il fattore primo , che è anche ;
, che ha solo i fattori e , come i suoi fattori primi e questi sono apparsi in precedenza come e .
Si noti che questo non significa che deve essere un numero primo per ogni primo. Ad esempio , dove è un numero primo, ma no.
I fattori primi di un numero di Fibonacci che non dividono nessun numero di Fibonacci precedente sono detti fattori caratteristici o divisori primi primitivi.
Un fattore primitivo di è congruente a , con l'eccezione .
Se e è un divisore primitivo di , allora è primo. Se e è un divisore primitivo di , allora è primo (questo teorema è stato citato per la prima volta da Édouard Lucas, ma non dimostrato).
Proprietà di divisibilità I numeri di Fibonacci godono in generale delle seguenti proprietà di divisibilità:
se allora
dove il simbolo significa che è un divisore di
Un altro risultato è il seguente: scelti numeri di Fibonacci da un insieme , allora uno dei numeri scelti divide un altro esattamente (Weinstein 1966).
Mihàly Bencze trovò una nuova proprietà di divisibilità con una nuova sequenza. La sequenza ha i primi quattro valori fissati e la regola
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 B(n) 4 0 0 3 4 0 3 7 4 3 10 11 7 13
Ora si osserva che è sempre divisibile per , quando è un numero primo (Bencze 1998).
Primalità Se è un numero primo maggiore di e oppure e è un numero primo (una condizione che ricorda quella sulla primalità di Sophie Germain), allora , quindi è composto.
Se è primo, allora non è un quadrato perfetto ad eccezione di , nel qual caso però è , con non quadrato perfetto.
Relazioni con il massimo comun divisore e la divisibilità Un'importante proprietà dei numeri di Fibonacci riguarda il loro massimo comun divisore. Infatti è soddisfatta l'identità
(teorema di Vorob'ev).
Da questo segue che è divisibile per se e solo se è divisibile per . Questa proprietà è importante perché ne segue che un numero di Fibonacci può essere un numero primo solamente se stesso è un numero primo, con l'unica eccezione di (l'unico numero di Fibonacci per cui potrebbe essere divisibile è ).La sequenza dell'OEIS elenca i primi numeri primi presenti nella successione di Fibonacci; la sequenza ne elenca invece gli indici Il viceversa tuttavia non è vero: , ad esempio, è uguale a .
Non è noto se i numeri primi che sono anche numeri di Fibonacci siano o meno infiniti.
Inoltre si può dimostrare che ogni numero primo divide almeno uno, e di conseguenza infiniti, numeri di Fibonacci.
Altre proprietà Tra le altre proprietà minori della successione di Fibonacci vi sono le seguenti.
Charles Raine trovò quanto segue. Si considerino 4 numeri di Fibonacci consecutivi e un triangolo rettangolo con cateti , e ipotenusa . Allora, se è uguale al prodotto dei termini esterni e è uguale al doppio del prodotto dei termini interni (ovvero se e ), anche è un numero di Fibonacci. Inoltre, l'area del triangolo è uguale al prodotto dei quattro numeri.
Prendendo ad esempio i numeri e allora è . Sommando i quadrati ed estraendo la radice quadrata otteniamo , che è l'undicesimo numero di Fibonacci. L'area del triangolo sarà . Dati quattro numeri di Fibonacci consecutivi, il prodotto del primo col quarto è sempre pari al prodotto del secondo col terzo aumentato o diminuito di . 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 . Gli unici numeri di Fibonacci che sono anche quadrati sono e come dimostrato nel 1963 da John H. E. Cohn. Nel 2006 Yann Bugeaud, Maurice Mignotte e Samir Siksek hanno dimostrato che , e sono gli unici numeri di Fibonacci espressioni di potenze. L'identità di Cassini, scoperta nel 1680 da Jean-Dominique Cassini, afferma che per ogni intero ,
Tale identità è stata generalizzata nel 1879 da Eugène Charles Catalan:
La somma dei reciproci dei numeri di Fibonacci converge, come si può vedere applicando il criterio del rapporto, ricordando che il rapporto tra due numeri di Fibonacci consecutivi tende a . La somma di questa serie è circa è stato dimostrato che questo numero è irrazionale. Si può ricavare già da termini con PARI/GP: sum(i=1,100,1.0/fibonacci(i))
Algoritmo di Euclide con ciclo più lungo Lamé dimostrò nel 1844 che l'algoritmo di Euclide ha un ciclo più lungo se in input ci sono numeri di Fibonacci.
Frazioni continue Ci sono legami con le frazioni continue da parte dei numeri di Fibonacci e anche con le frazioni di Farey e la sezione aurea.
Una particolare frazione continua infinita è la sezione aurea
La frazione continua precedente si può anche considerare come vari pezzetti di termini convergenti; ad esempio:
I vari pezzetti visti prima danno due legami inattesi della sezione aurea: uno con la successione di Fibonacci, l'altro con la sequenza di Farey.
Difatti tra i pezzetti si ripete la sequenza come nei numeri di Fibonacci. Escludendo , per ottenere il terzo elemento si devono sommare i primi due, per ottenere poi il successivo termine si devono sommare i precedenti due, ecc.
Sempre dai pezzetti si osserva che due successivi convergenti della sezione aurea soddisfano la relazione Ad esempio con e si ha che , come nella sequenza di Farey.
Generalizzazioni Una generalizzazione si può ottenere ponendo:
e per ogni sia