# 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

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