<s>[INST] Explicit solution of the recursion $x_n = x_{n-1}^2 - 2$ with $x_0>2$ Let $m>2$ be an integer, $x_0 = m$ and $x_n = {(x_{n-1})}^2 - 2$ for $n > 0.$ Prove that $x_n=\lceil\tau(n) \rceil$, where $\tau(n) = α^{2^n}$ and $\alpha >1$ satisfies $\alpha + \frac{1}{\alpha} = m$.
This is the problem.  The only thing I can think of is that it could have something to do with $\varphi$, since for $m=3$ we have $x(n)=\lceil\left(\varphi^2\right)^n\cdot \varphi) \rceil$, $\alpha = \varphi^2$. Other than that I have no idea how to move on. Thanks in advance
 [/INST] From $x_0=m=\alpha + \frac{1}{\alpha}$ we have
$$x_1=m^2-2=\alpha^2+\frac{1}{\alpha^2}$$
And from $\alpha^2-m\alpha+1=0$ we have $$\alpha=\frac{m+\sqrt{m^2-4}}{2}\Rightarrow \alpha^2=\frac{m^2-2+m\sqrt{m^2-4}}{2}$$
which satisfies, from (easy to check) $m^2-4<m\sqrt{m^2-4}<m^2-2$: $$m^2-3<\alpha^2<m^2-2$$
So, we conclude
$$x_1=m^2-2=\alpha^2+\frac{1}{\alpha^2}=\left \lceil \alpha^2 \right \rceil$$
Then, inductively and recursively, we do the same steps with $m_1=x_1=\beta+\frac{1}{\beta}>2$, where $\beta=\alpha^2$ to conclude:
$$x_2=m_1^2-2=\beta^2+\frac{1}{\beta^2}=\left \lceil \beta^2 \right \rceil$$
Or
$$x_2=x_1^2-2=\alpha^4+\frac{1}{\alpha^4}=\left \lceil \alpha^4 \right \rceil$$
$$x_3=x_2^2-2=\alpha^8+\frac{1}{\alpha^8}=\left \lceil \alpha^8 \right \rceil$$
$$...$$
$$x_n=x_{n-1}^2-2=\alpha^{2^n}+\frac{1}{\alpha^{2^n}}=\left \lceil \alpha^{2^n} \right \rceil$$
</s>