[HOME - BASE Cinque - Appunti di Matematica ricreativa]

La successione di Fibonacci

Alcune proprietà - con dimostrazioni

Puoi trovare il problema originale di Fibonacci nella pagina: La successione di Fibonacci.

Definizione della successione di Fibonacci
Prendendo lo spunto dal famoso problema dei conigli, e estendendolo, la successione di Fibonacci può essere definita così:

• i primi 2 elementi sono 1, 1;
• ogni altro elemento è dato dalla somma dei due che lo precedono.

Chiamando Fib(n) la successione di Fibonacci, abbiamo la seguente definizione matematica:

• Fib(1) = 1
• Fib(2) = 1
• Fib(n) = Fib(n-2)+Fib(n-1) per n = 3, 4, 5, ...

In base a questa definizione si assume convenzionalmente Fib(0) = 0.

La successione di Fibonacci, dunque, è:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Si osservi che la funzione Fib(n) è ricorsiva, cioè è definita in termini della funzione stessa.

Una formula per calcolare Fib(n) in funzione di n
Tino, al Forum, segnala una formula "diabolica" che permette di calcolare l'n-esimo termine della successione di Fibonacci conoscendo soltanto n.
La formula di Binet è la seguente:

Fib(n) =

1 5

[

(

1+5 2

)

n

-

(

1-5 2

)

n

]

Il numero phi = (1+5)/2 che compare nella relazione precedente, è il famoso rapporto aureo.
Siccome: (1-5)/2 = 1-phi, la formula di Binet può essere scritta così:

Fib(n) =

1 5

[

(

phi

)

n

-

(

1-phi

)

n

]

N.B. Il simbolo 5 è la radice quadrata di 5

Le domande sono:
a) come si dimostra la validità della formula?
b) perché il risultato, per n intero, è sempre intero? perché la radice di 5 sparisce sempre?

Alessandro B. in una E-mail pone altre due domande.

Massimo comun divisore nella successione di Fibonacci
Il massimo comun divisore tra due numeri di Fibonacci Fib(n) e Fib(m) è il numero della successione, corrispondente al massimo comun divisore di n e m, ovvero:
MCD(Fib(n),Fib(m)) = Fib(MCD(n,m))
Es.: Fib(10) = 55, Fib(5) = 5, MCD(Fib(10),Fib(5)) = Fib(MCD(10,5)) = Fib(5) =5
Questa proprietà è stata scoperta nel 1876 da Edouard Lucas (1842-1891), l’autore della classica opera Recreations Mathematiques.

Come si dimostra?

Se un numero di Fibonacci è primo allora il suo indice è primo
Se mettiamo a confronto la successione di Fibonacci con una successione di numeri naturali, noteremo che ad ogni numero di Fibonacci primo corrisponde un indice primo. (con l'eccezione di Fib(3)=4).
Non vale il viceversa.

E' vero?
Come si dimostra?

Risposte & riflessioni

Una formula per calcolare Fib(n) in funzione di n
Ricordiamo che:

• = (5 + 1)/2
• 1- = (1 - 5)/2
• *(1-) = 1
• -(1-) = 5

Siccome e (1-) sono radici dell'equazione x²=x+1, si può dimostrare (per induzione) che:
se x²=x+1 allora xⁿ = Fib(n) * x + Fib(n-1), per n>0.

Da dimostrare...

Sostituiamo al posto di x:
ⁿ = Fib(n) * + Fib(n-1)

Ma siccome anche (1-) è soluzione, possiamo sostituirlo:
(1-)ⁿ = Fib(n) * (1-) + Fib(n-1)

Sottraiamo le due espressioni:
ⁿ-(1-)ⁿ = Fib(n) * (-(1-))

Ricaviamo Fib(n):

Fib(n) =

n-(1-)n ------------------ (-(1-))

=

n-(1-)n -------------- 5

Sostituendo il valore di , ricaviamo:

Fib(n) =

1 5

[

(

1+5 2

)

n

-

(

1-5 2

)

n

]

Massimo comun divisore nella successione di Fibonacci
Voglio dimostrare che:
MCD(Fib(n),Fib(m)) = Fib(MCD(n,m))

Prima cosa che serve
Prima di tutto dobbiamo dimostrare che che Fib(n) e Fib(n+1) sono sempre primi fra loro, cioè non hanno fattori primi comuni.

Ecco una semplicissima dimostrazione.
Ricordiamo che:

• Se A e B hanno un fattore comune, esso è fattore anche di A+B.
• Se A e B hanno un fattore comune, esso è fattore anche di B-A.
• Se A e B NON hanno fattori comuni, allora NON ne hanno neppure B e A+B.
• Perciò se B e A+B allora anche la loro differenza ha quel fattore e la differenza è proprio A

Prendiamo 3 numeri di Fibonacci successivi: saranno del tipo A, B, A+B.
Se A e B sono primi fra loro, allora anche B e A+B lo saranno. Quindi, se trovo una coppia di numeri di Fibonacci successivi primi fra loro allora, da quel punto in avanti, tutte le coppie di numeri consecutivi saranno primi fra loro.
La successione di Fibonacci è:
0,1,1,2,3,5,...
Visto che 2 e 3 sono primi fra loro allora lo saranno tutte le coppie successive.

Seconda cosa che serve
Se m divide n allora Fib(m) divide Fib(n)

Esempio 4 divide 12, quindi 3 divide 144.
Ora che ci penso, questo non credo di averlo utilizzato.

Terza cosa che serve: la regola della somma
Fib(m+n) = Fib(m)*Fib(n-1) + Fib(n)*Fib(m+1)

Esempio: m=4; n=6; Fib(4+6) = Fib(10)
= Fib(4)*Fib(5) + Fib(6)*Fib(5)
= 3*5 + 8*5=15+40 = 55 = Fib(10)

Da dimostrare...
Si dimostra utilizzando la matrice di transizione.
Oppure per induzione, fissando t e facendo variare u.

Quarta cosa che serve: il famoso algoritmo di Euclide
Se n = qm+r, allora MCD(n,m) = MCD(m,r)

Questo non lo dimostro, perché è molto noto, ma siccome è determinante per la dimostrazione del teorema, lo spiego e faccio un esempio.
Se permettete, lo utilizzerò in una versione semplificata in cui q=1.
Se n = m+r, allora MCD(n,m) = MCD(m,r)

Prendiamo a,b interi con a,b>0 e supponiamo 0<a<b.

Sottraiamo a da b, avremo che:
b-a+r1, con r1<b.
Osserviamo che:
- se r1=0, allora b = a e abbiamo già che MCD(a,b)=a;
-altrimenti:
MCD(a,b) = MCD(a,r1),
con il vantaggio che r1 sarà minore di b.

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r1 (supponiamo a>=r1)
Sottraendo r1 da a avremo:
a-r1=r2, con r2<=a.
dove
- se r2=0, si ha che r1=a, quindi MCD(a,b) = MCD(a,r1) = r2;
-altrimenti:
MCD(a,b)=MCD(a,r1)=MCD(r1,r2).

Andando avanti così, r(i) diventerà sempre più piccolo e ad un certo punto avremo un r(k)=0
MCD(a,b)=MCD(a,r1)=MCD(r1,r2)=...=MCD(r(k-1),0)=r(k-1)
Quindi:
MCD(a,b)=r(k-1)

Ecco un esempio pratico:
MCD(60,35)=
MCD(35,25)=
MCD(25,10)=
MCD(10,15)=
MCD(10,5)=
MCD(5,5)=
MCD(5,0)=5
Questo algoritmo è meno rapido di quello di Euclide ma mi sembra che calzi meglio alla conclusione della dimostrazione.

FINALMENTE si comincia.
Consideriamo due numeri di Fibonacci: Fib(m) and Fib(m+n).

Utilizziamo la seguente proprietà:

Fib(m+n) = Fib(m)*Fib(n-1) + Fib(n)*Fib(m+1)

Dalla proprietà discende che:
MCD(Fib(m), Fib(m+n)) =
MCD(Fib(m), Fib(m)*Fib(n-1) + Fib(n)*Fib(m+1)) = (ho applicato banalmente la formula al secondo termine)
MCD(Fib(m), Fib(n)*Fib(m+1)) = (ho eliminato l'addendo Fib(m)*Fib(n-1) perché è multiplo di Fib(m))
MCD(Fib(m), Fib(n)) (ho eliminato il fattore Fib(m+1) perché è relativamente primo con Fib(m))

Per ora ho dimostrato che:
MCD(Fib(m), Fib(m+n)) = MCD(Fib(m), Fib(n))

Se noi guardiamo gli argomenti (o indici) delle Fib(k) scopriamo di essere di fronte proprio all'algoritmo di Euclide!

Se n = m+r, allora MCD(n,m) = MCD(m,r)
Ciò significa che, in particolare, nell'espressione:
MCD(Fib(m), Fib(n))
possiamo sostituire al maggiore fra m ed n, la differenza fra i due. Se ad esempio n>m, possiamo scrivere:
MCD(Fib(m), Fib(n)) = MCD(Fib(m), Fib(n-m)) = MCD(Fib(m), Fib(r)) con il vantaggio che n<=n

A questo punto, come abbiamo fatto con l'algoritmo semplificato di Euclide, possiamo andare avanti ad oltranza fino ad incontrare una differenza uguale a zero. Avremo allora:
MCD(Fib(m), Fib(n)) = ... ... ... = MCD(Fib(d), Fib(0)) = Fib(d)

Ma, attenzione, che cosa è d?
Per come abbiamo applicato l'algoritmo, d è proprio il MCD(m,n)!

E ora, la sostituzione finale.

MCD(Fib(m), Fib(n)) = Fib(d) = Fib(MCD(m,n))

Che è quello che volevamo dimostrare. Grandioso!

Se Fib(m) è primo allora m è primo (con l'eccezione m=4)

Si può utilizzare questa proprietà:
Fib(nk) è multiplo di Fib(k) per qualsiasi n>1 e per k >1

Da dimostrare...

Consideriamo un numero m, composto (maggiore di 4).
Allora: m=n*k e Fib(m) = Fib(nk)
Siccome Fib(nk) è multiplo di Fib(k) possiamo concludere che Fib(m) è composto.

In definitiva, vale l'impicazione:
Se m è composto allora Fib(m) è composto.

Da questa si può costruire l'implicazione contronominale:
Se Fib(m) NON è composto allora m NON è composto.

ovvero
Se Fib(m) è primo allora m è primo.

Agosto 2004

Sito Web realizzato da Gianfranco Bo