Fibonacci e Binet - 2

La linearizzazione delle potenze di $\phi$ non è l'unico metodo per ricavare la formula di Binet. In alternativa si può fare uso della cosiddetta matrice di Fibonacci

$$
F=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
$$
per cui vale
$$
F^2=
 \begin{pmatrix}
2 & 1 \\
1 & 1
\end{pmatrix}
\,,\,
 F^3=
 \begin{pmatrix}
3 & 2 \\
2 & 1
\end{pmatrix}
\,,\,
F^4= \begin{pmatrix}
5 & 3 \\
3 & 2
\end{pmatrix}
\,,\,
F^5= \begin{pmatrix}
8 & 5 \\
5 & 3
\end{pmatrix}
 $$
e più in generale, com'è relativamente semplice mostrare induttivamente, 
$$
F^n =\begin{pmatrix}
f_{n+1} & f_{n} \\
f_n &f_{n-1}
\end{pmatrix}
$$

dove $(f_1,f_2,f_3,f_4,f_5,f_6,f_7\ldots)=(1,1,2,3,5,8,13,\ldots)$ rappresenta la successione di Fibonacci. Essenzialmente, occorre quindi calcolare le potenze di $F$ in modo efficiente.

Iniziamo determinando gli autovalori di $F$; il suo polinomio caratteristico è il "polinomio aureo" 

$$
p_F(\lambda)={\rm det}(F-\lambda I_2)=\lambda^2-\lambda-1
$$
i cui zeri sono gli autovalori di $F$
$$
\lambda_1=\phi=\frac{1+\sqrt 5}{2} \quad,\quad
\lambda_2=\rho=-\frac{1}{\phi}=1-\phi=\frac{1-\sqrt 5}{2} \;.
$$
Per i relativi autospazi vale
$$
S_\phi={\rm Ker}(F-\phi I_2)=
\left<
\begin{pmatrix}
-1 \\ \rho
\end{pmatrix}
\right>
$$
e
$$
S_\rho={\rm Ker}(F-\rho I_2)=
\left<
\begin{pmatrix}
-1 \\ \phi
\end{pmatrix}
\right> \;.
$$
Di conseguenza, per
$$
B=
\begin{pmatrix}
-1 & -1 \\ \rho & \phi
\end{pmatrix}
$$
vale
$$
F=
B
 \begin{pmatrix}
\phi & 0 \\ 0 & \rho
\end{pmatrix}
B^{-1}
$$
e
$$
F^n =
B
 \begin{pmatrix}
\phi^n & 0 \\ 0 & \rho^n
\end{pmatrix}
B^{-1}
= \ldots =
\frac{1}{\sqrt{5}}
\begin{pmatrix}
\phi^{n+1}-\rho^{n+1} & \phi^n-\rho^n \\  \phi^n-\rho^n & \phi^{n-1}-\rho^{n-1}
\end{pmatrix} \:.
$$
Dal confronto delle componenti con
$$
F^n =\begin{pmatrix}
f_{n+1} & f_{n} \\
f_n &f_{n-1}
\end{pmatrix}
$$
segue immediatamente che
$$
f_n =  \frac{ \phi^n-\rho^n}{\sqrt{5}} \quad,
$$
come volevasi dimostrare.