I'm attempting to prove the first part of Exercise 1.5, in Tom Apostol's Mathematical Analysis, regarding the Fibonacci numbers:
The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13 \dots$ are defined by the recursion formula $x_{n + 1} = x_{n} + x_{n-1}$, with $x_1 = x_2 = 1$.
Prove that $\gcd(x_{n}, x_{n+1}) = 1$.
The base case on the first two steps is pretty simple, of course: $\gcd(x_1, x_2) = 1$.
But I'm concerned I'm doing some weird pseudo-logical sleight of hand with the inductive hypothesis: Instead of proving directly that $\gcd(x_{n-1}, x_{n}) = 1$ implies $\gcd(x_{n}, x_{n+1}) = 1$, I find it easier to show that $\gcd(x_{n}, x_{n+1}) \neq 1 \implies \gcd(x_{n-1}, x_{n}) \neq 1$. This looks like a proof by contrapositive to me: $P$ implies $Q$, is equivalent to not $Q$ implies not $P$.
(Another way to phrase my argument, is that if $F_{n+1}$ and $F_{n}$ have a common factor $\alpha > 1$, then the definition of the Fibs implies that $\alpha \mid F_{n-1}$ as well, which implies $\alpha \mid F_{n-2}$, which implies $\alpha \mid F_{n-3}, \dots$, until we bottom out at the base cases, where this is clearly false. I have more than one way to phrase the thing, but I would rather stick to induction if it's legal, since I understand it a little better.)
Your argument is fine, of course.
You can also do it directly. Assume $\gcd(x_{n-1}, x_n) =1$. Then $\exists \alpha, \beta \in \mathbb{Z}$ such that $\alpha x_{n-1} + \beta x_n = 1$.
We have
$$(\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$$ so $\gcd(x_n, x_{n+1}) =1$.