[Math] Fibonacci Numbers $F_n$ and $F_{n + 1}$ are relatively prime for all $n \geq 0$.

Question

I have looked a bunch of solutions of this problem on the web. But I want to know that whether my solution is correct or not. My solution is as follows

Proof(By Induction)

$P(n)$:The Fibonacci numbers $F_n$ and $F_{n + 1}$ are relatively prime.

Base Case: $P(0)$ is true because $F_0 = 0$ and $F_1 = 1$ are relatively prime.

Inductive Step:
Assume $P(n)$ to be true. Now to show that for $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)$ is true

Thus, by induction $P(n)$ is true for all $n \geq 0$.

Answer 1

The idea is fine, but you really ought to use more words; it makes the argument much clearer and much more readable. Here’s how I would present the same argument.

Assume as induction hypothesis that $\gcd(F_n,F_{n+1})=1$. Then there are integers $s$ and $t$ such that

$$\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*}$$

and it follows that $\gcd(F_{n+1},F_{n+2})=1$ as well. The result now follows by induction.