I have a problem . The exercise says:
Show that the recurrence $$\begin{align*}&X_0=m\;,\\&X_n=X_{n-1}^2-2\;,\qquad\text{for }n>2\;,\end{align*}$$ has a solution $X_n=\left\lceil\alpha^{2^n}\right\rceil$, if $m$ is an integer greater than $2$, where $\alpha+\alpha^{-1}=m$ and $\alpha>1$. For example, if $m = 3$ the solution is $$X_n=\left\lceil\varphi^{2^{n+1}}\right\rceil\;,\qquad\varphi=\frac{1+\sqrt5}2\;,\qquad\alpha=\varphi^2\;.$$
Well I have found that
$$\begin{align*} &X_1=m^2-2\\ &X_2=(m^2-2)^2-2\\ &X_3=\left((m^2-2)^2-2\right)^2-2\\ &\;\vdots \end{align*}$$
THEN
$$\begin{align*} \alpha+\alpha^{-1}&=m\iff \alpha^2+\alpha^{-2}+2=m^2\iff \alpha^2+\alpha^{-2}=X_1\\ \left(\alpha^2+\alpha^{-2}\right)^2&=X_1^2\iff X_2=\alpha^4+\alpha^{-4}\\ &\;\;\vdots \end{align*}$$
I guess that $X_n=\alpha^{2^n}+\alpha^{-2^n}$, where $\alpha>1$ and $n>0$. That clearly holds for $n=0,1,2$.
Let’s say that it holds for $n$ and it must hold for $n+1$. By induction we see that
$$X_{n+1}=X_n^2-2=\alpha^{2^{n+1}}+\alpha^{-2^{n+1}}+2-2=\alpha^{2^{n+1}}+\alpha^{-2^{n+1}}$$
Now how do I prove that $X_n$ is an integer (which it must be) and what must I do to end in the answer that the exercise asks for?
You’ve shown that $X_n=\alpha^{2^n}+\alpha^{-2^n}$ for each $n\in\Bbb N$. On the other hand, it’s clear from the definition that $X_n$ is an integer for each $n\in\Bbb N$, so $\alpha^{2^n}+\alpha^{-2^n}$ is an integer for each $n\in\Bbb N$. We’re told that $\alpha>1$, so $0<\alpha^{-1}<1$, and therefore $0<\alpha^{-2^n}<1$ for each $n\in\Bbb N$. Thus,
$$X_n-1<X_n-\alpha^{-2^n}=\alpha^{2^n}<X_n\;,$$
where $X_n-1$ and $X_n$ are consecutive integers, and it follows immediately that
$$X_n=\left\lceil\alpha^{2^n}\right\rceil\;.$$