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.

  • 3
    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.2012-11-19
  • 0
    http://math.stackexchange.com/questions/236578/recurrence-relation-fibonacci-numbers/2366342012-11-19
  • 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
    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??2012-11-19
  • 0
    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 well2012-11-19
  • 0
    @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.2012-11-19
  • 0
    @Zimul8r, yes thanks2012-11-19
  • 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