0
$\begingroup$

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$

  • 1
    have you tried using induction?2012-11-20
  • 0
    yup but it ended up gettin really messy and i got more confused then anything, im assuming the best way would be by contradiction?2012-11-20
  • 0
    james: please see the question linked above as a duplicate: your question is asked and addressed in that post.2012-11-20
  • 0
    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?2012-11-20
  • 1
    james, see also http://math.stackexchange.com/questions/240724/fibonacci-question?lq=12012-11-20

1 Answers 1

0

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$.

  • 1
    could you possibly send me the reference for bezouts lemma please?2012-11-20
  • 0
    Surely you are [joking](http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity).2012-11-20
  • 2
    The thing that requires *some* work is to show the $a_i$ are integers.2012-11-20
  • 0
    ohh sorry part of the question i didnt write up, says to assume they are all integers2012-11-20
  • 1
    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$$2012-11-20
  • 1
    @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*.2012-11-20
  • 0
    @Brian *Again*, that's *not* Bezout's Lemma!2012-11-20
  • 2
    @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.2012-11-20
  • 0
    @Brian Ah, I see. Did you know it by some other name?2012-11-21
  • 1
    @Bill: No, I never had a name for it at all.2012-11-21