Demostración por inducción sobre los números de Fibonacci: demuestre que fn∣f2nfn∣f2nf_n\mid f_{2n}

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

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

F norte = F norte − 1 + F norte − 2 con F 1 = F 2 = 1

Utilice la inducción para demostrar que F norte | F 2 norte ( F norte divide F 2 norte )

Basis Step es obviamente cierto; pero estoy enfrentando dificultades en el Paso Inductivo. Si asumo que la hipótesis inductiva es cierta para algunos k , es decir, F 2 k F k = C (Para algún entero positivo C > 0 ), no tengo claro cómo debo seguir adelante y demostrar que PAG ( 2 k + 1 ) también es cierto

Soy nuevo aquí, así que si estoy haciendo algo mal, páselo por alto debido a mi ingenuidad.

Intente observar algunos ejemplos pequeños para ver qué sucede; a veces, debe fortalecer su hipótesis de inducción y demostrar una afirmación más sólida. (Y también, hay formas fáciles de probar esta afirmación sin inducción, por supuesto, pero en este contexto supongo que lo que quieres/necesitas es una prueba por inducción).
@Tarun, corrija el error tipográfico donde escribí F 2 k F 2 k = C en lugar de F 2 k F k = C . No puedo editar ya que la edición requiere que se cambien al menos 6 caracteres.
No creo que eso funcione. La edición verifica las cosas que han cambiado. Volver a escribir no ayudará (hasta donde yo sé).

Respuestas (2)

Desde el principio, no hay una declaración clara para inducir. Como tal, debe adivinar la hipótesis de inducción y encontrar un patrón explícito que pueda describir.

Sugerencia: Mire la secuencia de valores de F 2 k F k . ¿Ves un patrón allí? Eso sugiere probar el siguiente hecho:

F 2 k + 2 F k + 1 = F 2 k F k + F 2 k − 2 F k − 1

Comprueba que los dos primeros términos de esta serie gramo norte = F 2 norte F norte son números enteros, por lo que se concluye por inducción que todo término es un número entero.

hola, ¿cómo probaste el hecho?
@SunainaPati ¿Conoces la fórmula de Binet? Eso es casi inmediato ya que ( a 2 k − b 2 k ) / ( a k − b k ) = ( a k + b k ) .
En realidad, no estoy seguro de cómo proceder después de eso...
@SunainaPati ¿Qué has probado? ¿Hiciste la inducción como sugerí inicialmente? Eso nos da el resultado a. No estoy seguro de dónde está atascado, así que si puede mostrar su trabajo, eso me permitirá adaptar mi respuesta.
¡Lo tengo! Antes no me di cuenta de que son raíz de X 2 = X + 1

La pregunta es antigua, la respuesta de Calvin Lin es excelente y ya está aceptada, pero aquí hay otro método (por el famoso bien de la integridad ):

Lo sabemos F norte ∧ F metro = F norte ∧ metro , dónde a ∧ b es el mcd de a y b . Entonces F norte ∧ F 2 norte = F norte   ∧   2 norte = F norte . Esto significa que F norte divide F 2 norte .

Demostración por inducción sobre los números de Fibonacci: demuestre que fn∣f2nfn∣f2nf_n\mid f_{2n}
RespuestasAquíPolítica de privacidad1y, 3v