3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Recurrences like this can't be solved except in a few very special cases, each with its own unique ad hoc method, hence no book. $\endgroup$ – Ivan Neretin Nov 30 '16 at 17:39
  • $\begingroup$ Well, that is rather unfortunate. $\endgroup$ – Rellek Nov 30 '16 at 17:41
  • 1
    $\begingroup$ Come to think of it, the recurrence $z_{n+1}=z_n^2+C$ is responsible for the creation of Mandelbrot set, which spawned a whole new area of study, but that's another story. $\endgroup$ – Ivan Neretin Nov 30 '16 at 17:45
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for saving me the trouble of having to write this :-) $\endgroup$ – Jyrki Lahtonen Nov 30 '16 at 18:07
2
$\begingroup$

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}}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.