Solving a nonlinear recurrence: $a_n = a_{n-1}^2 -2$ 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!
 A: 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.
A: 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}}$$
