[daniiy]

Hola.

En un problema piden probar por inducción que los números de Fibonacci \( F_n \) y \( F_{n+1} \) son coprimos para todo entero \( n\geq{0} \).

\( F_n = F_{n-1} + F_{n-2},  n\geq 2, F_0 = 0, F_1=1 \)

Entiendo que haya que demostrar que \( mcd(F_{k+1}, F_{k+2}) = 1 \)

Mi profesor en el paso inductivo hace una reducción al absurdo para demostrarlo. Supone que el máximo común divisor de ambos términos es igual a \( d>1 \) y que \( d|F_{k+1} \) y \( d|F_{k+2} \) y que por lo tanto (por el tema pasado que pregunté de aritmética modular), d también divide a la resta de \( F_{k+2} - F_{k-1} \), lo que es igual a que \( d|F_k \) sustituyendo con la ecuación de Fibonacci.

Hasta aquí todo perfecto. Luego ya me pierdo, aunque realmente me pierdo en 1 sóla línea. Me pierdo cuando mi profesor escribe:

\( mcd(F_{k+1}, F_k)\geq d>1 \)

[pierrot]

Hasta aquí todo perfecto. Luego ya me pierdo, aunque realmente me pierdo en 1 sóla línea. Me pierdo cuando mi profesor escribe:

\( mcd (F_{k+1}, F_k) \geq{d>1} \)

En el paso inductivo, la hipótesis es que \( mcd (F_k,F_{k+1})=1 \), y quiere probar que \( mcd (F_{k+1},F_{k+2})=1 \). Entonces, si este último no fuera uno, sería un \( d>1 \) que obviamente por ser divisor común, verifica que \( d|F_{k+1} \) y \( d|F_{k+2} \), y de ahí \( d|F_{k+2}-F_{k+1}=F_k \) (nota que tienes una errata donde pones \( F_{k+2} - F_{\red k-1} \)). Luego \( d \) es un divisor común de \( F_k \) y de \( F_{k+1} \), y en consecuencia, menor o igual que el máximo común divisor de \( F_k \) y \( F_{k+1} \). Eso es lo que escribe aquí:

\( mcd (F_{k+1}, F_k) \geq d>1 \)

Y es absurdo porque la hipótesis inductiva es que \( mcd (F_{k+1},F_k)=1 \).

[Juan Pablo Sancho]

Mira este hilo:

http://rinconmatematico.com/foros/index.php?topic=73082.msg290807#msg290807

PabloN respondió y fue más rápido.

[daniiy]

Gracias a los dos, lo he entendido

Saludos!