Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

marked as duplicate by Douglas S. Stones, Ross Millikan, martini, Martin Argerami, Noah Snyder Nov 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
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. –  coffeemath Nov 19 '12 at 17:33
    
    

1 Answer 1

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

share|improve this answer
    
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.