3
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Hint: use induction. $\endgroup$ – lulu Apr 27 '17 at 14:09
  • $\begingroup$ @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. $\endgroup$ – jrs Apr 27 '17 at 14:15
  • 3
    $\begingroup$ 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})$ $\endgroup$ – lulu Apr 27 '17 at 14:16
  • 2
    $\begingroup$ @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$." $\endgroup$ – Arthur Apr 27 '17 at 14:18
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.