1

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).

user96160
  • 33
  • I tried using the transformation of the equation, but can't arrive to an explicit formula: $$ {a_{n+1}+1}={(a_{n}-1)}{(a_n+1)} $$ $$ b_n = a_n+1 $$ $$ {b_{n+1}}={(b_{n}-2)}{(b_n)} $$ $$ {b_{n+1}}={(b_{n})^2-2b_n} $$ – user96160 Dec 16 '19 at 21:53
  • $a_{n}=2^{n+1}+\dfrac1{2^{n+1}}$ – J. W. Tanner Dec 16 '19 at 23:02
  • I keep getting $$a_n = 2^{2^{n}} + \left(2^{2^n}\right)^{-1}$$ but all answers say otherwise. Did I do something wrong? – peterwhy Dec 16 '19 at 23:18
  • @peterwhy that's because you are correct and the question is a dup. – rtybase Dec 16 '19 at 23:19

2 Answers2

2

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

Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73
  • Yes, that would work. But I am supposed to find a solution by only manipulating the recurrence equations, I missed that part. – user96160 Dec 16 '19 at 22:00
2

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.

Somos
  • 35,251
  • 3
  • 30
  • 76