Una fórmula directa para los Números de Fibonacci

Los Números de Fibonacci son aquellos que se obtienen de la siguiente fórmula recursiva:
$$\begin{align}
x_0 &=1 \\
x_1 &=1 \\
x_{n+2} &=x_n+x_{n+1}
\end{align}$$
Esto significa que, considerando que los dos primeros números en la lista son \(1\) y \(1\), cada número se obtiene sumando los dos anteriores. Así que la lista comienza:
$$1,1,2,3,5,8,13,21,\dots$$
La fórmula anterior es recursiva porque arroja números en términos de otros números anteriores de la misma lista. Por supuesto es importante conocer los primeros dos números para obtener los sucesivos. Pero ¿existe una fórmula directa de los Números de Fibonacci? Con "fórmula directa" me refiero a una fórmula que nos diga cuál es el número de la lista que está en el lugar \(n\), y que dependa sólo de \(n\). La respuesta es afirmativa, y a continuación deduciré esta fórmula directa utilizando sobretodo el concepo de diagonalización de una matriz cuadrada.

Lo primero es escribir la fórmula recursiva de otra manera, usando el producto de matrices:
$$
\begin{pmatrix}
x_{n+1} \\ x_{n+2}
\end{pmatrix}
=
\begin{pmatrix}
0 & 1 \\ 1 & 1
\end{pmatrix}
\begin{pmatrix}
x_n \\ x_{n+1}
\end{pmatrix}
$$
Usando una notación más compacta:
$$V_{n+1}=AV_n $$
Esto es de nuevo una fórmula recursiva, con la ventaja de que puede obtenerse una fórmula más directa:
$$V_n=A^nV_0 $$
donde
$$V_0=
\begin{pmatrix}
0\\ 1
\end{pmatrix}
$$
Listo: esto nos daría una fórmula directa para el número \(x_n\) de la sucesión de Fibonacci. Pero hay un problema: necesitamos conocer la matriz \(A^n\). Para esto necesitamos también una fórmula directa. Y aquí es donde entra el concepto de diagonalización.

Se dice que una matriz cuadrada \(A\) es diagonalizable si existe una matriz invertible \(P\) tal que la matriz \(D=P^{-1}AP\) sea una matriz diagonal, es decir, una matriz que tiene todas sus entradas iguales a cero, excepto posiblemente en la diagonal principal. La teoría nos dice que de ser posible esto, las entradas de la diagonal son precisamente las raíces reales de su polinomio característico:
$$\det(xI-A)$$
Si estas raíces son distintas, siempre es posible llevar a cabo la diagonalización. Una vez que se tienen estos valores queda establecida la matriz diagonal \(D=PAP^{-1}\) y por tanto la matriz \(D^n\), que consta de las potencias \(n\)-ésimas de cada elemento de la diagonal de \(D\). Con esto puede obtenerse \(A^n\) como sigue:
$$A^n=(PDP^{-1})^n=PD^nP^{-1}$$
En nuestro caso, el polinomio característico de \( A=\big(\begin{smallmatrix} 0 & 1 \\ 1 & 1 \end{smallmatrix}\big)\) es:
$$\det\begin{pmatrix} x & -1 \\ -1 & x-1 \end{pmatrix} =x(x-1)-1=x^2-x-1$$
cuyas raíces son los números:
$$\varphi=\frac{1+\sqrt{5}}{2}\text{ ,   } 1-\varphi=\frac{1-\sqrt{5}}{2}$$
\(\varphi\) es el famoso número áureo o proporción áurea, que es la proporción entre los lados mayor y menor de un rectángulo áureo, aquel que tiene la propiedad de que al recortar un cuadrado queda otro rectángulo con la misma proporción entre sus lados:

En la figura, el rectángulo de lado mayor \(A+B\) y lado menor \(A\) es áureo, así como el rectángulo de lado mayor \(A\) y lado menor \(B\) si se cumple que:

$$\frac{A+B}{A}=\frac{A}{B}$$

En ese caso \(\varphi=\frac{A}{B}\) es el número áureo, que satisface por lo tanto que:

$$1+\frac{1}{\varphi}=\varphi$$

o lo que es lo mismo:

$$\varphi^2-\varphi-1=0$$

es decir, \(\varphi\) es la raíz positiva del polinomio

$$x^2-x-1=0$$

que es el polinomio característico de la matriz \(A\). La raíz negativa es precisamente \(1-\varphi\).

La teoría nos dice que podemos construir una matriz \(P\) invertible tal que \(P^{-1}AP\) es la matriz diagonal

$$D=\begin{pmatrix} \varphi & 0 \\ 0 & 1-\varphi \end{pmatrix}$$

El procedimiento consiste en encontrar vectores columna distintos de cero que sean cada uno solución respectivamente de los sistemas de ecuaciones:

$$\begin{pmatrix} -\varphi & 1 \\ 1 & 1-\varphi \end{pmatrix}\begin{pmatrix}x \\ y \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \end{pmatrix}$$

y

$$\begin{pmatrix} \varphi-1 & 1 \\ 1 & \varphi \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \end{pmatrix}$$

Podemos considerar entonces como soluciones de estos respectivos sistemas a los vectores columna:

$$\begin{pmatrix} \varphi-1 \\ 1 \end{pmatrix} \text{  y  } \begin{pmatrix} -\varphi \\ 1 \end{pmatrix}$$

para construir la matriz

$$P=\begin{pmatrix} \varphi-1& -\varphi  \\ 1 & 1 \end{pmatrix}$$

cuya matriz inversa es

$$P^{-1}=\frac{1}{2\varphi-1}\begin{pmatrix} 1& \varphi  \\ -1 & \varphi-1 \end{pmatrix}$$

es decir

$$PP^{-1}=P^{-1}P=\begin{pmatrix} 1& 0  \\ 0 & 1 \end{pmatrix}$$

En efecto, puede corroborarse que

$$P^{-1}AP=\begin{pmatrix} \varphi & 0 \\ 0 & 1-\varphi \end{pmatrix}$$

Ahora obtengamos la enésima potencia de la matriz diagonal anterior:

$$D^n=\begin {pmatrix} \varphi^n & 0 \\ 0 & (1-\varphi)^n \end{pmatrix} $$

Por tanto, podemos obtener:

$$A^n = \frac{1}{2\varphi-1} \begin{pmatrix}\varphi-1& -\varphi  \\ 1 & 1 \end{pmatrix} \begin {pmatrix} \varphi^n & 0 \\ 0 & (1-\varphi)^n \end{pmatrix} \begin{pmatrix} 1& \varphi  \\ -1 & \varphi-1 \end{pmatrix}$$

es decir, haciendo las cuentas:

$$A^n = \frac{1}{\sqrt{5}}\begin{pmatrix} (\varphi-1)\varphi^n+\varphi(1-\varphi)^n & (\varphi-1)\varphi^{n+1}+\varphi(1-\varphi)^{n+1} \\ \varphi^n-(1-\varphi)^n & \varphi^{n+1}-(1-\varphi)^{n+1} \end{pmatrix}$$

Sustituyendo en la fórmula

$$V_n=A^nV_0 $$

y considerando \(x_{n+1}\) obtenemos:

$$ x_{n+1}=\frac{\varphi^{n+1}-(1-\varphi)^{n+1}}{\sqrt{5}}$$

o bien, ¡ la fórmula directa para el término  \(x_n\) de la sucesión de Fibonacci !:

$$ x_n=\frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}}$$