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
 A: Proof by induction.
Step I:  All the $a_n$ are odd.
Pf:  Clearly they start odd, if we assume that $a_{n-1}$ is odd then the recursion instantly implies that $a_n$ is also odd.
Step II.  Assume, inductively,  that $\gcd(a_{n-1},a_{n-2})=1$
Note that this is easily proven for small $n$.
Now suppose that $\gcd(a_n,a_{n-1})>1$ and let $p$ denote a prime which divides that $\gcd$.  We remark that Step I implies that $p$ is odd.
Since $p$ divides both $a_n$ and $a_{n-1}$ we see that $p$ divides $2a_{n-2}$ as $$2a_{n-2}=5a_{n-1}-a_n$$
As $p$ is odd this implies that $p\,|\,a_{n-2}$ thus $p\,|\,\gcd(a_{n-2},a_{n-1})$ in contradiction of the induction hypothesis, and we are done.
A: 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.
