Dado un número de Fibonacci, busque el siguiente número de Fibonacci

Question

La secuencia de Fibonacci es <span class="math-container">%-%-%</span>, donde cada término después de los dos primeros es la suma de los dos términos anteriores.

¿Podemos encontrar el siguiente número de Fibonacci si se nos da algún número de Fibonacci?

Por ejemplo, si <span class="math-container">%-%-%,</span> entonces su respuesta debe ser <span class="math-container">%-%-%</span> porque <span class="math-container">%-%-%</span> es el siguiente número de Fibonacci después de <span class="math-container">%-%-%</span>.

Answer 1

Dado un número Fibonacci $n$, vamos a $m$ ser el siguiente número de Fibonacci. La secuencia de Fibonacci tiene la propiedad de que para cualquier tres elementos $r,s,t$, tenemos $rt=s^2\pm 1$ (la prueba es por inducción, que usted puede intentar el $-$ la elección de los signos de los suplentes). Y sabemos que el anterior número Fibonacci es $m-n$. Así tenemos $$m(m-n)=n^2\pm 1$$ Esta es una ecuación de segundo grado en $m$, con soluciones $m=\frac12(n\pm\sqrt{5n^2\pm 4})$. Sabemos que $m\ge n$, lo $m$ debe ser igual a $\frac12(n+\sqrt{5n^2\pm 4})$. Y podemos elegir entre las $+4$ e $-4$ porque sólo uno de $\sqrt{5n^2+4}$ e $\sqrt{5n^2-4}$ puede ser un número entero (con la única excepción de la de $n=1$).

Así que la respuesta es que cualquiera de $\frac12(n+\sqrt{5n^2+4})$ e $\frac12(n+\sqrt{5n^2-4})$ es un número entero.

Tenga en cuenta que la única excepción de la $n=1$ se produce dos veces en la secuencia de Fibonacci, por lo que de hecho hay dos respuestas posibles en este caso.

Answer 2

La relación de dos entradas consecutivas en la secuencia de Fibonacci se aproxima rápidamente a <span class="math-container">%-%-%</span>. Por lo tanto, si multiplicas tu número por <span class="math-container">%-%-%</span> y redondeas al entero más cercano, obtendrás el siguiente término a menos que estés al principio de la secuencia.

Answer 3

$n\in\mathbb{N}$ es un número de Fibonacci iff $5n^2-4$ o $5n^2+4$ es un cuadrado. En el primer caso, $n=F_{2k+1}$ mientras que en el segundo caso $n=F_{2k}$. Asumiendo $n\geq 2$, en el primer caso, $F_{2k+2}=\lfloor \varphi n \rfloor$ y en el último caso, $F_{2k+1}=\lceil \varphi n\rceil $, con $\varphi=\frac{1+\sqrt{5}}{2}$.

Ejemplo: si $n=8$ tenemos que $5\cdot 8^2+4=18^2$, por lo tanto $n$ es un número de Fibonacci, incluso con el índice y el siguiente número de Fibonacci es $\lceil 8\varphi \rceil =13$.

Answer 4

A lo largo de líneas similares a Mateo Daly respuesta:

Binet la fórmula se obtiene un valor exacto para la n-esima número Fibonacci, donde la numeración comienza con $F_0=0$ e $F_1=1$:

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

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

$=\phi^n - (\frac{-1}{\phi})^n$, donde $\phi = \frac{1+\sqrt{5}}{2}$ (usando la identidad que $\phi-1=\frac{1}{\phi}$, que es fácil de probar).

Desde allí es fácil demostrar que para $n>2$, $|$registro$_\phi(F_n\sqrt{5})-n|<0.5$. (Sugerencia: como $n$ se hace más grande, el primero de estos dos términos se hace muy grande y el segundo va a cero.)

Si $F_n=1$ obviamente la pregunta es incontestable, y si $F_n=0$ es trivial. Si $F_n>1$ entonces $n>2$ y así podemos calcular $n$ por redondeo de registro de$_\phi(F_n\sqrt{5})$ al entero más cercano.

Ahora tenemos $n$, basta con aplicar la fórmula de Binet en los delanteros dirección y hemos terminado.