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.

$(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
4  
This looks like a homework assignment. If so, please tag it as such - people will still help, but will probably not provide a complete solution, unless you explain how far you have progressed with the problem, and what exactly is causing you problems. –  Old John Nov 13 '12 at 18:32
3  
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the homework tag; people will still help, so don't worry. Also, many find the use of imperative ("Prove", "Solve", etc.) to be rude when asking for help; please consider rewriting your post. –  Austin Mohr Nov 13 '12 at 18:32
1  
(ii) is kind of strange : the notion of coprimality doesn't really make sense for non-integers, so in some sense it's making the statement: 'assume $\{a_n, a_{n+1}, a_{n+2}\}$ are integers for all $n\in\mathbb{N}$; prove that all $a_n$ are integers.' –  Steven Stadnicki Nov 13 '12 at 19:10
    
I noticed that in part (b) the $a_6 = 121/2$ is not an integer. –  sperners lemma Nov 13 '12 at 19:42
    
@spernerslemma It's subtle but the recurrence is changed in part b. (+2 becomes +1) –  EuYu Nov 13 '12 at 19:52
show 2 more comments

1 Answer

Here is a hint how to solve (i).

We are given the recurrence $$a_1 = 1,\, a_2 = 1,\, a_{n-1} a_{n+1} = a_n^2 + 2$$

Lemma When $n > 1$, $a_{n} < a_{n+1}$. proof: By induction assume $a_{n-1} < a_n$. $$a_{n+1} = \frac{a_n^2+2}{a_{n-1}} > \frac{a_n^2+2}{a_{n}} = a_n+\frac{2}{a_{n}} > a_n.$$

Corollary When $n > 2$, $a_n > 2$.

Theorem $a_n$ are all integers. proof: We have

  • $a_{n-1} a_{n+1} = a_{n}^2 + 2$
  • $a_{n-2} a_{n} = a_{n-1}^2 + 2$
  • $a_{n-3} a_{n-1} = a_{n-2}^2 + 2$

thus $a_{n-1}$ divides $a_{n-2}a_n - 2$ and $a_{n-2}^2+2$ thus it divides their sum: $a_{n-1}|a_{n-2}(a_{n-2}+a_n)$ multiply by $a_n$ to get $a_{n-1}|(a_{n-1}^2+2)(a_{n-2}+a_n)$ but $a_{n-1}\not|(a_{n-1}^2+2)$ [if it did then we would have $a_{n-1}|2$ which is a contradiction] so we deduce $a_{n-1}|a_{n-2}+a_n$. Squaring gives $a_{n-1}|a_{n-2}^2+2a_{n-2}a_n+a_n^2$ which we can rewrite to $a_{n-1}|a_{n-2}^2+2a_{n-1}^2+4+a_n^2$ but we already know $a_{n-1}|a_{n-2}^2+2+2a_{n-1}^2$ [since both $a_{n-2}^2+2$ and $2a_{n-1}^2$ are multiples of $a_{n-1}$] so we conclude that $a_{n-1}|a_{n}^2+2$.

Lemma $a_n$ are odd. proof: Let $o_i \equiv a_i \pmod 2$ this definition is valid due to $a_i$ being integers) then assume by induction $o_i = 1$ for all $i \le n$. Then clearly $o_{n+1} \equiv o_{n-1}^{-1}(o_{n}^2+2) \equiv 1^{-1} (1^2+0) \equiv 1 \pmod 2$.

Lemma For $n > 1$, $a_{n-1}$ and $a_{n}$ are coprime. proof: Suppose they were not, since the sequence is strictly increasing we have $a_{n-1}|a_{n}$ thus $a_{n-1}|a_{n-2}a_{n} = a_{n-1}^2+2$ thus $a_{n-1}|2$ contradiction.

share|improve this answer
    
im confused where did a_{n-1} a_{n+1} = a_n^2 + 2$$ come into this? –  simon Nov 13 '12 at 19:52
    
@simon, I don't understand what you are asking. That formula is the definition of the recurrence. –  sperners lemma Nov 13 '12 at 19:54
    
the formula from the question is a_{n+2}a_n = a^2_{n+1} +2 –  simon Nov 13 '12 at 19:55
1  
@simon The index is just shifted if that's where your confusion is from. Replace $n$ by $n+1$ and you recover your recurrence. –  EuYu Nov 13 '12 at 20:00
1  
@EuYu ohhhh okay thankyouu :) makes sense now! –  simon Nov 13 '12 at 20:09
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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