# fibonacci question [duplicate]

Possible Duplicate:
Recurrence relation, Fibonacci numbers

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

$(i)$ Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ are coprime for $n \in \mathbb N$

$(ii)$ Assume that the set $\{a_n , a_{n+1} , a_{n+2}\}$ is pairwise coprime for $n \in \mathbb N$. Prove that all $a_n$ are integers by induction.

$(b)$ Consider the recurrence relation $a_{n+2}a_n = a^2_{n+1} + 1$ with $a_1 = 1, a_2 = 2$ and compare this sequence to the Fibonacci numbers. What do you find? Formulate it as a mathematical statement and prove it.

-

## marked as duplicate by Douglas S. Stones, Ross Millikan, martini, Martin Argerami, Noah SnyderNov 19 '12 at 22:38

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.

What have you tried? Have you at least computed the first dozen terms? –  Ross Millikan Nov 19 '12 at 17:30
You should really do some initial work! Because for example statement (i) is easy to show: by induction show they are odd, then use a simple divisibility argument do finish via induction that two adjacent terms are coprime. –  coffeemath Nov 19 '12 at 17:33

## 1 Answer

(a.i) you use simple induction. you have the basis for $a_1 = a_2 = 1$ and from the relation you can easily see that if the $a_k$ are all odd until $n+1$ then $a_{n+2}$ must be odd. Also if $a_{n+2} |c$ and $a_{n+1} |c$ then $c(\frac{a_{n+2}}{c}a_n-\frac{{a_{n+1}}^2}{c})=2 \Rightarrow c\in\{2 , 1\}$ but since $a_n$ are odd then $c=1$

-
i tried using induction for question (a.i), for the basis step i got a_{3} = 3 which is odd. however for the inductive step i ended up with a^2_{n+1} + a_{n+3}a_{n+2} = a^2_{k+2} .... and didnt really know where to go from there?? –  shingi Nov 19 '12 at 17:44
basis step: a_1 = a_2 = 1 are odd. Inductive step: assume every element up until k is odd then (a_k a_{k-2}) = (a_{k-1})^2 + 2 from the assumption we get that (a_k a_{k-2}) = odd number and since also a_{k-2} is odd then a_k must be odd as well –  user44874 Nov 19 '12 at 20:34
@user44874 I think you grabbed the wrong equation. For (a.i) you should use the first equation, with the +2, so your final equation should = 2. That's why all the terms being odd matters. You get c divides 2, and since the a_i are odd, c=1. –  Zimul8r Nov 19 '12 at 20:41
@Zimul8r, yes thanks –  user44874 Nov 19 '12 at 21:39
$$a_{1}=1 ,a_{2}=1,a_{3}=2,a_{4}=3,a_{5}=5,a_{6}=8,is it correct ? a_{n+2}a_{n}=(a_{n+1})^2+1$$for example :$$n=4,a_{6}a_{4}=8*4=24 , (a_{5})^2+1=5^1+1=26 ,24 \neq 26$$ –  Khosrotash Nov 7 '14 at 7:27