Identidad de Fibonacci: $f_{n-1}f_{n+1} - f_{n}^2 = (-1)^n$

Question

Considerar esta ecuación de Fibonacci: $$f_{n+1}^2 - f_nf_{n+2}$ $

El problema, deberá escribir un programa con n , salida el resultado de esta ecuación. Podría utilizar la fórmula $$f_n = \frac{(1+\sqrt{5})^n - ( 1 - \sqrt{5} )^n}{2^n\sqrt{5}}$ $

Sin embargo, de mathworld, encontré esta fórmula Cassini's identity $$f_{n-1}f_{n+1} - f_{n}^2 = (-1)^n$$

So, I decided to play around with the equation above, and I have:

$$ \text{Let } x = n + 1 $ $ $$ \text{then the equation above becomes } f_x^2 - f_{x-1}f_{x+1} $ $ $$ \Rightarrow -( f_{x-1}f_{x+1} - f_x^2 ) = -1(-1)^x = (-1)^{x+1} = (-1)^{n+1+1} = (-1)^{n+2}$ $

Así que esta ecuación es 1 o -1. ¿Estoy en el camino correcto?

Gracias,
Chan

Answer 1

Tenemos los siguientes (fácilmente probado por inducción):

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix} ^ n =\begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \\ \end{pmatrix} $

Los determinantes de las matrices de la comparación nos da la identidad inmediatamente.

Answer 2

Tratemos de encontrar el mcd de a$F_n$$F_{n+1}$, usando el algoritmo de Euclides Extendido. Voy a escribir los pasos del algoritmo en una tabla; este método de tabla se explicó también en algunos Bill Dubuque de puestos.

$\begin{array}{|l||c|c|} \hline F_{n+1} & 1 & 0 \\\hline F_{n} & 0 & 1 \\\hline F_{n-1} & 1 & -1 \\\hline F_{n-2} & -1 & 2 \\\hline F_{n-3} & 2 & -3 \\\hline \vdots & \vdots & \vdots \\\hline F_{n-k} & (-1)^{k+1}F_k & (-1)^kF_{k+1} \\\hline \end{array} $

Después de unos pocos pasos podemos adivinar el $k$-ésimo de la línea, lo que nos da la siguiente fórmula:
$F_{n-k}=(-1)^{k+1}F_kF_{n+1}+(-1)^kF_{k+1}F_n=(-1)^{k+1}(F_kF_{n+1}-F_{k+1}F_n)$.

Para $k=n-1$ tenemos Cassini de la identidad de $F_1=(-1)^n(F_{n-1}F_{n+1}-F_n^2)$.

Así que lo único que tenemos que hacer es verificar la fórmula anterior, que se puede hacer fácilmente por inducción en $k$.

Inductivo paso: sabemos que:
$F_{n-k}=(-1)^{k+1}(F_kF_{n+1}-F_{k+1}F_n)=-(-1)^{k}(F_kF_{n+1}-F_{k+1}F_n)$
$F_{n-(k-1)}=(-1)^{k}(F_{k-1}F_{n+1}-F_{k}F_n)$

Desde $F_{n-(k+1)}=F_{n-(k-1)}-F_{n-k}$, obtenemos
$F_{n-(k+1)}=(-1)^{k}[(F_{k-1}+F_k)F_{n+1}-(F_k+F_{k+1})F_n]=(-1)^{k+2}(F_{k+1}F_{n+1}-F_{k+2}F_n)$
que completa el paso inductivo.