Prueba por inducción sobre los números de Fibonacci: mostrar que $f_n\mid f_{2n}$

Question

Yo estaba estudiando la Inducción Matemática cuando me encontré con el siguiente problema:

Los números de Fibonacci son la secuencia de números definidos por el lineal de la ecuación de recurrencia-

$f_n = f_{n-1} + f_{n-2}$ $f_1 = f_2 = 1$

El uso de la inducción para demostrar que $f_n \; | \; f_{2n}$ ($f_n$ divide $f_{2n}$)

Base Paso es obviamente cierto; pero me estoy enfrentando dificultades en el Paso Inductivo. Si asumo la hipótesis inductiva para ser cierto para algunos $k$, es decir, $\dfrac{ f_{2k} } { f_{k} } = c$ (Para algún entero positivo $c > 0$), no estoy claro en cuanto a cómo debe proceder más allá y probar que $P(2k+1)$ también es cierto.

Soy nuevo aquí, así que si estoy haciendo algo mal, por favor, pasar por alto en la cuenta de mi ingenuidad.

Answer 1

Desde el principio, no hay una clara declaración de inducir. Como tal, usted tiene que adivinar la hipótesis de inducción, y encontrar un explícito el modelo que usted podría describir.

Sugerencia: ver la secuencia de valores de $\frac{f_{2k}}{f_k}$. Ves un patrón no? Eso sugiere probar el siguiente hecho:

$$\frac{f_{2k+2}} { f_{k+1} } = \frac{f_{2k} } { f_k } + \frac{f_{2k-2} } {f_{k-1} }$$

Compruebe que los dos primeros términos de esta serie $g_n = \frac{f_{2n}}{f_n}$ son enteros, por lo tanto a la conclusión de que la inducción por que cada término es un número entero.

Answer 2

La pregunta es vieja, Calvin Lin respuesta es grande y ya aceptado, pero aquí es otro método (por la famosa causa de completess):

Sabemos que $f_n \wedge f_m=f_{n\wedge m}$ donde $a\wedge b$ es el mcd de a$a$$b$. Por lo $f_n \wedge f_{2n}=f_{n\ \wedge\ 2n}=f_n$. Esto significa que $f_n$ divide $f_{2n}$.