Evaluación con ayuda de un tutor

¿Sólo se puede calcular la sucesión de Fibonacci de forma recursiva?

Anteriormente observaste que la sucesión de Fibonacci es recursiva. Es decir, para conocer un número de Fibonacci correspondiente al índice \(n\) es necesario, en general, calcular los anteriores. ¿Será posible convertir la sucesión de su forma recursiva a una no recursiva? Esto implicaría contar con una fórmula que permitiera conocer \(F_n\) sólo en términos de \(n\), aún sin contar con \(F_{n-2}\) y \(F_{n-1}\).

Para ello, se estudiará primero el comportamiento de las potencias de \(\Phi\) y \(-\phi\), y luego se usarán éstas para la eventual construcción de la fórmula buscada.

Las potencias de \(\Phi\) y \(-\phi\)

Observa las siguientes potencias de \(\Phi\). Compruébalas tanto algebráicamente como con tu calculadora y haz llegar tus resultados a tu tutor. Recuerda que \(\Phi=\frac{1+\sqrt{5}}{2}\).

Seguro notas que los coeficientes en las ecuaciones anteriores son números de Fibonacci. Así, ya cuentas con las expresiones para las primeras 5 potencias de \(\Phi\). Y puedes conjeturar que \(\Phi^n=F_{n-2}+F_{n-1}\Phi\). Pero para demostrarlo para cualquier \(n\), debes adoptar un abordaje más general.

Ahora nota las potencias de \(-\phi\). Compruébalas tanto algebráicamente como con tu calculadora y haz llegar tus resultados a tu tutor. Recuerda que \(\phi=\frac{1}{\Phi}\) y nota que también lo puedes expresar como \(\phi=\frac{-1+\sqrt{5}}{2}\).

En este caso, los coeficientes también son números de Fibonacci y podrías conjeturar que \((-\phi)^n=F_{n-2}+F_{n-1}(-\phi)\). Pero, nuevamente, para generalizar esta ecuación para cualquier \(n\), deberás adoptar un abordaje más general.

Como conoces una relación recursiva de los números de Fibonacci, podrías aprovechar esto para usar la inducción matemática como una forma de generalizar esto y, así, saber a ciencia cierta que la fórmula es válida independiente del índice usado. Recuerda que la inducción matemática consiste en tres pasos principales, a saber:

  1. Determinar que la fórmula es válida para \(n=2\). Normalmente se hace la comprobación para \(n=1\), pero en nuestro caso particular, como no existe \(F_{-1}\), es necesario empezar con \(n=2\).
  2. Suponer que la fórmula es válida para un entero \(k\).
  3. Corroborar, usando la fórmula para \(k\), que también es válida para el siguiente entero (esto es, para \(k+1\)).

Tarea

  1. Escribe un texto para enviar a tu asesor demostrando por inducción la validez de la fórmula para \((\Phi)^n\).
  2. Escribe un texto para enviar a tu asesor demostrando por inducción la validez de la fórmula para \((-\phi)^n\).

Deducción de la fórmula de Binet

La fórmula de Binet es una fórmula para calcular la sucesión de Fibonacci de una manera no recursiva. Hay muchas formas de demostrarla, pero en este caso podemos aprovechar las fórmulas anteriormente demostradas para \((\Phi)^n\) y \((-\phi)^n\) para deducir la fórmula de Binet.

Para ello te proporcionamos algunas sugerencias para atacar el problema:

  1. Intenta combinar las expresiones para \((\Phi)^n\) y \((-\phi)^n\) mediante una operación (por ejemplo, suma o resta) de tal forma que desaparezcan los términos que involucran a \(F_{n-2}\). Estos términos involucran el cálculo de los números de Fibonacci que, para calcularse, requieren recursividad. Es por ello que nos conviene deshacernos de ellos. Tal vez te quede un término que involucre \(F_{n-1}\), pero este te conviene que permanezca, pues es el que eventualmente despejarás para obtener la fórmula no recursiva de la sucesión.
  2. Cuando obtengas dicha ecuación, notarás que relaciona a \(F_{n-1}\), \(\Phi\), \(-\phi\), \((\Phi)^n\) y \((-\phi)^n\). De esta fórmula, despeja a \(F_{n-1}\).
  3. En lo posible, trata de reducir los términos que te queden que involucran \(\Phi\) y \(\phi\) usando sus definiciones respectivas (\(\frac{1+\sqrt{5}}{2}\) y \(\frac{-1+\sqrt{5}}{2}\)). Con ello tendrás una fórmula reducida que te indique el número \(F_{n-1}\) de la sucesión sólo en función de algunas constantes, y con una única variable \(n\). Es decir, una fórmula no recursiva.
  4. Aunque la expresión que obtengas será para \(F_{n-1}\), puedes recorrer los índices para obtener la correspondiente a \(F_n\).

Tarea

Envía a tu tutor tu intento de la deducción de la fórmula no recursiva para obtener \(F_n\).