Miguel Angel Carrasco
7 de noviembre de 2022

Introducción

En la literatura y en la web se pueden encontrar varias demostraciones para la fórmula de Binet, pero en mi experiencia algunas de estas demostraciones carecen del formalismo necesario. También hay otras demostraciones en donde el formalismo está presente, sin embargo no suelen ser tan claras. En este artículo trato de balancear estas dos situaciones tratando de usar un lenguaje claro, con el suficiente formalismo, sin obviar u omitir pasos.

La fórmula de Binet es una fórmula explícita para obtener cualquier término de la secuencia de Fibonacci.

La secuencia de Fibonacci

La secuencia de Fibonacci es una famosa sucesión de enteros donde cada término es la suma de los dos términos anteriores, empezando por el $0$ y el $1$, es decir

$$0,1,1,2,3,5,8,13,21,34,55,89,144,...$$

La cual se puede escribir como

$$\begin{array}{rl}{F}_0& =0\\ F_1& =1\\ F_n& =F_{n-1}+F_{n-2},\forall n\in \mathbb{N}\wedge n>1\end{array}$$

La fórmula de Binet

Se le atribuye a Jacques Philippe Marie Binet la siguiente fórmula explícita para obtener $F_n$ de los términos de la secuencia de fibonacci

$$\boxed{F_n=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]}$$

quien la encontró en 1843. Aunque de hecho, fue descubierta en 1718 por el matemático francés Abraham De Moivre (1667–1754) usando funciones generadoras. Fue derivado de forma independiente en 1844 por el ingeniero y matemático francés Gabriel Lamé (1795–1870).

Otra forma de escribir esta fórmula es la siguiente

$$\boxed{F_n=\frac{1}{\sqrt{5}}\left[{\phi }^n-{\psi }^n\right]}$$

donde $\phi =\frac{1+\sqrt{5}}{2}$ y $\psi =\frac{1-\sqrt{5}}{2}$

A $\phi$ se le suele denominar la proporción áurea (Golden ratio en inglés).

Existen unas propiedades entre $\phi$ y $\psi$ muy útiles que usaremos en las siguientes demostraciones. Estas propiedades son las siguientes

1. ${\phi }^{-1}=\psi$
2. ${\psi }^{-1}=-\phi$
3. $\phi =1+{\phi }^{-1}$
4. $\psi =1+{\psi }^{-1}$

Demostración de estas propiedades:

$$\begin{array}{rl}{\phi }^{-1}& =\frac{2}{1+\sqrt{5}}=\frac{2(1-\sqrt{5})}{(1+\sqrt{5})(1-\sqrt{5})}\\ & =\frac{2(1-\sqrt{5})}{1-5}=\frac{-2(1-\sqrt{5})}{4}=-\frac{1-\sqrt{5}}{2}=-\psi \end{array}$$

$$\begin{array}{rl}{\psi }^{-1}& =\frac{2}{1-\sqrt{5}}=\frac{2(1+\sqrt{5})}{(1-\sqrt{5})(1+\sqrt{5})}\\ & =\frac{2(1+\sqrt{5})}{1-5}=\frac{-2(1+\sqrt{5})}{4}=-\frac{1+\sqrt{5}}{2}=-\phi \end{array}$$

$$1+{\phi }^{-1}=1-\psi =1-\frac{1-\sqrt{5}}{2}=\frac{2-1+\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}=\phi$$

$$1+{\psi }^{-1}=1-\phi =1-\frac{1+\sqrt{5}}{2}=\frac{2-1-\sqrt{5}}{2}=\frac{1-\sqrt{5}}{2}=\psi$$

De donde quedan demostradas las propiedades $\square$.

Demostración por inducción fuerte de la fórmula de Binet

Es fácil demostrar que la fórmula de Binet se cumple para todo $n\in \mathbb{N}\cup 0$ usando inducción fuerte.

Para $n=0$ vemos que se cumple

$$\begin{array}{rl}{F}_0& =\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^0-{\left(\frac{1-\sqrt{5}}{2}\right)}^0\right]\\ & =\frac{1}{\sqrt{5}}\left[1-1\right]=\frac{0}{\sqrt{5}}=0\end{array}$$

Para $n=1$ vemos que también se cumple

$$\begin{array}{rl}{F}_1& =\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^1-{\left(\frac{1-\sqrt{5}}{2}\right)}^1\right]\\ & =\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt{5}-1+\sqrt{5}}{2}\right]\\ & =\frac{1}{\sqrt{5}}\left[\frac{2\sqrt{5}}{2}\right]=\frac{\sqrt{5}}{\sqrt{5}}=1\end{array}$$

Ahora supongamos que se cumple para $n=k$, $n=k-1$ y para todo entero anterior a k, mayor o igual a 0, para algún $k$. Vamos a demostrar que eso implica que se cumple para $n=k+1$. Por simplicidad usaremos la forma que usa a $\phi$ y a $\psi$, de tal manera que de acuerdo a nuestra hipótesis de inducción se cumple $F_k=\frac{1}{\sqrt{5}}\left[{\phi }^k-{\psi }^k\right]$ y $F_{k-1}=\frac{1}{\sqrt{5}}\left[{\phi }^{k-1}-{\psi }^{k-1}\right]$. Por lo que entonces

$$\begin{array}{rl}{F}_{k+1}& =F_k+F_{k-1}\\ & =\frac{1}{\sqrt{5}}\left[{\phi }^k-{\psi }^k\right]+\frac{1}{\sqrt{5}}\left[{\phi }^{k-1}-{\psi }^{k-1}\right]\\ & =\frac{1}{\sqrt{5}}\left[{\phi }^k-{\psi }^k+{\phi }^{k-1}-{\psi }^{k-1}\right]\\ & =\frac{1}{\sqrt{5}}\left[{\phi }^k+{\phi }^{k-1}-{\psi }^k-{\psi }^{k-1}\right]\\ & =\frac{1}{\sqrt{5}}\left[({\phi }^k+{\phi }^{k-1})-({\psi }^k+{\psi }^{k-1})\right]\\ & =\frac{1}{\sqrt{5}}\left[{\phi }^k(1+{\phi }^{-1})-{\psi }^k(1+{\psi }^{-1})\right]\end{array}$$

Y de las propiedades explicadas en la sección anterior, dado que $1+{\phi }^{-1}=\phi$ y $1+{\psi }^{-1}=\psi$, tenemos que

$$\begin{array}{rl}{F}_{k+1}& =\frac{1}{\sqrt{5}}\left[{\phi }^k(1+{\phi }^{-1})-{\psi }^k(1+{\psi }^{-1})\right]\\ & =\frac{1}{\sqrt{5}}\left[{\phi }^k\phi -{\psi }^k\psi \right]\\ & =\frac{1}{\sqrt{5}}\left[{\phi }^{k+1}-{\psi }^{k+1}\right]\end{array}$$

Que justamente era lo que queríamos demostrar. $\square$

Derivación de la fórmula de Binet usando álgebra lineal

Aunque hemos demostrado la fórmula de Binet usando inducción fuerte y con ello tenemos la certeza de que dicha fórmula es verdadera, aún no tenemos idea de cómo fue que se obtuvo esa fórmula en primer lugar. Una forma de encontrar esta fórmula es haciendo uso del álgebra lineal.

Notemos primero que podemos escribir $F_2$ y $F_1$ en forma matricial como

$$\left[\begin{array}{c}{F}_2\\ F_1\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]$$

Y observamos que podemos escribir también $F_3$ y $F_2$ como

$$\begin{array}{rl}\left[\begin{array}{c}{F}_3\\ F_2\end{array}\right]& =\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_2\\ F_1\end{array}\right]\\ & =\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]\\ & ={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^2\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]\end{array}$$

Es claro que repitiendo este proceso $n$ veces podemos escribir $F_{n+1}$ y $F_n$ como

$$\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]$$

Ahora, si definimos

$$A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$

Podemos rescribir esta matriz como

$$\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]=A^n\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]$$

Es claro que si encontramos una forma explícita para calcular $A^n$, se obtendrá una fórmula explícita para $F_n$ y $F_{n+1}$. Una forma de simplificar el cálculo de elevar a la potencia $n$ una matriz, es mediante un proceso de diagonalización. Es decir, si podemos encontrar una matriz invertible $P$ y otra matriz $D$ tal que

$$A=PD{P}^{-1}$$

donde $D$ sea una matriz diagonal, es decir de la forma

$$D=\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]$$

Calcular $A^n$ sería muy sencillo, ya que

$$\begin{array}{rl}{A}^n& =(PD{P}^{-1}{)}^n=\stackrel{\text{n veces}}{\overbrace{(PD{P}^{-1})(PD{P}^{-1})\cdots (PD{P}^{-1})}}\\ & =PD(P^{-1}P)D(P^{-1}P)\cdots (P^{-1}P)D{P}^{-1}=P{D}^n{P}^{-1}\end{array}$$

Y como D es una matriz diagonal

$$D^n={\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]}^n=\left[\begin{array}{cc}{\lambda }_1^n& 0\\ 0& {\lambda }_2^n\end{array}\right]$$

por lo que solo tendríamos que elevar a la $n$ los elementos en la diagonal, calcular $P$ y $P^{-1}$ y expandir $PD{P}^{-1}$. Para obtener $P$ y $D$ a partir de $A$ podemos usar el teorema de eigen descomposición. Donde D estaría formada por los eigenvalores de A en los elementos de su diagonal, es decir ${\lambda }_i$ para valores de $i\in 1,2$ serían dichos eigenvalores y $P$ estaría definida como una matriz por bloques de los dos eigenvectores correspondientes a dichos eigenvalores.

$$P=\left[\begin{array}{cc}{\mathbf{v}}_1& {\mathbf{v}}_2\end{array}\right]$$

Donde $$\begin{gathered} \mathbf{v}1=\left[\begin{array}{c}{v}_{11}\\ v_{12}\end{array}\right] \\ \mathbf{v}2=\left[\begin{array}{c}{v}_{21}\\ v_{22}\end{array}\right] \end{gathered}$$

Y por lo tanto

$$P=\left[\begin{array}{cc}{v}_{11}& v_{21}\\ v_{12}& v_{22}\end{array}\right]$$

Donde ${\mathbf{v}}_1$ y ${\mathbf{v}}_2$ serían esos eigenvectores correspondientes a los eigenvalores ${\lambda }_1$ y ${\lambda }_2$ respectivamente.

La diagonalización es posible gracias a que sabemos que los eigenvalores y eigenvectores de A cumplen por definición que

$$A{\mathbf{v}}_{\mathbf{i}}={\lambda }_i{\mathbf{v}}_{\mathbf{i}}\forall i\in 1,2$$

De donde podemos ver que

$$\begin{array}{rl}AP& =A\left[\begin{array}{cc}{\mathbf{v}}_1& {\mathbf{v}}_2\end{array}\right]\\ & =\left[\begin{array}{cc}A{\mathbf{v}}_1& A{\mathbf{v}}_2\end{array}\right]\\ & =\left[\begin{array}{cc}{\lambda }_1{\mathbf{v}}_1& {\lambda }_2{\mathbf{v}}_2\end{array}\right]\\ & =\left[\begin{array}{cc}{\lambda }_1{v}_{11}& {\lambda }_2{v}_{21}\\ {\lambda }_1{v}_{12}& {\lambda }_2{v}_{22}\end{array}\right]\\ & =\left[\begin{array}{cc}{v}_{11}& v_{21}\\ v_{12}& v_{22}\end{array}\right]\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]\\ & =PD\end{array}$$

Y multiplicando $P^{-1}$ por la derecha ambos lados de la ecuación obtenemos

$$\begin{array}{rl}AP(P^{-1})& =PD(P^{-1})\\ A& =PD{P}^{-1}\end{array}$$

Ahora bien, dado que $A{\mathbf{v}}_{\mathbf{i}}={\lambda }_i{\mathbf{v}}_{\mathbf{i}}\forall i\in 1,2$, tenemos que

$$\begin{array}{rl}A{\mathbf{v}}_{\mathbf{i}}-{\lambda }_i{\mathbf{v}}_{\mathbf{i}}& =0\forall i\in 1,2\end{array}$$

donde $0$ es el vector cero y factorizando ${\mathbf{v}}_{\mathbf{i}}$

$$(A-{\lambda }_{i}I){\mathbf{v}}_{\mathbf{i}}=0\forall i\in 1,2$$

donde $I$ es la matriz identidad. Vemos que solo puede cumplirse esta identidad ya sea cuando todo ${\mathbf{v}}_{\mathbf{i}}$ sea igual a $0$ o bien cuando $\det (A-{\lambda }_{i}I)=0$. Los vectores cero no nos serían útiles para diagonalizar, además de que ningún eigenvector puede ser el vector 0, por lo que usaremos la segunda identidad para encontrar los valores de ${\lambda }_i$ y ${\mathbf{v}}_{\mathbf{i}}$.

Por lo tanto para encontrar los valores de ${\lambda }_i$ vemos que

$$\begin{array}{rlr}\det (A-\lambda I)& =\det \left(\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]-\left[\begin{array}{cc}\lambda & 0\\ 0& \lambda \end{array}\right]\right)& =0\\ & =\det \left(\left[\begin{array}{cc}1-\lambda & 1\\ 1& -\lambda \end{array}\right]\right)& =0\\ & ={\lambda }^2-\lambda -1& =0\end{array}$$

${\lambda }^2-\lambda -1$ es el denominado polinomio característico. Resolviendo para $\lambda$ encontrando las raíces del polinomio tenemos que

$$\begin{gathered} {\lambda }_1=\frac{1+\sqrt{5}}{2}=\phi \\ {\lambda }_2=\frac{1-\sqrt{5}}{2}=\psi \end{gathered}$$

Ahora tenemos que encontrar los eigenvectores correspondientes para cada ${\lambda }_i$.

Empezando por ${\lambda }_1$ (que recordemos ${\lambda }_1=\phi$) tenemos que

$$\begin{array}{rl}(A-{\lambda }_{1}I){\mathbf{v}}_1& =0\\ \left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]-\left[\begin{array}{cc}\phi & 0\\ 0& \phi \end{array}\right]\left[\begin{array}{c}{v}_{11}\\ v_{12}\end{array}\right]& =\left[\begin{array}{c}0\\ 0\end{array}\right]\\ \left[\begin{array}{cc}1-\phi & 1\\ 1& -\phi \end{array}\right]\left[\begin{array}{c}{v}_{11}\\ v_{12}\end{array}\right]& =\left[\begin{array}{c}0\\ 0\end{array}\right]\end{array}$$

Y de las propiedades anteriores, sabemos que $1-\phi =\psi$, así como ${\psi }^{-1}=-\phi$ por lo que

$$\left[\begin{array}{cc}\psi & 1\\ 1& {\psi }^{-1}\end{array}\right]\left[\begin{array}{c}{v}_{11}\\ v_{12}\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right]$$

Reduciendo el sistema de ecuaciones resultante con Gauss-Jordan

$$\left(\begin{array}{ccc}\psi & 1& 0\\ 1& {\psi }^{-1}& 0\end{array}\right)\stackrel{\psi R_2\to R_2}{\to }\left(\begin{array}{ccc}\psi & 1& 0\\ \psi & 1& 0\end{array}\right)\stackrel{R_1-R_2\to R_2}{\to }\left(\begin{array}{ccc}\psi & 1& 0\\ 0& 0& 0\end{array}\right)$$

De donde vemos que

$$\psi v_{11}+v_{12}=0$$

y podemos tomar $v_{12}=1$ por conveniencia de tal manera que

$$v_{11}=\frac{-1}{\psi }=-{\psi }^{-1}=\phi$$

por lo que el eigenvector ${\mathbf{v}}_1$ tomaría la forma

$${\mathbf{v}}_1=\left[\begin{array}{c}\phi \\ 1\end{array}\right]$$

Para el caso del eigenvalor ${\lambda }_2$ (recordando que ${\lambda }_2=\psi$) tendríamos que $$\begin{array}{rl}(A-{\lambda }_{2}I){\mathbf{v}}_2& =0\\ \left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]-\left[\begin{array}{cc}\psi & 0\\ 0& \psi \end{array}\right]\left[\begin{array}{c}{v}_{21}\\ v_{22}\end{array}\right]& =\left[\begin{array}{c}0\\ 0\end{array}\right]\\ \left[\begin{array}{cc}1-\psi & 1\\ 1& -\psi \end{array}\right]\left[\begin{array}{c}{v}_{21}\\ v_{22}\end{array}\right]& =\left[\begin{array}{c}0\\ 0\end{array}\right]\end{array}$$

Y por la simetría de la situación es fácil concluir que

$${\mathbf{v}}_2=\left[\begin{array}{c}\psi \\ 1\end{array}\right]$$

De donde

$$P=\left[\begin{array}{cc}\phi & \psi \\ 1& 1\end{array}\right]$$

y por lo tanto

$$P^{-1}=\frac{1}{\det (P)}\text{adj}(P)$$

y dado que

$$\begin{array}{rl}\det (P)& =\phi -\psi \\ & =\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\\ & =\frac{1+\sqrt{5}-1+\sqrt{5}}{2}\\ & =\frac{2\sqrt{5}}{2}\\ & =\sqrt{5}\end{array}$$

y que

$$\text{adj}(P)=\left[\begin{array}{cc}1& -\psi \\ -1& \phi \end{array}\right]$$

entonces

$$P^{-1}=\frac{1}{\sqrt{5}}\left[\begin{array}{cc}1& -\psi \\ -1& \phi \end{array}\right]$$

por lo que entonces dado que $A^n=P{D}^n{P}^{-1}$ tenemos que $$\begin{array}{rl}{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n& =\left[\begin{array}{cc}\phi & \psi \\ 1& 1\end{array}\right]{\left[\begin{array}{cc}\phi & 0\\ 0& \psi \end{array}\right]}^n\frac{1}{\sqrt{5}}\left[\begin{array}{cc}1& -\psi \\ -1& \phi \end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{cc}\phi & \psi \\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\phi }^n& 0\\ 0& {\psi }^n\end{array}\right]\left[\begin{array}{cc}1& -\psi \\ -1& \phi \end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{cc}{\phi }^{n+1}& {\psi }^{n+1}\\ {\phi }^n& {\psi }^n\end{array}\right]\left[\begin{array}{cc}1& -\psi \\ -1& \phi \end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{cc}{\phi }^{n+1}-{\psi }^{n+1}& \psi {\phi }^{n+1}-\phi {\psi }^{n+1}\\ {\phi }^n-{\psi }^n& \psi {\phi }^n-\phi {\psi }^n\end{array}\right]\end{array}$$

Finalmente vemos que $$\begin{array}{rl}\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]& ={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{cc}{\phi }^{n+1}-{\psi }^{n+1}& \psi {\phi }^{n+1}-\phi {\psi }^{n+1}\\ {\phi }^n-{\psi }^n& \psi {\phi }^n-\phi {\psi }^n\end{array}\right]\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{cc}{\phi }^{n+1}-{\psi }^{n+1}& \psi {\phi }^{n+1}-\phi {\psi }^{n+1}\\ {\phi }^n-{\psi }^n& \psi {\phi }^n-\phi {\psi }^n\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{c}{\phi }^{n+1}-{\psi }^{n+1}\\ {\phi }^n-{\psi }^n\end{array}\right]\end{array}$$

De donde claramente tenemos que

$$F_{n+1}=\frac{1}{\sqrt{5}}\left[{\phi }^{n+1}-{\psi }^{n+1}\right]$$

y

$$\boxed{F_n=\frac{1}{\sqrt{5}}\left[{\phi }^n-{\psi }^n\right]}$$

Que es precisamente la fórmula de Binet $\square$.

Referencias

• Wikipedia: Fibonacci Number
• Wikipedia: Golden Ratio
• Wikipedia: Characteristic polynomial
• Wolfram: Eigen Decomposition
• Wolfram: Eigen Decomposition Theorem
• Hyper-Textbook: Optimization Models and Applications, L. El Ghaoui, EECS Department, UC Berkeley - Spectral Theorem section
• Fibonacci and Lucas Numbers with Applications, Volume 1, 2nd Edition - Thomas Koshy