recurrence work

Question

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$

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
james, see also http://math.stackexchange.com/questions/240724/fibonacci-question?lq=1 — amWhy, Nov 20 '12 at 22:38

score 1 · Answer 1 · answered Nov 20 '12 at 22:21

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

answered Nov 20 '12 at 22:21

Did

279,727

1

could you possibly send me the reference for bezouts lemma please? – james Nov 20 '12 at 22:24
Surely you are joking. – Did Nov 20 '12 at 22:30
2

The thing that requires some work is to show the $a_i$ are integers. – André Nicolas Nov 20 '12 at 22:37
ohh sorry part of the question i didnt write up, says to assume they are all integers – james Nov 20 '12 at 22:38
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$$
– Bill Dubuque Nov 20 '12 at 22:44
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. – Brian M. Scott Nov 20 '12 at 23:05
@Brian Again, that's not Bezout's Lemma! – Bill Dubuque Nov 20 '12 at 23:28
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. – Brian M. Scott Nov 20 '12 at 23:32
@Brian Ah, I see. Did you know it by some other name? – Bill Dubuque Nov 21 '12 at 01:46
1

@Bill: No, I never had a name for it at all. – Brian M. Scott Nov 21 '12 at 04:40

recurrence work

1 Answers1