Giochiamo con i numeri di Fibonacci

Iniziamo ad esaminare un tema apparentemente semplice ma che ha ancora vasti settori in cui indagare ulteriormente: i numeri di Fibonacci.

Numeri di Fibonacci classici
I numeri di Fibonacci sono i numeri della successione di Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21,. . . . . ciascuno dei quali, dopo il secondo è la somma dei due precedenti.

In generale è:
F(0)=0
F(1)=1
F(k)= F(k-1)+F(k-2)

I numeri di Fibonacci possono anche essere considerati come una funzione di numeri interi non negativi:
   n  = 0, 1, 2, 3, 4, 5, 6,  7,  8,  9, 10, 11,  12, ...    
F (n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

La soluzione esatta in forma chiusa per questa funzione è chiamata "formula di Binet":
    
F (n) = (Phi ^ n - Phip ^ n) / sqrt (5) (per tutti intero n> = 0 oppure n <0),

dove

Phi  = (1 + sqrt (5)) / 2 = 1,61803398874989484820 ... (Golden Ratio)
Phip = Phi Prime = (1 - sqrt (5)) / 2 = 1 - Phi = -1/Phi = -0,61803398874989484820 ...,

Poiché F (k) è un intero e l'entità delle Phip ^ n / sqrt (5) è inferiore a 1 / 2 per n> = 0,
una forma variante della formula è:

F(k) = ceil (Phi ^ n / sqrt (5)), n> = 0.

Se si dispone di un numero di Fibonacci si può calcolare il suo indice: k = indFib (F (k)) 


La formula è la seguente:
     indFib(k) = 0 if |k| < 1, altrimenti
     iindFib(k) = ceil (Log (sqrt (5) * abs( k )) / Log (Phi)).

Ad esempio, indFib (144) = 12.  E' accurata se k è un numero di Fibonacci.

Un numero di Fibonacci si verifica  con isFib (k)
Un numero di Fibonacci deve essere un numero intero e si deve ottenere un quadrato perfetto da  5 * x ^ 2 + 4 o 5 * x ^ 2 - 4.

I numeri di Fibonacci possono essere definiti anche per n negativi:
     F(–2*k) = –F(2*k) F (-2 * k) =-F (2 * k)
     F(–2*k – 1) = F(2*k + 1) F (-2 * k - 1) F = (2 * k + 1)

       n  = ..., –6, –5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, 6, ...
     F(n) = ..., –8,  5, –3,  2, –1,  1, 0, 1, 1, 2, 3, 5, 8, ...

La funzione continua analitica:
     Fe(x) = (Phi^x – 1 / Phi^x) / Sqrt(5),
passa attraverso tutti i numeri di Fibonacci, anche n = x (n positivo o negativo).

La funzione continua analitica:
     Fo (x) = (Phi ^ x + 1 / Phi ^ x) / sqrt (5),
passa attraverso tutti i numeri di Fibonacci di n dispari = x (n positivo o negativo).

La funzione continua analitica:
     Fib(x) = (1 + cos(x*Pi))*Fe(x)/2 + (1 – cos(x*Pi))*Fo(x)/2,
passa attraverso tutti i numeri di Fibonacci per ogni n = x (n positivo o negativo).

Questa ultima espressione può essere ridotta a:
     Fib(x) = (Phi^x – cos(x*Pi) / Phi^x) / sqrt(5)

Questa formula può anche essere usato per calcolare la funzione di Fibonacci generalizzata di una
variabile complessa.Ad esempio:

Fib (3 + 4 * i) = -5248.51130,72837,20182,8 ... -14195.96228,83530,10885,8 ... * i. * I.

E' pur vero che Fib (x 2) = Fib (x 1) + Fib (x).

Ad esempio Fib (3,6 + 4,7 * i) = Fib (2,6 + 4,7 * i) + Fib (1.6 + 4.7 * I).

Numeri complessi di Fibonacci
Un numero complesso di Fibonacci è un numero complesso z la cui parte reale Re(z) è un numero di Fibonacci F(k).

Ad esempio z=8-i è un numero complesso di Fibonacci perchè Re(z)=8=F(6).


Proprietà dei numeri complessi di Fibonacci

Il rapporto di numeri complessi di Fibonacci con k dispari e n > 0 è tale che:

[F(k) - n*i] / [F(k-1)-(n-1)*i] = [F(k+n)+i*(-1)^(n-1)] / [F(k+(n-1)]

dove F(k+n)=Sum(i=k+1,n-1,F(i))

Ad esempio:
(5  - i ) / 3-i = 8  + i / 5
(13 - i ) / 8-i = 21 + i / 13
(8 - 2i) / (5 - i) = (21 - i) / 13
(13 - 3i)/(8 - 2i) = (55 + i)/34 (13 - 3i) / (8 - 2i) = (55 + i) / 34

Per k pari e n > 0 la formula non vale per i numeri complessi ma solo per i numeri interi sostituendo 1 a i,
ovvero:

[F(k) - n] / [F(k-1)-(n-1)] = [F(k+n)+(-1)^(n-1)] / [F(k+(n-1)]

dove F(k+n)=Sum(i=k+1,n-1,F(i))

(8 - 1) / (5 - 1) = (13 + 1) / 8.
(13 - 2) / 8 - 1) = (34 - 1) / 21
(8 - 3)/(5 - 2) = (34 + 1)/21 (8 - 3) / (5 - 2) = (34 + 1) / 21

Legame con il triangolo di Tartaglia o con i coefficienti binomiali

Il triangolo di Tartaglia o di Pascal è noto. Ebbene se si considerano le diagonali che dall'alto a destra scendono verso sinistra si individuano i numeri di Fibonacci.

La relazione esistente è difatti:
Fib(n)= Sum(k=0,n-1,(n-k-1 k) ) = Sum(k=1,n,(n-k k-1) )   

dove per semplicità la notazione (n-k-1 k) rappresenta un coefficiente binomiale

Teorema
Ogni numero di Fibonacci è un fattore di (un numero infinito di) numeri di Fibonacci successivi oppure ogni k-th numero di Fibonacci è un multiplo di F (k)". E' equivalente a dire matematicamente che:
Se Fib(k) = m allora Fib(n*k) = t con m|t

Si dimostra in due modi possibili:
1.mo modo:

Dai coefficienti binomiali

Fib(k)        = Sum(i=1,k-1, (k-i i-1) ) = m
 
Fib(n*k)    = Sum(i=1,n*k-1, (n*k-i i-1) ) = t
   
2.do modo:

Costruiamo una tabella mettendo x se il risultato m di m=Fib(k) non è un divisore di Fib(k) e * se lo è:

       i        3 4 5 6 7   8   9  10 11 12

Fib(i)       2 3 5 8 13 21 34 55 89 144

2=Fib(3) * x  x * x    x   *   x   x   *

3=Fib(4) x *  x x x    *   x   x    x  *

5=Fib(5) x x * x x     x   x   *    x  x

Proseguendo si vede ad esempio che:
- 2 è un fattore ogni 3 Fib(k)
- 3 è un fattore ogni 4 Fib(k)
- 5 è un fattore ogni 5 Fib(k)
etc

Teorema
I numeri di Fibonacci vicini non hanno fattori in comune oppure Fib (k) e Fib (k +1) sono coprimi.

Se Fib(k)=m*a   e  Fib(k+1)=m*b  per assurdo allora Fib(k+2)=Fib(k)+Fib(k+1)=m*(a+b)
Il che vorrebbe dire che tutta la serie di Fibonacci dovrebbe avrebbe lo stesso fattore m in comune,
il che non è vero.

=== Teorema di Vorob’ev ===

gcd( F(m), F(n) ) = F( gcd(m,n) )

Numeri di Fibonacci primi
Come corollario di prima, se l'indice di un numero di Fibonacci è un multiplo di k, il numero di Fibonacci è composto.

Se il numero di Fibonacci è un primo lo è anche l'indice.

Non è vero il contrario. Infatti ad esempio

F (19) = 4.181 e F (19) non è primo perché 113x37 = 4.181

Il più grande numero primo di Fibonacci F (81.839) è stato segnalato in aprile 2001 da David Broadbent e Bouk de Water.

La serie di numeri indice dei numeri primi di Fibonacci è A001605 Sloane

Numeri di Fibonacci e fattori primi speciali
Se guardiamo i fattori primi di un numero di Fibonacci, ci sarà almeno uno di loro che non è mai apparso come un fattore in ogni numero di Fibonacci in precedenza.

Questo è noto come teorema di Carmichael e si applica a tutti i numeri di Fibonacci, tranne casi particolari:

Fib (1) = 1 (non ha fattori primi),
Fib (2) = 1 (non ha fattori primi),
Fib (6) = 8, che ha solo il fattore primo 2, che è anche Fib (3),
Fib (12) = 144, che anche solo il 2 e 3, come i suoi fattori primi e questi sono apparsi in precedenza come Fib (3) = 2 e Fib (4) = 3.


Alla prox