Let $\displaystyle a_0, a_1, a_2,$ ... be a seqence of positive integers for which

$\displaystyle a_0=1,$

$\displaystyle a_{2n+1}=a_n$

$\displaystyle a_{2n+2}=a_n+a_{n+1}$

Prove that $\displaystyle a_n$ and $\displaystyle a_{n+1}$ are relatively prime for every nonnegative integer $\displaystyle n$.

$\displaystyle a_0=1$

$\displaystyle n=0, \:a_1=1, \:\:a_2=2$

$\displaystyle n=1, \:a_3=1, \:\:a_4=3$

$\displaystyle n=2, \:a_5=2, \:\:a_6=3$

$\displaystyle n=3, \:a_7=1, \:\:a_8=4$

$\displaystyle n=4, \:a_9=3, \:a_{10}=5$

$\displaystyle n=5, \:a_{11}=2, \:a_{12}=5$

$\displaystyle n=6, \:a_{13}=3, \:a_{14}=4$

$\displaystyle n=7, \:a_{15}=1, \:a_{16}=5$

$\displaystyle n=8, \:a_{17}=4, \:a_{18}=7$

...

...

...

There doesn't seem to be a discernable pattern, but any how, I think these can be approached by Strong Induction.

The basis case is easy. $\displaystyle gcd(a_0,a_1)=gcd(1,1)=1$ is obvious.

The Inductive step: Assume $\displaystyle gcd(a_k,a_{k+1})=gcd(a_{2p+1}, a_{2p+2})=gcd(a_p,a_{p+1})=1$. We show that $\displaystyle gcd(a_{k+1},a_{k+2})=1$, $\displaystyle p \in \mathsb{z}^+ \cup {0}$

I can't see the recurrence relation for $\displaystyle a_k$. Need help.