# Gcd of every other Fibonacci number

Let $f_n$ be Fibonacci Sequence. $$gcd(f_{n},f_{n+2})=1,\quad \forall\,n\in\mathbb{N}.$$ Prove

Could you help me with this one? I have done the base case, I just can't figure out the inductive step. Thanks!

-

Suppose that for a particular $k$ we have $\gcd(f_k,f_{k+2})=1$. We will show that $\gcd(f_{k+1},f_{k+3})=1$.
Suppose that $d$ divides $f_{k+1}$ and $f_{k+3}$. Then since $f_{k+2}=f_{k+3}-f_{k+1}$, we have $d$ divides $f_{k+2}$. But then because $f_{k}=f_{k+2}-f_{k+1}$, it follows that $d$ divides $f_k$.
This forces $d=1$ by the induction assumption.
A broad hint: $\gcd(f_{n+3}, f_{n+1})$ $=\gcd(f_{n+2}+f_{n+1}, f_{n+1})$ $=\gcd(f_{n+2}+f_{n+1}-f_{n+1}, f_{n+1})$ $=\gcd(f_{n+2}, f_{n+1})$ $=\gcd(f_{n+2}, f_{n+1}-f_{n+2})$ $=\ldots$, where the second and last steps use the theorem that $\gcd(a+cb, b) = \gcd(a,b)$.