The series $f_n$ is defined by the following relation: $f_0=0,\,f_1=1$, $f_{n}=f_{n-1}+f_{n-2}$, for $n>1$. Show that $f_n$ and $f_{n+1}$ are coprime.
$$f_0=0,\,f_1=1,\,f_2=2,\,f_3=3,\,f_4=5,\,f_5=8,\,f_6=13$$
By induction:
For all $n>1$ let $P(n)$ be the assumption $\gcd(f_n,f_{n+1})=1$.
$$P(1) \ \text{is true},$$ $$P(1): \gcd(1,1)=1 $$
$$(V.L)_{n+1}=\gcd(f_{n+1}, f_{n+2})=\gcd(f_{n+1}, f_{n+1}+f_n) \\ =\gcd(f_{n+1}, f_n)=1=(H.L)_{n+1}$$
Now how do I show that if $d\mid f_{n+1}+f_n$ and $d\mid f_{n+1}$ that $\gcd(f_{n+1}, f_n)=1$?
Many thanks.
Hint: $\gcd(f_{n+1}, f_n) = \gcd (f_{n+1} - f_n , f_n ) = \gcd(f_{n-1}, f_n)$.