Recurrence. Nonhomogeneous recurrence relation.

Question

Given the following recurrence relation: $$ {a_{n+1}}={(a_{n})}^2-2 ,\\a_0=\frac{5}{2}$$ Prove that $\left \lfloor{a_{n}}\right \rfloor $ is a power of 2 for every natural number n, using recurrence equation transformations ( i.e. without induction).

Answer 1

Let us use the Ansatz that $\,a_n = b_n + b_n^{-1}\,$ which implies $\, a_n^2 = b_n^2 + b_n^{-2} + 2\,$ and hence $\,a_n^2 - 2 = b_n^2 + b_n^{-2}.\,$ Using the $\,a\,$ recurrence $\,a_{n+1} = a_n^2-2,\,$ we get that $\,b_{n+1} = b_n^2\,$ with $\,b_0 = 2^1.\,$ Solving this $\,b\,$ recurrence and, using the inequality $\,0 < b_n^{-1} < 1,\,$ we find that $\,b_n = 2^{2^n} = \lfloor a_n \rfloor.\,$ As a comment to the question notes, this is essentially a duplicate question.

Answer 2

Hint: Use induction to show that \begin{eqnarray*} a_n= \frac{2^{2(n+1)}+1}{{2^{n+1}}}. \end{eqnarray*}