Demostrar por inducción la igualdad de Fibonacci

Question

[pregunta:]

Demostrar por inducción que el i número de Fibonacci satisface la igualdad
$$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}$$ donde $\phi$ es la proporción áurea y $\hat{\phi}$ es su conjugado.
[fin]

He hecho múltiples intentos, el más fructífero es el que sigue, aunque es incorrecto, y no consigo averiguar en qué me equivoco:

[mi respuesta:]
Lo que sigue es un planteamiento incorrecto, tras el cual viene el planteamiento que debería haber hecho

Hipótesis inductiva: $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}, i\in\mathbb{N} $$ (Incluyo 0)
Caso base: $$F_0=\frac{\phi^0-\hat{\phi^0}}{\sqrt5}=0$$

Prueba: $$\begin{eqnarray*} F_{i+1}&=&\frac{\phi^{i+1}-\hat{\phi^{i+1}}}{\sqrt5}\\ &=&\frac{\phi*\phi^i-\hat{\phi}*\hat{\phi^i}}{\sqrt5}\\ &=&\frac{\frac{1+\sqrt5}{2}*\phi^i-\frac{1-\sqrt5}{2}*\hat{\phi^i}}{\sqrt5}\\ &=&\frac{\frac{\phi^i+\sqrt5\phi^i}{2}-\frac{\hat{\phi^i}-\sqrt5\hat{\phi^i}}{2}}{\sqrt5}\\ &=&\frac{\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{2}}{\sqrt5}\\ &=&\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{2*\sqrt5}\\ &=&\frac{1}{2}\left(\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{\sqrt5}\right)\\ &=&\frac{1}{2}\left(\frac{\sqrt5\phi^i}{\sqrt5} + \frac{\sqrt5\hat{\phi^i}}{\sqrt5} +\frac{\phi^i-\hat{\phi^i}}{\sqrt5}\right)\\ &=&\frac{1}{2}\left(\phi^i+\hat{\phi^i}+F_{i}\right)\text{ by inductive hypothesis}\\ &=&\frac{1}{2}\left(\sqrt5*...\right)\\ \end{eqnarray*}$$ En realidad acabo de ver mi error en esa línea (al final he multiplicado por $\frac{\sqrt5}{\sqrt5}$ y sustituido por $F_i$ , pero veo que ahí se suman los conjugados, no se restan).

Enfoque correcto: $$\begin{eqnarray*} F_{i+1}&=&F_{i} + F_{i-1}\\ &=&\frac{\phi^i-\hat{\phi^i}}{\sqrt5}+\frac{\phi^{i-1}-\hat{\phi^{i-1}}}{\sqrt5}\\ &=&\frac{\left(\phi+\hat{\phi}\right)\left(\phi^i-\hat{\phi^i}\right)-\phi\hat{\phi}\left(\phi^{i-1}-\hat{\phi^{i-1}}\right)}{\sqrt5}\text{ (see answer for why this works)}\\ &=&\frac{\phi^{i+1}-\phi\hat{\phi^i}+\hat{\phi}\phi^i-\hat{\phi^{i+1}}-\phi^i\hat{\phi}+\phi\hat{\phi^i}}{\sqrt5}\\ &=&\frac{\phi^{i+1}-\hat{\phi^{i+1}}-\phi\hat{\phi^i}+\phi\hat{\phi^i}-\hat{\phi}\phi^i+\hat{\phi}\phi^i}{\sqrt5}\\ &=&\frac{\phi^{i+1}-\hat{\phi^{i+1}}}{\sqrt5}\\ \text{Q.E.D., punk problem.} \end{eqnarray*}$$

Por lo que he buscado en la web, no hay ninguna fuente disponible que demuestre esto de la secuencia de Fibonacci - todas pruebas de hipótesis inductivas demuestran la secuencia real con la inducción.

Bill, siempre es fácil olvidar las propiedades inherentes a los números especiales... Ni siquiera me di cuenta $\phi$ + $\hat{\phi}$ = 1 en tu primera pista, así como la multiplicación, hasta que lo señalaste. Alex, estoy seguro de que repasando el problema de esa manera también se obtiene el resultado, pero con el de Bill es mucho más rápido.

Gracias por la ayuda.

Answer 1

No se puede empezar desde $F_{i+1}=\frac{\phi^{i+1}-\smash{\hat{\phi}}^{i+1}}{\sqrt5}$ ya que eso es lo que estás tratando de probar. Más bien, la prueba debe partir de lo que tienes (la hipótesis inductiva) y trabajar a partir de ahí. Dado que los números de Fibonacci se definen como $F_n=F_{n-1}+F_{n-2}$ , necesitas dos casos base, ambos $F_0$ y $F_1$ que te dejaré resolver. El paso de la inducción debe entonces comenzar así: $$\begin{eqnarray*} F_{i+1}&=&F_i + F_{i-1}\\ &=&\frac{\phi^i-\smash{\hat{\phi}}^i}{\sqrt5}+\frac{\phi^{i-1}-\hat{\phi}{}^{i-1}}{\sqrt5}\\ \end{eqnarray*}$$ lo que, con suerte, es una pista suficiente para empezar.

Editar : Aquí hay una versión más trabajada. He cometido una errata en mis comentarios. $$\begin{eqnarray*} F_{i+1}&=&F_i + F_{i-1}\\ &=&\frac{\phi^i-\smash{\hat{\phi}}^i+\phi^{i-1}-\hat{\phi}{}^{i-1}}{\sqrt5}\\ &=&\frac{(\smash{\hat{\phi}}^2-\hat{\phi})\phi^{i+1}-(\phi^2-\phi)\smash{\hat{\phi}}^{i+1}}{\sqrt5}\\ \end{eqnarray*}$$

Answer 2

HINT $\rm\quad \phi^{\:n+1}\!-\:\bar\phi^{\:n+1}\ =\ (\phi+\bar\phi)\ (\phi^n\!-\:\bar\phi^n)\ -\ \phi\:\bar\phi\ (\phi^{\:n-1}\!-\:\bar\phi^{\:n-1})$

Por lo tanto, al sustituir $\rm\ \phi+\bar\phi\ =\ 1\ =\ -\phi\bar\phi\ $ y dividiendo por $\:\phi-\bar\phi = \sqrt 5\:$ deducimos $\rm\ \ldots$

REMARK $\ $ Para entender la esencia del asunto vale la pena enfatizar que tal prueba inductiva equivale a precisamente para demostrar que $\rm\:f_n\:$ y $\rm\: \bar{f}_n = (\phi^n-\bar\phi^n)/(\phi-\bar\phi)\:$ son ambas soluciones de la ecuación en diferencia (recurrencia) $\rm\ f_{n+2} = f_{n+1} + f_n\:,\:$ con condiciones iniciales $\rm\ f_0 = 0,\ f_1 = 1\:.\:$ La inducción (trivial) simplemente demuestra la singularidad de dichas soluciones. Resultará bastante instructivo estructurar la prueba desde este punto de vista. También significará que más adelante podrá reutilizar este teorema de unicidad para las recurrencias.

En general, al igual que en el caso anterior, los teoremas de unicidad proporcionan herramientas muy poderosas para demostrar las igualdades, un punto que destaco en muchos puestos anteriores. Por ejemplo, véase mis publicaciones anteriores sobre telescopio y el teorema fundamental del cálculo de diferencias, esp. este.

Answer 3

F0 = 0 se mantiene. F1 = 1 se mantiene. Supongamos que Fk = φk-ˆ φk √5 se mantiene ∀k < n. Fn = Fn-1 + Fn-2 por definición de Fn. Fn = φn - − 1 - ˆ φn - − 1 √5 + φn - − 2 - ˆ φn - − 2 √5 por inducción. Verifiquemos una identidad: φi-1 - ˆ φi-1 + φi-2 - ˆ φi-2 = (1 + 1+√5 2 )φi-2 -(1 + 1-√5 2 )ˆ φi-2 = 4+2+2√5 4 φi-2 - 4+2-2√5 4 ˆ φi-2 = 1+2√5+5 4 φi-2 - 1-2√5+5 4 ˆ φi-2 = (1+√5 2 )2φi-2 -(1-√5 2 )2 ˆ φi-2 = φi - ˆ φ2 Concluimos que Fn = φn-ˆ φn √5 , es decir, que la hipótesis de inducción se cumple también para n. Por inducción la igualdad se cumple para todo n ≤ 0