1
$\begingroup$

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.

  • 0
    http://math.stackexchange.com/questions/240712/recurrence-relations-question2012-11-19

1 Answers 1

2

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

  • 0
    $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 $2014-11-07