I've been dealing with the following problem for a while:
Let $a_n$ be a sequence in $\mathbb{N}$, such that $a_{0} =7, a_{1} =9, a_{n} =5 \cdot a_{n-1}-2 \cdot a_{n-2}$. Prove that $a_n$ and $a_{n+1}$ are coprime.
I've tried coming up with a general formula for $a_n$ but couldn't. I know that the gcd between $a_n$ and $a_{n+1}$ should be 1, but how should I prove it? I guess that I could say that there's a prime that divide's both of them and get a contradiction...
So if p divides $a_n$ and $a_{n+1}$ it must divide their sum:
$5(a_n + a_{n-1}) \equiv 2 (a_{n-1} + a_{n-2}) \mod {p}$
$p$ can't divide both 5 and 2 at the same time unless it's 1. But what can I say about the rest? Is this the best way to go?
Thanks