¿Cómo se deriva la fórmula para el enésimo número de Fibonacci?

Answer 1

Esto puede parecer matar una hormiga con un ladrillo de dos toneladas, pero solo para demostrar el poder y la belleza de la maquinaria de funciones generadoras:

Para encontrar, con suerte, la fórmula de forma cerrada para el [math] n [/ math] -th número de Fibonacci en función de [math] n [/ math] razonamos, o asumimos, que existe una función [math] g (x) [/ math] cuya representación en serie de potencia tiene los coeficientes que son exactamente lo que estamos buscando (¿qué tan genial es eso?):

[matemáticas] \ displaystyle g (x) = \ sum_ {n \ geqslant 0} F_n \ cdot x ^ n \ tag {1} [/ matemáticas]

donde [math] F_n [/ math] es el [math] n [/ math] -th número de Fibonacci en forma cerrada como una función de [math] n [/ math].

Siendo un estudiante joven de generación de la ciencia, nunca acepte una relación de recurrencia que no esté definida adecuadamente, con condiciones límite / iniciales. Como tal, tomamos la secuencia de Fibonacci como se define por OEIS en A000045:

[matemáticas] F_ {n + 1} = F_n + F_ {n-1} \ tag {2} [/ matemáticas]

[matemáticas] n \ geqslant 1; \; F_0 = 0; \; F_1 = 1 \ etiqueta {3} [/ matemáticas]

La plantilla:

• multiplique ambos lados de ( 2 ) por [matemáticas] x ^ n [/ matemáticas]:

[matemáticas] F_ {n + 1} x ^ n = F_nx ^ n + F_ {n-1} x ^ n \ tag {4} [/ matemáticas]

• sum ( 4 ) sobre todos los valores legales de [math] n [/ math] para los que se mantiene la relación de recurrencia (use ( 3 )):

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} F_ {n + 1} x ^ n = \ sum_ {n \ geqslant 1} F_nx ^ n + \ sum_ {n \ geqslant 1} F_ {n-1} x ^ n \ tag {5} [/ matemáticas]

• batir ( 5 ) hasta que pueda expresar sus dos lados explícitamente en términos de [matemáticas] g (x) [/ matemáticas]:

Tratemos con el lado derecho de ( 5 ): su primera suma coincide con la suma en ( 1 ) casi exactamente; la única diferencia entre los dos es el valor inicial del índice de suma [math] n [/ math]: it es [matemática] 1 [/ matemática] en ( 5 ) y [matemática] 0 [/ matemática] en ( 1 ). Aquí es donde entran nuestras condiciones iniciales: desde [matemáticas] F_0 = 0 [/ matemáticas] entonces:

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} F_nx ^ n = \ sum_ {n \ geqslant 1} F_nx ^ n + F_0x ^ 0 – F_0x ^ 0 = \ sum_ {n \ geqslant 0} F_nx ^ n – 0 = g (x) \ etiqueta {6} [/ matemáticas]

El subíndice del futuro [matemático] n [/ matemático] -th número de Fibonacci en la segunda suma en el lado derecho del signo igual en ( 5 ) es por [matemática] 1 [/ matemática] unidad menor que la potencia del término [matemático] x ^ n [/ matemático] correspondiente. Entonces, si factorizamos [math] x [/ math] de esa suma tendremos:

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} F_ {n-1} x ^ n = x \ cdot \ sum_ {n \ geqslant 1} F_ {n-1} x ^ {n-1} = x \ cdot g (x) \ tag {7} [/ math]

Ahora ( 5 ) adquiere la siguiente forma:

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} F_ {n + 1} x ^ n = g (x) + x \ cdot g (x) \ tag * {} [/ matemáticas]

Cambiando a la suma en el lado izquierdo del signo igual en ( 5 ) vemos que faltan dos términos que van con [matemática] F_0 [/ matemática] y [matemática] F_1 [/ matemática] y que el subíndice del futuro [math] n [/ math] -th El número de Fibonacci es [math] 1 [/ math] unidad más grande que la potencia del término [math] x ^ n [/ math] correspondiente. Si sumamos y restamos los términos faltantes y multiplicamos y dividimos la suma completa entre [matemáticas] x [/ matemáticas] (y debido a las condiciones iniciales que hemos especificado anteriormente) entonces:

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} F_ {n + 1} x ^ n = \ sum_ {n \ geqslant 1} F_ {n + 1} x ^ n + F_0 – F_0 + F_1 – F_1 = \ etiqueta * {} [/ math]

[matemáticas] \ displaystyle \ dfrac {1} {x} \ Big (\ sum_ {n \ geqslant 1} F_ {n + 1} x ^ {n + 1} + F_1x ^ 1 – F_1x ^ 1 \ Big) = \ dfrac {1} {x} (\ sum_ {n \ geqslant 1} F_nx ^ n – x) = \ tag * {} [/ math]

[matemáticas] \ dfrac {1} {x} (g (x) – x) \ tag * {} [/ matemáticas]

Ahora ( 5 ) se convierte en:

[matemáticas] \ dfrac {g (x) -x} {x} = g (x) – xg (x) \ tag {5} [/ matemáticas]

• lanza tu conciencia culpable al viento y trata [matemáticas] g (x) [/ matemáticas] no como una entidad analítica sino puramente algebraica: resuelve el nuevo ( 5 ) para [matemáticas] g (x) [/ matemáticas]:

[matemáticas] g (x) = \ dfrac {x} {1-xx ^ 2} \ tag {8} [/ matemáticas]

• Intente representar [math] g (x) [/ math] en ( 8 ) como una serie de potencia de cualquier manera que pueda (sin preocuparse por la convergencia y la existencia):

En este caso particular podemos usar el método de fracciones parciales. Resuelve la ecuación cuadrática:

[matemáticas] 1 – x – x ^ 2 = 0 \ etiqueta * {} [/ matemáticas]

y designar sus raíces como:

[matemáticas] r_ + = \ dfrac {1} {2} (1 + \ sqrt {5}) \ tag {9} [/ matemáticas]

[matemáticas] r_- = \ dfrac {1} {2} (1 – \ sqrt {5}) \ tag {10} [/ matemáticas]

Por lo tanto:

[matemáticas] 1 – x – x ^ 2 = (1 – xr _ +) (1 – xr_-) \ tag * {} [/ matemáticas]

en cuyo caso ( 8 ) se descompone en:

[matemáticas] g (x) = \ dfrac {1} {r_ + – r _-} \ Big (\ dfrac {1} {1-xr_ +} – \ dfrac {1} {1-xr _-} \ Big) \ etiqueta {11} [/ matemáticas]

Pero las fracciones entre paréntesis de ( 11 ) no son nada más (y nada menos) que nuestra buena serie geométrica de viejos amigos con [matemáticas] a = 1 [/ matemáticas] y [matemáticas] r = xr _ {\ pm} [/ matemáticas ] Por lo tanto:

[matemáticas] r_ + – r_- = \ dfrac {1} {2} + \ dfrac {\ sqrt {5}} {2} – \ dfrac {1} {2} + \ dfrac {\ sqrt {5}} { 2} = \ sqrt {5} \ tag * {} [/ math]

y:

[matemáticas] \ displaystyle g (x) = \ dfrac {1} {\ sqrt {5}} \ Big (\ sum_ {n \ geqslant0} r _ + ^ nx ^ n – \ sum_ {n \ geqslant0} r _- ^ nx ^ n \ Big) \ tag * {} [/ math]

Afortunadamente, la suma anterior no es demasiado loca y al llevar la raíz cuadrada inversa de [matemáticas] 5 [/ matemáticas] bajo el signo de la suma y factorizar el término común [matemáticas] x ^ n [/ matemáticas]:

[matemáticas] \ displaystyle g (x) = \ sum_ {n \ geqslant0} \ Big (\ dfrac {r _ + ^ n – r _- ^ n} {\ sqrt {5}} \ Big) x ^ n \ tag * { }[/matemáticas]

y al comparar la suma anterior con la de ( 1 ), debe quedar claro que:

[matemáticas] F_n = \ dfrac {1} {\ sqrt {5}} (r _ + ^ n – r _- ^ n) \ tag {12} [/ matemáticas]

Por último, las raíces de la ecuación cuadrática anterior se han ganado sus propias designaciones especiales:

[matemáticas] r_ + = \ varphi \ tag * {} [/ matemáticas]

[matemáticas] r_- = \ psi \ etiqueta * {} [/ matemáticas]

usando which ( 12 ) se convierte en ( 13 ) (un buen número de Fibonacci):

[matemáticas] F_n = \ dfrac {1} {\ sqrt {5}} (\ varphi ^ n – \ psi ^ n) \ tag {13} [/ matemáticas]

(extra para expertos: vemos que para valores muy grandes de [matemática] n [/ matemática] la magnitud de [matemática] r _- ^ n [/ matemática] o [matemática] \ psi ^ n [/ matemática] nunca es mayor que [math] 0.5 [/ math], por lo tanto, para tales [math] n [/ math] s la fórmula de aproximación:

[matemáticas] F_n \ approx \ dfrac {1} {\ sqrt {5}} \ Big (\ dfrac {1+ \ sqrt {5}} {2} \ Big) ^ n \ tag {14} [/ math]

resulta ser el exacto : el número entero más cercano al lado derecho de ( 14 ))

Answer 2

Usaría matrices, porque son más intuitivas ya que puedes hacer una transformación 2 × 2 que puede transformar el vector que contiene [a; b] en el vector [b; a + b]. La matriz es A = [0 1; 1 1]. (Nota: esta notación es perfecta para escribir en Matlab y es reconocida por Wolfram Alpha. Espacia entradas separadas en la misma línea, líneas separadas por punto y coma. Los vectores son altos, la matriz es cuadrada 2 × 2)

Para obtener el enésimo elemento del conjunto de Fibonacci, elevaría la matriz A a la potencia (N-1) (tenga en cuenta la exponenciación al cuadrar: funciona porque las matrices son asociativas, y eso es mucho más de lo que se necesita) y luego aplíquelo al vector [0; 1] (los dos primeros elementos). Obtendrá los elementos Nth y (N + 1) th en el vector resultante.

Answer 3

Un método relativamente rápido y fácil es representar la serie como una ecuación de diferencia finita y resolverla usando una transformación [matemática] z [/ matemática]. La ecuación FD es

[matemáticas] x (k) + x (k + 1) = x (k + 2) [/ matemáticas]

con [matemáticas] x (0) = 0 [/ matemáticas] y [matemáticas] x (1) = 1 [/ matemáticas].

Las transformaciones estándar [matemáticas] z [/ matemáticas] para estos términos son [matemáticas] x (k) = X (z) [/ matemáticas], [matemáticas] x (k + 1) = zX (z) -zX ( 0) [/ math] y [math] x (k + 2) = z ^ 2X (z) -z ^ 2X (0) -zX (1) [/ math], que nos da la solución en [math] dominio z [/ math]

[matemáticas] X (z) = \ frac {1} {z ^ 2-z-1} = \ frac {1} {(z- \ tfrac {1- \ sqrt {5}} {2}) (z + \ tfrac {1+ \ sqrt {5}} {2})} = \ frac {1 / \ sqrt {5}} {z- \ tfrac {1+ \ sqrt {5}} {2}} – \ frac {1 / \ sqrt {5}} {z- \ tfrac {1- \ sqrt {5}} {2}} [/ math].

Las transformadas inversas [math] z [/ math] de los dos términos nos dan la solución

[matemáticas] x (k) = \ frac {1} {\ sqrt {5}} \ left (\ frac {1+ \ sqrt {5}} {2} \ right) ^ k- \ frac {1} {\ sqrt {5}} \ left (\ frac {1- \ sqrt {5}} {2} \ right) ^ k [/ math] para [math] k = 0,1,2, \ cdots [/ math]

El enfoque es muy general y puede usarse para muchas de estas ecuaciones. Para obtener más información sobre la transformación [matemática] z [/ matemática] y cómo se utiliza para resolver ecuaciones de diferencias finitas, consulte Z-transform – Wikipedia.

Answer 4

Esta es una derivación estándar de la fórmula de Binet, y quizás de todas las demás secuencias (por ejemplo, Lucas) que se define de forma recursiva.

[matemáticas] \ displaystyle \ boxed {F_n + F_ {n + 1} = F_ {n + 2}} \ tag * {(1)} [/ math]

[matemáticas] \ displaystyle F_1 = 1, F_2 = 1 \ etiqueta * {(2)} [/ matemáticas]

Podemos “observar” que forma una secuencia más o menos geométrica si los trazamos en un gráfico. Así que establecemos

[matemáticas] F_n = r ^ n \ etiqueta * {} [/ matemáticas]

De (1) tenemos,

[matemáticas] \ displaystyle \ begin {align} r ^ n + r ^ {n + 1} & = r ^ {n + 2} \\ r ^ 2-r-1 & = 0 \\ r & = \ frac {1 \ pm \ sqrt 5} 2 \ end {align} \ tag * {} [/ math]

Así que afinamos nuestra suposición de ser

[matemáticas] F_n = ar_1 ^ n + br_2 ^ n \ tag * {} [/ matemáticas]

Conocemos los valores de [math] r_1 [/ math] y [math] r_2 [/ math], por lo que lo que queda es averiguar [math] a [/ math] y [math] b [/ math].

Sustituimos [math] n [/ math] como 1 y 2, para verificar los valores de [math] a [/ math] y [math] b [/ math].

[matemáticas] \ left \ {\ begin {matrix} 1 & = & \ displaystyle a \ left (\ frac {1+ \ sqrt 5} 2 \ right) + b \ left (\ frac {1- \ sqrt 5} 2 \ right) \\ 1 & = & \ displaystyle a \ left (\ frac {3+ \ sqrt 5} 2 \ right) + b \ left (\ frac {3- \ sqrt 5} 2 \ right) \ end {matrix} \ derecho. \ tag * {} [/ math]

Resolviendo el sistema de ecuaciones, uno debería obtener

[matemáticas] \ displaystyle \ boxed {\ left \ {\ begin {matrix} a & = & \ dfrac 1 {\ sqrt 5} \\ b & = & – \ dfrac 1 {\ sqrt 5} \ end {matrix} \ right. } \ tag * {} [/ math]

Para hacer la notación un poco más compacta,

[matemáticas] \ displaystyle \ boxed {F_n = \ frac {\ phi ^ n- \ phi ^ {- n}} {\ sqrt 5}} \ tag * {} [/ math]

La fórmula también explica por qué la proporción entre dos números consecutivos de Fibonacci tiende a la proporción áurea, porque

[matemáticas] \ displaystyle \ lim_ {n \ to + \ infty} \ phi ^ {- n} = 0 \ tag * {} [/ matemáticas]