Proof that consecutive terms of a sequence are coprime 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

Just solving the recurrence:

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}$.

This is a homogeneous linear recurrence relation with constant coefficionts, so the usual algorithm works.
The characteristic polynomial is
$$
p(t) = t^2 - 5t + 2 
$$
Going for the roots
$$
0 = (t - 5/2)^2 + 2 - 25/4 = (t - 5/2)^2 - 17/4 \iff \\
t = \frac{5 \pm\sqrt{17}}{2}
$$
This gives the general solution
$$
a_n = 
k_1 \left( \frac{5 + \sqrt{17}}{2} \right)^n + 
k_2 \left( \frac{5 - \sqrt{17}}{2} \right)^n
$$
Applying the initial values gives
$$
a_0 = k_1 + k_2 = 7 \\
a_1 = k_1 \frac{5 + \sqrt{17}}{2} + 
k_2 \frac{5 - \sqrt{17}}{2} = 9
$$
and
$$
k_1 = \frac{7 - \sqrt{17}}{2} \\
k_2 = \frac{7 + \sqrt{17}}{2} \\
$$
and we get
$$
a_n = 
\frac{7 - \sqrt{17}}{2} \left( \frac{5 + \sqrt{17}}{2} \right)^n +
\frac{7 + \sqrt{17}}{2} \left( \frac{5 - \sqrt{17}}{2} \right)^n
$$
No idea yet if that form is of any help.
