Tweet
Tengo que resolver un problema a partir de inducción matemática, el cual es el siguiente: Demostrar m.c.d(Fn, F(n+1)) = 1, sabiendo que F0=0 y F1 =1 y F(n+2) = Fn + F(n+1).
En primer lugar compruebo que la expresión se cumple para n = 0:
m.c.d(0,1)= 1 (Se cumple)
Hipotesis de inducción: Suponiendo que la expresión se cumple para n = k
, siendo k un numero natural entre 0 y n, m.c.d(Fk, F(k+1))=1, debemos probar si m.c.d(F(k+1),F(k+2)) =1.
Se deduce a partir del enunciado que:
m.c.d(F(k+1),F(k+2)) = m.c.d(F(k+1), Fk+F(k+1))
Ahora aplico una propiedad de divisibilidad:
Si c|a y c|b, entonces c|d, siendo d = m.c.d(a,b) ---> d|a y d|b
Si d|F(k+1) y d|Fk+F(k+1) ---> d|(-1)F(k+1)+1(Fk+F(k+1)) --> d|Fk
*Aquí tengo la duda, ¿Porqué se multiplica -1 y 1 en la expresión anterior?
Bueno el problema seguiría así:
Si d|F(k+1) y d|Fk, sabemos por inducción que el m.c.d(F(k+1),Fk) = 1
por tanto d = 1.
Me gustaría que me aclarasen dicha duda.
Gracias
En primer lugar compruebo que la expresión se cumple para n = 0:
m.c.d(0,1)= 1 (Se cumple)
Hipotesis de inducción: Suponiendo que la expresión se cumple para n = k
, siendo k un numero natural entre 0 y n, m.c.d(Fk, F(k+1))=1, debemos probar si m.c.d(F(k+1),F(k+2)) =1.
Se deduce a partir del enunciado que:
m.c.d(F(k+1),F(k+2)) = m.c.d(F(k+1), Fk+F(k+1))
Ahora aplico una propiedad de divisibilidad:
Si c|a y c|b, entonces c|d, siendo d = m.c.d(a,b) ---> d|a y d|b
Si d|F(k+1) y d|Fk+F(k+1) ---> d|(-1)F(k+1)+1(Fk+F(k+1)) --> d|Fk
*Aquí tengo la duda, ¿Porqué se multiplica -1 y 1 en la expresión anterior?
Bueno el problema seguiría así:
Si d|F(k+1) y d|Fk, sabemos por inducción que el m.c.d(F(k+1),Fk) = 1
por tanto d = 1.
Me gustaría que me aclarasen dicha duda.
Gracias