Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Recurrence relation, Fibonacci numbers

could someone possibly help me prove. thankyou.

$(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$.

prove $a_n$ and $a_{n+1}$ are coprime for $n \in \mathbb N$

so far i have:

$a_1 = a_2 = 1$

$a_3 = 3$

$a_4 = 11$

$a_5 = 41$

share|improve this question

marked as duplicate by amWhy, Henry T. Horton, Micah, froggie, Thomas Nov 20 '12 at 23:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

have you tried using induction? –  user31280 Nov 20 '12 at 22:19
yup but it ended up gettin really messy and i got more confused then anything, im assuming the best way would be by contradiction? –  james Nov 20 '12 at 22:21
james: please see the question linked above as a duplicate: your question is asked and addressed in that post. –  amWhy Nov 20 '12 at 22:28
thankyou i just skimmed through that and it is the same question, ive completed all the sections, however, cant seem to prove why they're coprime? –  james Nov 20 '12 at 22:30

1 Answer 1

For every $n$, $a_{n+2}\color{red}{a_n}-a_{n+1}\color{red}{a_{n+1}}=2$ hence Bézout says that the gcd of $\color{red}{a_n}$ and $\color{red}{a_{n+1}}$ is either $1$ or $2$. Since every $a_n$ is odd, this gcd is $1$.

share|improve this answer
could you possibly send me the reference for bezouts lemma please? –  james Nov 20 '12 at 22:24
The thing that requires some work is to show the $a_i$ are integers. –  André Nicolas Nov 20 '12 at 22:37
That's not by Bezout's Lemma but, rather, by definition, a $\rm\,\bf GCD\,$ is a $\rm\,{\bf C}ommon\ {\bf D}ivisor,\,$ hence $$\rm\:d = gcd(\color{#C00}{a_n},\color{#0A0}{a_{n+1}})\mid \color{#C00}{a_n},\color{#0A0}{a_{n+1}}\Rightarrow\:d\mid a_{n+2} \color{#C00}{a_n} - a_{n+1}\color{#0A0}{a_{n+1}}\! = 2$$ –  Bill Dubuque Nov 20 '12 at 22:44
@did: I first learned the result $50$ years ago, but it’s only in the last year that I learned that it’s known as Bézout’s lemma. –  Brian M. Scott Nov 20 '12 at 23:05
@Bill: I know perfectly well that what’s needed for the argument isn’t Bézout’s lemma; I was responding only to did’s surprise that someone would need a reference for that name. –  Brian M. Scott Nov 20 '12 at 23:32

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