¿Dadas $n$ y $\newcommand{\Fib}{\mathrm{Fib}} \Fib(n)$, es posible calcular el número anterior en la secuencia de Fibonacci - $\Fib(n-1)$ utilizando matemáticas de enteros en tiempo constante? En otras palabras, creo que estoy en busca de una formula de forma cerrada.
Por ejemplo: da $n=10$ y $\Fib(10)=55$, quisiera determinar que $\Fib(9)=34$ sin usar $\Fib(7) + \Fib(8)$.
Por la Fórmula de Binet, sabemos que $F_n = \dfrac{1}{\sqrt{5}}\left(\phi^n-(-\phi)^{-n}\right) \approx \dfrac{1}{\sqrt{5}}\phi^n$ donde $\phi = \dfrac{1+\sqrt{5}}{2}$.
Usando esta fórmula, se puede disfrutar de la $F_{n-1}$ es el entero más cercano a $\dfrac{1}{\phi} F_n$ grandes $n$
Más rigurosamente, tenemos $F_{n-1} - \dfrac{1}{\phi} F_n = \dfrac{1}{\sqrt{5}}\left(\phi^{n-1}-(-\phi)^{-(n-1)}\right) - \dfrac{1}{\phi\sqrt{5}}\left(\phi^n-(-\phi)^{-n}\right)$ $= -\dfrac{(-\phi)^{-(n-1)}}{\sqrt{5}} - \dfrac{(-\phi)^{-(n+1)}}{\sqrt{5}}$ $= \dfrac{(-\phi)^{-n}}{\sqrt{5}}\left(\phi + \phi^{-1}\right) = (-\phi)^{-n}$.
Así, por $n \ge 2$,$\left|F_{n-1} - \dfrac{1}{\phi} F_n \right| = \phi^{-n} < \frac{1}{2}$, y así, $F_{n-1}$ es el entero más cercano a $\dfrac{1}{\phi}F_n$.
Dividiendo $F_n$ $\phi$ y redondeando el resultado al entero más cercano no debe ser demasiado computacional.
Esta es una nota discrepante sobre algunas de estas respuestas. Soy purposly haciendo de este una respuesta, aunque es realmente una anti respuesta.
El problema con cualquier respuesta que utiliza $\phi$ es que, como se obtiene mayor $n$, $\phi$ debe computar con precisión cada vez más grande. Esto va a tomar no a tiempo constante, para el cómputo del $\phi$ o la multiplicación por $\phi$.
% Toque $\rm\ n\:$es que un número de Fibonacci FIB intervalo $\rm\ [\phi\ n - 1/n,\ \phi\ n + 1/n]\ $ contiene un número entero positivo (el siguiente número de Fibonacci $\rm\ n > 1)$. Esto sigue de las propiedades básicas de fracciones continuadas.
Por ejemplo, $\rm\ 2 \to [2.7,\ 3.7],\ \ 3\to [4.5,\ 5.2],\ \ 5 \to [7.9,\ 8.3]\ \ldots$
Para una prueba ver por ejemplo, $ $ T. Komatsu: el intervalo asociado con un número de fibonacci. $\ $
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
