La formula di Binet per i numeri di Fibonacci: una dimostrazione con l’algebra lineare

La formula di Binet per i numeri di Fibonacci: una dimostrazione con l’algebra lineare

Francesco Daddi

Agosto 2009

Lo scopo di queste pagine è quello di dimostrare la formula di Binet per i numeri di Fibonacci facendo uso dell’algebra lineare.

La successione di Fibonacci è definita nel seguente modo:

F₀ = 0

F₁ = 1

F_n = F_n−1 + F_n−2   ∀ n > 1

Osserviamo che, per ogni k ≥ 1, risulta:

F_k+1 = F_k + F_k−1

che possiamo riscrivere nel seguente modo:

F_k+1 / F_k = 1 + F_k−1 / F_k;

se poniamo

u_k = ⎡ F_k+1 ⎤ / ⎣ F_k ⎦,   A = ⎡ 1   1 ⎤ / ⎣ 1   0 ⎦,

si ha:

u_k = A u_k−1 ⇒ u_k = A² u_k−2 ⇒ ... ⇒ u_k = A^k u₀ dove u₀ = ⎡ 1 ⎤ / ⎣ 0 ⎦;

dobbiamo cercare di scrivere con una formula chiusa le potenze di A per risolvere questo problema:

possiamo diagonalizzare A:

A = ⎡ 1   1 ⎤ / ⎣ 1   0 ⎦ = ⎡ (1 + √5) / 2   0 ⎤ / ⎣ 0   (1 − √5) / 2 ⎦ ...

⎡ 1   1 ⎤

⎣ 1   0 ⎦

⎡ (1 + √5) / 2   (1 − √5) / 2 ⎤

⎣ 1   1 ⎦