En una inducción matemática, ¿se puede demostrar el paso "n's caso implica n+1's caso" por contrapositivo?

Question

Estoy intentando demostrar la primera parte del Ejercicio 1.5, en la obra de Tom Apostol Análisis matemático en relación con los números de Fibonacci:

Los números de Fibonacci $1, 1, 2, 3, 5, 8, 13 \dots$ están definidos por la fórmula de recursión $x_{n + 1} = x_{n} + x_{n-1}$ con $x_1 = x_2 = 1$ .

Demostrar que $\gcd(x_{n}, x_{n+1}) = 1$ .

El caso base de los dos primeros pasos es bastante sencillo, por supuesto: $\gcd(x_1, x_2) = 1$ .

Pero me preocupa que esté haciendo un extraño juego de manos pseudo-lógico con la hipótesis inductiva: En lugar de demostrar directamente que $\gcd(x_{n-1}, x_{n}) = 1$ implica $\gcd(x_{n}, x_{n+1}) = 1$ Me parece más fácil demostrar que $\gcd(x_{n}, x_{n+1}) \neq 1 \implies \gcd(x_{n-1}, x_{n}) \neq 1$ . Esto me parece una prueba por contrapositiva: $P$ implica $Q$ equivale a no $Q$ implica no $P$ .

(Otra forma de expresar mi argumento, es que si $F_{n+1}$ y $F_{n}$ tienen un factor común $\alpha > 1$ entonces la definición del Fibs implica que $\alpha \mid F_{n-1}$ también, lo que implica $\alpha \mid F_{n-2}$ , lo que implica $\alpha \mid F_{n-3}, \dots$ Hasta que lleguemos al fondo de los casos básicos, donde esto es claramente falso. Tengo más de una forma de expresar la cosa, pero prefiero quedarme con la inducción si es legal, ya que la entiendo un poco mejor).

Answer 1

Su argumento está bien, por supuesto.

También puedes hacerlo directamente. Supongamos que $\gcd(x_{n-1}, x_n) =1$ . Entonces $\exists \alpha, \beta \in \mathbb{Z}$ tal que $\alpha x_{n-1} + \beta x_n = 1$ .

Tenemos

$$(\beta -\alpha)x_n + \alpha x_{n+1} = (\beta -\alpha)x_n + \alpha (x_n + x_{n-1}) = \beta x_n + \alpha x_{n-1} = 1$$ así que $\gcd(x_n, x_{n+1}) =1$ .