# recurrence work [duplicate]

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$

-

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

This question was marked as an exact duplicate of an existing 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
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$.
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