Fibonacci Invertido

[carroza]

Hola a todos.

Por el titulo del hilo no penseis que quiero cuestionar la orientación sexual de Leonardo Pisano, tambien conocido como Fibonacci.

Conoceréis la serie de Fibonacci: 1,1,2,3,5,8,13, etc en la que cada término se obtiene como la suma de los dos anteriores.

Series de Fibonacci hay muchas, tantas como parejas de números iniciales podemos considerar. Por ejemplo, 1,3,4,7,11, 18, etc. Incluso podemos considerar numero no enteros:
1, 1.212, 2.212, 3.424,5.636 etc

Partiendo de dos numeros iniciales, es muy facil obtener todos los numeros siguientes de la sucesión.

Lo que no es tan facil es hacer el problema invertido.

Por ejemplo, imaginad que queremos una serie de Fibonacci, en la que el primer número sea 1, y el décimo número sea 100.
El problema consiste en encontrar el segundo número, tal que cuando reconstruya la serie, me salga que el décimo número sea 100. Podeis comprobar que el numero que sale es 2.3235.


En general, el problema que os planteo es el siguiente: Enconrar una formula para obtener el segundo término de una sucesión de Fibonacci, contando con que el primero sea 1, de tal forma que el valor del término n sea M. Ya os aviso que hay una formula muy sencilla, muy precisa para n grande (de 10 en adelante).

Un saludo

[Abdulai]

Ocultar contenido

Mostrar solución Ocultar solución

Consideremos la sucesión de Fibonacci definida como 0,1,1,2,3,5,8,13.... ($F(0)=0\;,F(1)=1$

Definimos $H(n) = \alpha F(n) + F(n+1)$ que verifica $H(n) = H(n-1) + H(n-2)$ y $H(0)=1$

$\therefore\quad H(9) = \alpha F(9) + F(10 \;\;\longrightarrow\;\; \alpha=\dfrac{H(9)-F(10)}{F(9)}$
($H(9)$ es el décimo término)

Entonces el 2do término debe ser: $H(1) = \dfrac{H(9)-F(10)}{F(9)}F(1) + F(2) = \dfrac{H(9)-F(10)+F(9)}{F(9)} = \dfrac{H(9)-F(8)}{F(9)}$

Siendo $H(9)=100\;,\;F(8)=21\;,\;F(9)=34 \;\;\longrightarrow\;\;H(1)=\dfrac{79}{34}$

Para valores grandes es mejor usar la fórmula explícita de la sucesión de Fibonacci

[Jaime Rudas]

Ocultar contenido

Mostrar solución Ocultar solución

Llamemos Fx(n) al término n de la sucesión de Fibonacci cuando el primer término es 1 y el segundo, x. Entonces tenemos

n.........Fx(n)
1.........1
2.........x
3.........1+x
4.........1+2x
5.........2+3x
6.........3+5x
7.........5+8x
8.........8+13x
:::::::::::::::::::::
:::::::::::::::::::::
n.........$F_1(n-2)+F_1(n-1)x$

De donde nos resulta:

$M=F_1(n-2)+F_1(n-1)x$

$x=\dfrac{M-F_1(n-2)}{F_1(n-1)}$

Ahora, hay también una fórmula para $F_1(n)$

$F_1(n)=\dfrac{\phi^n-(1-\phi)^n}{\sqrt 5}$

donde $\phi$ es el número áureo

$\phi=\dfrac{1+\sqrt 5}2$

[teclado]

Ocultar contenido

Mostrar solución Ocultar solución

Igual es un poco redundante, pero partiendo de

$f(n) = f(n-1) + f(n-2)$

Puede escribirse como

$<br /> \begin{aligned}<br /> f(n) &= a_1f(n-1) + a_0f(n-2)\\<br /> a_0 &= 1\\<br /> a_1 &= 1<br /> \end{aligned}<br />$

Aplicando lo primero a $f(n-1)$:

$<br /> \begin{aligned}<br /> f(n) &= (a_1+a_0)f(n-2) + a_1f(n-3) = a_2f(n-2) + a_1f(n-3)\\<br /> a_2 &= a_1 + a_0<br /> \end{aligned}<br />$

En general,

$<br /> \begin{aligned}<br /> f(n) &= a_kf(n-k) + a_{k-1}f(n-k-1)\\<br /> f(n) &= (a_k+a_{k-1})f(n-k-1) + a_kf(n-k-2)\\<br /> a_{k+1} &= a_k+a_{k-1}<br /> \end{aligned}<br />$

La sucesión $\{a_k\}_{k=0}$ es la sucesión clásica de Fibonacci, con $a_0=a_1=1$, que supongo que conocemos, y podemos escribir aplicando lo anterior para $k=n-1$, lo siguiente

$f(n) = a_{n-1}f(1) + a_{n-2}f(0)$

Como el 10 elemento de la sucesión que buscamos es $f(9)$ (dado que comenzamos a contar desde 0), y recordando $\{a_k\} = \{1,1,2,3,5,8,13,21,34,55...\}$

$f(9) = 34f(1) + 21f(0)$

y

$f(1) = \frac{f(9)-21f(0)}{34} = \frac{100-21}{34} = \frac{79}{34} \approx 2,32352941176$

[Richard R Richard]

Ocultar contenido

Mostrar solución Ocultar solución

Si defino una función generadora de la sucesión de fibonacci con el segundo elemento igual a la unidad llamémosle $r=1$

$F(i,r)= F(i,1)=$ devuelve el elemento i de la sucesión de fibonacci cuando $r=1$

entonces sabemos que $M$se puede escribir en función de $n$ de la siguiente manera cuando $r$ es cualquier valor mayor a cero

$M=F(n-1, 1) K+F(n-2, 1)$


entonces $K =\dfrac{M-F(n-2, 1)}{F(n-1, 1)}$

[carroza]

Hola.

Gracias por vuestras respuestas y por participar.

La fórmula muy sencilla que os pedía (aproximada, pero muy buena para n grande), no requiere evaluar la serie de Fibonacci canónica para n.
Imaginaros que os pidiera el caso de M=100000, n = 938. Sería bastante aburrido de calcular 1,1,2,3 ... hasta el término 938.

A partir del desarrollo de Jaime, puede obtenerse un resultado compacto, valido para cualquier n, mejor quen el que yo tenía previsto. Enhorabuena, Jaime

Un saludo

[carroza]

Pongo la solución que to tenía en la cabeza

Ocultar contenido

Mostrar solución Ocultar solución

Las series de Fibonacci, efectivamente, está muy relacionada con el número aureo. Para ello, imaginemos que queremos obtener una progresión geométrica, $a_1= x, a_2=x^2, a_3= x^3 \dots a_n = x^n \dots$, que además cumpla la condición de Fibonacci que $a_n + a_{n+1} = a_{n+2}$.

Obtenemos dos soluciones: $x_1= {1 + \sqrt{5} \over 2} = \varphi \simeq 1.618$, que es la razón aurea, y $x_2= {1 - \sqrt{5} \over 2} = (1-\varphi) = {-1 \over \varphi} \simeq -0.618$, que es su inversa, cambiada de signo.

A partor de estas dos soluciones, cualquier serie que cumpla la condición de de Fibonacci, $a_n + a_{n+1} = a_{n+2}$, puede ponerse como una combinación de estas dos series geométricas:
$a_n = \alpha \varphi^{n-1} + \beta ({-1 \over \varphi} )^{n-1}$. De esta expresión, los valores de los coeficientes $\alpha, \beta$ pueden obtenerse de los dos primeros términos de la sucesión: $a_1 = \alpha + \beta$, $a_2 = \alpha \varphi - \beta / \varphi = (\alpha + \beta) \varphi - \beta =a_1 (\varphi -1) + \alpha)$.

A partir de la expresión general, $a_n = \alpha \varphi^{n-1} + \beta ({-1 \over \varphi} )^{n-1}$, puede verse que para n moderadamente grande, el primér término se hace mucho más grande que el segundo, con lo cual, con muy buena aproximación $a_n \simeq \alpha \varphi^{n-1}$, con lo que $\alpha \simeq a_n / \varphi^{n-1}$, y
$a_2 = a_1 (\varphi - 1) + a_n / \varphi^{n-1}$.

Como habeis indicado, esta expresión se puede hacer valida para todo n escribiendo $a_n = \alpha \varphi^{n-1} + (a_1 - \alpha) ({-1 \over \varphi} )^{n-1}$, de donde despejamos $\alpha = {a_n - a_1 ({-1 \over \varphi} )^{n-1} \over \varphi^{n-1} + ({-1 \over \varphi} )^{n-1} }$

saludos, y gracias por jugar