Recurrence relation, Fibonacci numbers [duplicate]
$(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.
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.