Solving a nonlinear recurrence: $a_n = a_{n-1}^2 -2$

Question

This particular recurrence showed up as part of a Putnam problem last year. We are asked to solve $a_k = a_{k-1}^2 -2$ with $a_0 = 5/2$.

I know the solution is $a_k = 2^{2^k} + 2^{-2^k}$. However, all they say is "using the identity $(x+x^{-1})^2 - 2 = x^2 + x^{-2}$, we find by induction $a_k = 2^{2^k} + 2^{-2^k}$".

I'm unsure of how that yields a solution so quickly. I understand that the similarity between the identity and the recurrence may prompt one to guess that $a_k$ is of the above form, but I am not sure of how to solve that completely.

Additionally, this method seems a little bit ad hoc. Would it be a relatively simple task to use more straightforward methods if one did not notice this pattern? For example, what if the recurrence were $a_k = a_{k-1}^2 -3$ instead?

Finally, are there any good books on solving recurrences like this? The wikipedia page on recurrence relations actually has a lot of useful information for solving many different recurrences, but I could not find a method for this particular recurrence.

Thanks!

Answer 1

The trick is to recognize the duplication formula for the cosine function. In general, we have $$ \cos(2\theta) = 2\cos^2(\theta)-1,\qquad \cosh(2x)=2\cosh^2(x)-1 \tag{1}$$ so by assuming $a_n = 2\cosh(x_n)$ we get $\color{blue}{a_{n+1}=2\cosh(2x_n)}$.
Since $x_0=\text{arccosh}\tfrac{5}{4}$ and $\exp\text{arccosh}\tfrac{5}{4}=\color{blue}{2}$, $$ a_n = 2\cosh\left(2^n\text{arccosh}\tfrac{5}{4}\right)=\color{blue}{2^{2^n}+2^{-2^n}}\tag{2}$$ as wanted. This is essentially the only case of the logistic map leading to a simple closed form.

Answer 2

The induction basis is easy: $2^{2^0}1+2^{-2^0}=2+\frac12=\frac52$

Now assume $a_n= 2^{2^n}+2^{-2^n}$. Then letting $x = 2^{2^n}$ in the identity, we have $$ a_n^2-2 = \left(2^{2^n}+2^{-2^n}\right)^2-2 = (x+x^{-1})^2 -2 \\ = x^2 + x^{-2} = \left(2^{2^n}\right)^2 +\left(2^{-2^n}\right)^2 \\= 2^{2\cdot 2^n} +2^{-2\cdot 2^n} = 2^{2^{(n+1)}}+2^{-2^{(n+1)}} = a_{n+1} $$ so the induction is established.

In general, non-linear recurrences are difficult, and since superposition does not hold, there is not a lot of generic technique for solving them. But $$a_n= a_{n-1}^2 - k$$ can be attacked successfully by the substitution $$b_n= \frac{a_n}{2^{2^n}}$$