Sono definiti da $F_0=0$, $F_1=1$ e $F_{n+2}=F_{n+1}-F_n, \forall n \in \mathbb N$. Esiste un modo per calcolare $F_n$ senza dovere prima calcolare tutti i precedenti numeri di Fibonacci? Sì, e per trovarlo usiamo le matrici.
In particolare definiamo la matrice $M=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right )$ e calcoliamo le sue potenze: $$ M^2=\left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right ),\ M^3=\left( \begin{array}{cc} 3 & 2 \\ 2 & 1 \end{array} \right ),\ M^4=\left( \begin{array}{cc} 5 & 3 \\ 3 & 2 \end{array} \right )\ \ldots$$ Come si vede, viene da supporre gli elementi di $M^n$ siano formati dai numeri $F_{n+1}$, $F_n$ e $F_{n-1}$. Possiamo dimostrarlo formalmente per induzione: si ha infatti $M^1=\left( \begin{array}{cc} F_2 & F_1 \\ F_1 & F_0 \end{array} \right)$ e supponiamo che per $1\leq k\leq n$ si abbia $M^k=\left( \begin{array}{cc} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array} \right)$: si avrà allora $$M^{n+1}=M^n\cdot M=\left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)=\\ \ \\=\left( \begin{array}{cc} F_{n+1}+F_n & F_{n+1} \\ F_n+F_{n-1} & F_n \end{array} \right)=\left( \begin{array}{cc} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{array} \right),$$che prova la nostra supposizione.
Ora però, calcolare la potenza ennesima di una matrice è comunque un processo laborioso. Possiamo però semplificarlo diagonalizzando la matrice stessa. Il polinomio caratteristico di $M$ è $$P(\lambda)=\left|M-\lambda I\right|=\left| \begin{array}{cc} 1-\lambda & 1 \\ 1 & -\lambda \end{array} \right|=\lambda^2-\lambda-1$$ che ha come radici $\lambda_{1,2}=\dfrac{1\pm\sqrt5}{2}\ $. Chiamiamo $\varphi$ la radice positiva (è il rapporto aureo, spesso chiamato, ancorché impropriamente, sezione aurea) e $\psi=1-\varphi=-1/\varphi\ $la radice negativa. Due autovettori relativi alle due radici sono $v_\varphi=\left(\begin{array}{c} \varphi \\ 1 \end{array} \right)\ $ e $\ v_\psi=\left(\begin{array}{c} \psi \\ 1 \end{array} \right)$.
Definiamo dunque la matrice $P=\left( \begin{array}{cc} \varphi & \psi \\ 1 & 1 \end{array} \right)$ e calcoliamo $P^{-1}=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} 1 & -\psi \\ -1 & \varphi \end{array} \right)$.
Si ha allora $P^{-1}MP=D=\left( \begin{array}{cc} \varphi & 0 \\ 0 & \psi \end{array} \right)$ e $M=PDP^{-1}$. Si avrà dunque $$M^n=(PDP^{-1})(PDP^{-1})\ldots (PDP^{-1}) =\\ \ \\=PD^nP^{-1}=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} \varphi & \psi \\ 1 & 1 \end{array} \right) \left( \begin{array}{cc} \varphi^n & 0 \\ 0 & \psi^n \end{array}\right)\left( \begin{array}{cc} 1 & -\psi \\ -1 & \varphi \end{array} \right)= \\ \ \\=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} \varphi^{n+1}-\psi^{n+1} & -\varphi^{n+1}\ \psi+\varphi\ \psi^{n+1} \\ \varphi^n-\psi^n & -\varphi^n\ \psi+\varphi\ \psi^n \end{array} \right)=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} \varphi^{n+1}-\psi^{n+1} & \varphi^n -\psi^n \\ \varphi^n-\psi^n & \varphi^{n-1}-\psi^{n-1} \end{array} \right)$$ dove abbiamo sfruttato il fatto che $P^{-1}P=I$ e l’identità $\varphi\ \psi=-1\ $. Otteniamo dunque $$F_n=\dfrac{1}{\sqrt5}(\varphi^n-\psi^n)\ .$$
Si ha allora $P^{-1}MP=D=\left( \begin{array}{cc} \varphi & 0 \\ 0 & \psi \end{array} \right)$ e $M=PDP^{-1}$. Si avrà dunque $$M^n=(PDP^{-1})(PDP^{-1})\ldots (PDP^{-1}) =\\ \ \\=PD^nP^{-1}=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} \varphi & \psi \\ 1 & 1 \end{array} \right) \left( \begin{array}{cc} \varphi^n & 0 \\ 0 & \psi^n \end{array}\right)\left( \begin{array}{cc} 1 & -\psi \\ -1 & \varphi \end{array} \right)= \\ \ \\=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} \varphi^{n+1}-\psi^{n+1} & -\varphi^{n+1}\ \psi+\varphi\ \psi^{n+1} \\ \varphi^n-\psi^n & -\varphi^n\ \psi+\varphi\ \psi^n \end{array} \right)=\dfrac{1}{\sqrt5}\left( \begin{array}{cc} \varphi^{n+1}-\psi^{n+1} & \varphi^n -\psi^n \\ \varphi^n-\psi^n & \varphi^{n-1}-\psi^{n-1} \end{array} \right)$$ dove abbiamo sfruttato il fatto che $P^{-1}P=I$ e l’identità $\varphi\ \psi=-1\ $. Otteniamo dunque $$F_n=\dfrac{1}{\sqrt5}(\varphi^n-\psi^n)\ .$$
Tra l’altro anche le successioni $f_n=\varphi^n$ e $p_n=\psi^n$ godono della stessa relazione di ricorsione della serie di Fibonacci, infatti poiché sia $\varphi$ che $\psi$ soddisfano l’equazione $\lambda^2=\lambda+1$ si ha $$f_{n+2}=\varphi^{n+2}=\varphi^n\cdot\varphi^2=\varphi^n(\varphi+1)=\varphi^{n+1}+\varphi^n=f_{n+1}+f_n$$ e analogamente per $p_n$.
Ogni serie $a_n$ per cui valga $a_{n+2}=a_{n+1}+a_n$ può essere scritta come combinazione lineare di $f_n$ e $p_n$: $$a_n=\dfrac{1}{\sqrt5}\left[\left(-a_0\psi+a_1\right)\varphi^n+\left(a_0\varphi-a_1\right)\psi^n\right]\ .$$
Ogni serie $a_n$ per cui valga $a_{n+2}=a_{n+1}+a_n$ può essere scritta come combinazione lineare di $f_n$ e $p_n$: $$a_n=\dfrac{1}{\sqrt5}\left[\left(-a_0\psi+a_1\right)\varphi^n+\left(a_0\varphi-a_1\right)\psi^n\right]\ .$$
Ad esempio per i numeri di Lucas $L_0=2$ e $L_1=1$ e si ottiene, semplificando: $$L_n=\varphi^n+\psi^n\ .$$
Per ogni successione di questo tipo (tranne il caso in cui $a_1=a_0\psi$, ovvero $\ a_n\propto\psi^n$) vale $$\lim_{n\to\infty}\dfrac{a_{n+1}}{a_n}=\varphi\ .$$
Post
0 commenti:
Posta un commento