Prove By Induction (Fibonacci Sequence)

Question

Prove by PMI $\gcd(f_n,f_{n+1}) = 1$ for all natural numbers $n$. $f_n$ represents the Fibonacci sequence.

Answer 1

Hint: $\gcd(a,b)=\gcd(a-b,b)$.

Answer 2

Three consecutive terms in a Fibonacci sequence can be written as $a,b,a+b$. If $d$ divides $b$ and $d$ divides $a+b$, then $d$ divides $a+b-b=a$.