# 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

• Hint: use induction. – lulu Apr 27 '17 at 14:09
• @lulu how exactly? I've tried by setting my hypothesis to $gcd(a_n, a_{n+1)}=1$ but can't work my way around it. – jrs Apr 27 '17 at 14:15
• Well...say $p\,|\,\gcd(a_n,a_{n-1})$. Then of course $p\,|\,2a_{n-2}$. It is easy to see that all the $a_n$ are odd so we must have $p\,|\,a_{n-2}$. Thus $p\,|\,\gcd(a_{n-2},a_{n-1})$ – lulu Apr 27 '17 at 14:16
• @Gio You could try infinite descent, which is almost like induction (it's what induction becomes if you throw in a contrapositive at the right moment). The problem then reads "Let $k\geq1$ be a number such that $\gcd(a_k, a_{k+1})\neq 1$. Show that $\gcd(a_{k-1}, a_k)\neq 1$." – Arthur Apr 27 '17 at 14:18

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.

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.

• This helps too, thanks. I didn't know about this algorithm... does it have a particular name? – jrs Apr 27 '17 at 15:00
• I added a link. Sadly I do not know about the history of that subject. – mvw Apr 27 '17 at 15:05