Números de Fibonacci $F_n$ y $F_{n + 1}$ son relativamente primos para todos $n \geq 0$ .

Question

He buscado un montón de soluciones de este problema en la web. Pero quiero saber si mi solución es correcta o no. Mi solución es la siguiente

Prueba (por inducción)

$P(n)$ Los números de Fibonacci $F_n$ y $F_{n + 1}$ son relativamente primos.

Caso base : $P(0)$ es cierto porque $F_0 = 0$ y $F_1 = 1$ son relativamente primos.

Paso inductivo : Supongamos que $P(n)$ que sea cierto. Ahora para demostrar que para $n \geq 0$ , $P(n) \implies P(n + 1)$

$\implies \gcd(F_n, F_{n + 1}) = 1$

$\implies s(F_n) + t(F_{n + 1}) = 1$

$\implies s(F_{n + 2} - F_{n + 1}) + t(F_{n + 1}) = 1$

$\implies (t - s)(F_{n + 1}) + s(F_{n + 2}) = 1$

$\implies \gcd(F_{n + 1}, F_{n + 2}) = 1$

$\implies P(n + 1)$ es cierto

Así, por inducción $P(n)$ es cierto para todos los $n \geq 0$ .

Answer 1

La idea está bien, pero deberías usar más palabras; hace que el argumento sea mucho más claro y legible. Así es como yo presentaría el mismo argumento.

Supongamos como hipótesis de inducción que $\gcd(F_n,F_{n+1})=1$ . Entonces hay enteros $s$ y $t$ tal que

$$\begin{align*} 1&=sF_n+tF_{n+1}\\ &=s(F_{n+2}-F_{n+1})+tF_{n+1}\\ &=sF_{n+2}+(t-s)F_{n+1}\;, \end{align*}$$

y se deduce que $\gcd(F_{n+1},F_{n+2})=1$ también. El resultado se sigue ahora por inducción.