Sucesión de Fibonacci

La sucesión de Fibonacci se puede escribir de forma recursiva como $$ F_ {1} = F_ {2} = 1 \quad \text{ y} \quad F_ {n} = F_ {n-1} + F_ {n-2} $$ para $ n \geq 3 $. Este es el ejemplo no trivial más simple de una recursividad lineal con coeficientes constantes. También hay una fórmula explícita a continuación. Veamos algunos terminos de esta sucesión
$$1,1,2,3,5,8,13,21,34,\ldots$$

Como ocurre con muchas recursiones lineales, podemos ejecutar la sucesión de Fibonacci hacia atrás resolviendo su relación de recursividad para el término de índice más pequeño, en este caso $ F_ {n-2} = F_ {n} -F_ {n-1} $. Esto nos permite calcular, por ejemplo, que $ F_ {0} = F_ {2} -F_ {1} = 0, F _ {- 1} = 1, F _ {- 2} = – 2, $ y así sucesivamente. Debido a que estos términos precedentes están definidos de forma única por la recursividad, con frecuencia se ve la definición de la secuencia de Fibonacci dada en la forma $ F_ {0} = 0, F_ {1} = 1 $ y $ F_ {n} = F_ {n- 1} + F_ {n-2} $ por $ n \geq 2. $ En general, se puede demostrar que $ F_ {n} = (- 1) ^ {n + 1} F _ {- n} $.

Las proporciones $$ \frac {1} {1}, \frac {2} {1}, \frac {3} {2}, \frac {5} {3}, \frac {8} {5}, \ldots , $$ entre términos sucesivos de la secuencia tienden hacia el límite $$ \frac {1+ \sqrt {5}} {2}, $$ una constante a menudo denotada por $ \varphi $ (la letra griega phi, también escrita $ \phi $) . $ \varphi $ es una solución de la ecuación cuadrática $ x ^ {2} -x-1 = 0 $. La otra raíz es $$ – \varphi ^ {- 1} = \frac {1- \sqrt {5}} {2} $$

Una posible explicación de este hecho es que los números de Fibonacci se dan explícitamente mediante la fórmula de Binet, la cual es $$ F_ {n} = \frac {\varphi ^ {n} – (- \varphi) ^ {- n}} {\sqrt {5}} $$ (Tenga en cuenta que esta fórmula es válida para todos los números enteros $ n$). Se llama así porque fue derivada por el matemático Jacques Philippe Marie Binet, aunque ya la conocía Abraham de Moivre.

La identidad más importante con respecto a la secuencia de Fibonacci es su definición recursiva, $ F_ {n + 1} = F_ {n} + F_ {n-1} $. Las siguientes identidades que involucran los números de Fibonacci pueden probarse por inducción.

  • $ F_ {0} + F_ {1} + \cdots + F_ {n} = F_ {n + 2} -1 $
  • y $ F_ {0} -F_ {1} + F_ {2} – \cdots-F_ {2 n-1} + F_ {2 n} = F_ {2 n-1} -1 $
  • $ F_ {0} ^ {2} + F_ {1} ^ {2} + F_ {2} ^ {2} + \cdots + F_ {n} ^ {2} = F_ {n} \cdot F_ {n + 1} $
  • y $ F_ {n-1} \cdot F_ {n + 1} = F_ {n} ^ {2} + (- 1) ^ {n} $
  • $ F_ {m + n + 1} = F_ {m + 1} \cdot F_ {n + 1} + F_ {m} \cdot F_ {n} $

Prueba de la fórmula de Binet para la sucesión de Fibonacci


Si $ F_ {n} $ es el $ n $-ésimo número de Fibonacci, entonces
$$
F_ {n} = \frac {1} {\sqrt {5}} \left (\left (\frac {1+ \sqrt {5}} {2} \right) ^ {n} – \left (\frac {1- \sqrt {5}} {2} \right) ^ {n} \right)
$$

Prueba

Ya hemos mensionado algo al respecto. Por lo que para ver esta fórmula para general los números de Finonacci, tiene sentido considerar la ecuación
%Para derivar una fórmula general para los números de Fibonacci, podemos mirar la interesante cuadrática
$$
x ^ {2} -x-1 = 0
$$

Como ya se mensiono las raíces de esta cuadrática son $ \frac {1 \pm \sqrt {5}} {2} $. Esta ecuación también se puede escribir como $$x ^ {2} = x + 1$$ A partir de esto, podemos escribir expresiones para todos $ x ^ {n} $:

\begin{eqnarray*} x &=&x \\ x^{2} &=&x+1 \\ x^{3} &=&x \cdot x^{2} =x \cdot(x+1) =x^{2}+x =(x+1)+x =2 x+1 \\ x^{4} &=&x \cdot x^{3} =x \cdot(2 x+1) =2 x^{2}+x =2(x+1)+x =3 x+2 \\ x^{5} &=&5 x+3 \\ x^{6} &=&8 x+5 \\ & \cdots & \\ x^{n} &=&F_{n} x+F_{n-1} \end{eqnarray*}

Sean las raíces de nuestra ecuación original $ \sigma = \frac {1+ \sqrt {5}} {2} $ y $ \tau = \frac {1- \sqrt {5}} {2} $. dado que tanto $ \sigma $ como $ \tau $ son raíces de la cuadrática, ambos deben satisfacer $ x ^ {n} = F_ {n} x + F_ {n-1}. $ Entonces

$$\sigma^{n}=F_{n} \sigma+F_{n-1}$$
$$\tau^{n}=F_{n} \tau+F_{n-1}$$

Restando la segunda ecuación de la primera ecuación se obtiene
$$
\sigma ^ {n} – \tau ^ {n} = F_ {n} (\sigma- \tau) + F_ {n-1} -F_ {n-1}
$$

$$\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}=F_{n}\left(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\right)$$

Esto produce la forma general del n-ésimo número de Fibonacci:

$$
F_{n}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}
$$

Sucesión de Fibonacci y la fórmula de Binet
Etiquetado en:

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

A %d blogueros les gusta esto: