# 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.

-
(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
@EuYu, so it's going odd, even, odd, even, .. and so we get odd/even! thanks. – sperners lemma Nov 13 '12 at 19:55
@spernerslemma Yea. From a brief inspection, it seems like the sequence of odd Fibonacci numbers $F_{2n+1}$ – EuYu Nov 13 '12 at 19:56

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.

-
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
@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
@EuYu ohhhh okay thankyouu :) makes sense now! – simon Nov 13 '12 at 20:09