The sequence $(u_n)$: $u_1=1, u_2=a>1$ and $u_{n+2}=(1+u_{n+1}^2)/u_n.$

Question

The sequence $(u_n)$ is defined by the formula: $$\left\{\begin{array}{cc} u_1=1, u_2=a>1\\ u_{n+2}=\frac{1+u_{n+1}^2}{u_n}\end{array} \right.$$ Find a so that $u_n$ is integers for all $n \in \mathbb{N}$.

I see $u_1=1; u_2=a; u_3=1+a^2$ and $$u_4=\dfrac{1+(a^2+1)^2}{a}=\frac{2}{a}+a^3+2a$$

$a$ is an integer and $a>1$. To $u_4$ is an integer, $\frac{2}{a}$ is an integer. So, $a=2$

That's only necessary condition.

I have trouble with proving sufficient condition. It means to prove if $a=2$ then $u_n$ is integer for all natural $n$.

Answer 1

Let $(F_n)_{n\geqslant0}$ be the Fibonacci sequence. Then you always have$$F_{2n-1}^{\,2}=F_{2n+1}F_{2n-3}-F_2^{\,2}=F_{2n+1}F_{2n-3}-1.$$In other words$$F_{2n+1}=\frac{F_{2n-1}^{\,2}+1}{F_{2n-3}}.$$Besides, $F_1=1$ and $F_3=2$. Therefore, the sequence $(u_n)_{n\in\Bbb N}$ is the sequence $(F_{2n-1})_{n\in\Bbb N}$, which is a sequence of natural numbers.

Answer 2

From given equation we can easily get this equation:$${u_{n+2}+u_{n}\over u_{n+1}} = {u_{n+1}+u_{n-1}\over u_{n}}$$ Since this is valid for all $n$ we have $${u_{n+2}+u_{n}\over u_{n+1}} = {u_{3}+u_{1}\over u_{2}} = {a^2+2\over a}$$ and thus we have a linear equation: $$ u_{n+1} = {a^2+2\over a}u_{n}-u_{n-1}$$ from which is easy to see $u_n\in \mathbb{N}$ for all $n$ if $a\mid a^2+2$, i.e. $a=2$ (use induction).