Mostrar que $f(2n) = f(n+1)^2 - f(n-1)^2$

Question

Sea $f(n) = f(n-1) + f(n-2)$ la secuencia de Fibonacci con $f(0)=0, f(1)=1$. Demostrar que $$f(2n) = f(n+1)^2 - f(n-1)^2.$$

He intentado varios enfoques diferentes para este problema. Tanto inductivamente desde el lado derecho como desde el izquierdo, y siempre termino yendo en círculos. ¡Cualquier ayuda sería apreciada! ¡Gracias!

Trabajando desde el lado izquierdo he obtenido: $$f(2(n+1)+1) = f(2n+1) + f(2n)$$ $$= f(2n-1) + f(2n) + f(2n)$$ $$= f(2n-1) + 2(f(n+1)^2 - f(n-1)^2)$$ Pero no puedo averiguar a dónde ir desde aquí. ¿Ayuda?

Answer 1

Encontré mucho más fácil probar la fórmula usando la representación matricial de los números de Fibonacci:

$$ \begin{pmatrix} 1 && 1 \\ 1 && 0\end{pmatrix}^n = \begin{pmatrix} F_{n+1} && F_n \\ F_n && F_{n-1}\end{pmatrix}. $$

Ahora, la multiplicación de matrices cumple $A^nA^m=A^{n+m}$, así que simplemente calcula la entrada de matriz $[A^{n+m}]_{1,2}$ y luego establece $m=n$. El resultado entonces se sigue.

Answer 2

Intentemos otra prueba.

Sabemos que $$F_{n+1}=F_{n-1}+F_n\tag{1}$$

Hay una identidad útil para la secuencia de Fibonacci. Puedes ver cómo se demuestra aquí. $$F_{n+m}=F_{n-1}F_m+F_n F_{m+1}\tag{2}$$ Vamos a poner $n=m$, entonces obtenemos $$F_{2n}=F_nF_{n-1}+F_nF_{n+1}$$ Usando (1), podemos expandir la segunda expresión - $$F_{2n}=F_nF_{n-1}+F_n(F_n+F_{n-1})$$ $$F_{2n}=2F_nF_{n-1}+F_n^2\tag{3}$$

Ahora usando (1), intentamos encontrar un valor para el lado derecho : $$F_{n+1}^2= (F_n+F_{n-1})^2 $$$$F_{n+1}^2 = F_n^2+F_{n-1}^2+2F_nF_{n-1}$$ $$F_{n+1}^2 - F_{n-1}^2=F_n^2+2F_nF_{n-1}\tag{4}$$

Claramente, (3) y (4) son iguales. Por lo tanto, demostrado

Answer 3

Vamos a buscar las soluciones de la ecuación recursiva en la forma $f(n)=C\lambda^n$. Si sustituimos esta forma en la recursión obtenemos $$\lambda^n=\lambda^{n-1}+\lambda^{n-2},\tag{1}$$ lo cual resulta en la ecuación cuadrática $$1=\frac{1}{\lambda}+\frac{1}{\lambda^2}$$ cuyas soluciones son $$\lambda_{1,2}=\frac{1\pm\sqrt{5}}{2}$$ Verifica que si $C_1\lambda_1^n$ y $C_2\lambda_2^n$ son soluciones de la ecuación recursiva entonces su suma también es una solución: $$f(n)=C_1\lambda_1^n+C_2\lambda_2^n,$$

donde $C_1=-C_2=\sqrt{5}$ se obtiene del hecho de que $f(0)=1$ y $f(1)=1$ (Usa eq. (1))

Ahora obtenemos $$f(n+1)^2=C_1^2\lambda_1^{2n+2}+C_2^2\lambda_2^{2n+2}+2C_1C_2(\lambda_1\lambda_2)^{n+1}\tag{2}$$ $$f(n+1)^2=C_1^2\lambda_1^{2n-2}+C_2^2\lambda_2^{2n-2}+2C_1C_2(\lambda_1\lambda_2)^{n-1}\tag{3}$$ Restamos (2) y (3) teniendo en cuenta que $\lambda_1\lambda_2=-1$ (de la ecuación cuadrática). Llegamos a $$f(n+1)^2-f(n-1)^2=C_1^2\lambda_1^{2n}\left(\lambda_1^2-\frac{1}{\lambda_1^2}\right)+C_2^2\lambda_2^{2n}\left(\lambda_2^2-\frac{1}{\lambda_2^2}\right)$$ Usando los valores de $C_1$,$C_2$,$\lambda_1$ y $\lambda_2$ observamos que $$C_1\lambda_1^{2n}\left(\lambda_1^2-\frac{1}{\lambda_1^2}\right)=C_2\lambda_2^{2n}\left(\lambda_2^2-\frac{1}{\lambda_2^2}\right)=1$$ y por lo tanto $$f(n+1)^2-f(n-1)^2=C_1\lambda_1^{2n}+C_2\lambda_2^{2n}=f(2n).$$

Answer 4

¿Has intentado usar la Fórmula de Binet? http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

Answer 5

Siguiendo la sugerencia de Joseph, podemos probar la identidad directamente usando la fórmula de Binet $$f(n) = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$ donde $$\varphi = \frac{1 + \sqrt{5}}{2} \qquad \psi = \frac{1 - \sqrt{5}}{2} = -\frac{1}{\varphi}$$ de modo que $$\varphi^2 - \frac{1}{\varphi^2} = \sqrt{5} = \frac{1}{\psi^2} - \psi^2 \qquad \varphi\psi - \frac{1}{\varphi\psi} = 0.$$ Entonces \begin{align} f(n+1)^2 - f(n-1)^2 & = \left(\frac{\varphi^{n+1} - \psi^{n+1}}{\sqrt{5}}\right)^2 - \left(\frac{\varphi^{n-1} - \psi^{n-1}}{\sqrt{5}}\right)^2\\ & = \frac{1}{5}\left(\varphi^{2n+2} - 2\varphi^{n+1}\psi^{n+1} + \psi^{2n+2} - \varphi^{2n-2} + 2\varphi^{n-1}\psi^{n-1} - \psi^{2n-2}\right)\\ & = \frac{1}{5}\left(\left(\varphi^2 - \frac{1}{\varphi^2}\right)\varphi^{2n} - 2\left(\varphi\psi - \frac{1}{\varphi\psi}\right)\varphi^n\psi^n - \left(\frac{1}{\psi^2} - \psi^2\right) \psi^{2n}\right)\\ & = \frac{1}{5}\left(\sqrt{5}\varphi^{2n} - 2 \cdot 0 \cdot \varphi^n\psi^n - \sqrt{5}\psi^{2n}\right)\\ & = \frac{\varphi^{2n} - \psi^{2n}}{\sqrt{5}}\\ & = f(2n). \end{align}