Why does the sequence $a_n = a_{n-1}^2 - 1$ end up in $0,-1,0,-1,\cdots$?

Question

I have this recurrence relation:

$$a_n=a_{n-1}^2-1$$

I can see that this sequence stays constant if $a_0=\phi$ or $1-\phi$ and it can also stably continue like $0,-1,0,-1,\cdots$. ($\phi=\frac{1+\sqrt{5}}2)$

The sequence will diverge to $+\infty$ if $|a_0|>\phi$.

I observed that whenever $a_0$ isn't $\pm\phi$ or $\pm(1-\phi)$ and $|a_0| \le \phi$, the sequence will converge to $0,-1,0,-1,\cdots$, no matter how close $a_0$ is to $\pm\phi,\pm(1-\phi)$. This makes sense to me intuitively, although I can't find a mathematical explanation.

How do I prove this, and which theory deals with this kind of problems?

Note that you are not using standard terminology here: a sequence converges to one value (or it doesn't converge), it can't converge to a sequence. What you mean is that the terms get closed to e.g. $(-1)^k$ for growing $k$ (in the first picture). — ViktorStein, Mar 11 '22 at 11:45
@Ramanujan Standard terminology for the phenomenon here is that the sequence oscillates between values near $0$ and values near $-1$. — Peter, Mar 11 '22 at 11:48
See https://math.stackexchange.com/questions/3466935/finding-julia-set-of-fz-z2-1 — lhf, Mar 11 '22 at 12:46
What if you find a value of $\epsilon$ such that $a_0=\phi-\epsilon$ eventually becomes $\phi-1$? Then it would stabilize? — JMP, Mar 11 '22 at 13:34

score 1 · Answer 1 · answered Mar 11 '22 at 12:59

You are looking at iterations of your function on the interval $[-\phi,\phi]$. Y ou can renormalize so that the interval becomes $[0,1]$ by taking

$$b_{n} := \frac{1}{2} - \left(\frac{\phi}{2} - \frac{1}{2}\right) a_n.$$

You then easily find that

$$b_{n+1} = \lambda b_{n} (1 - b_{n})$$

where

$$\lambda = 2 \phi = 3.23607\ldots $$

This is now a special case of (iterations of) the logistic map (https://en.wikipedia.org/wiki/Logistic_map), and the behavior in this special case is as you predict. (You can certainly prove this case directly, but just connecting the problem to a more well-known problem if you are interested.)

Astyx · Answer 2 · 2022-03-11T13:18:24.347

Let $f(x) = x^2-1$. Assume $x = \phi+\epsilon$ for some $\epsilon\ne0$. Then $$|f(\phi+\epsilon)-\phi| = |f(\phi+\epsilon)-f(\phi)| = |\epsilon f'(\phi) + o(\epsilon)|\,.$$

Since $f'(\phi) = 1+\sqrt{5}\gt 1$, this implies that if $a_n$ converges to $\phi$, then it stabilizes to $\phi$. It is then easy to see that this happens only if $a_0\in \{\phi, -\phi\}$.

The same reasoning yields the same result for $1-\phi$.

Let $g(x) = f(f(x))$. You can see that $|g(x)+1| = |g(x)-g(-1)| < |x+1|$ for all $x\in [-\phi, 1/2]$. Thus for $a_{0}$ in this interval, $a_{2n}$ converges to $-1$.

You can show a similar result for $0$. I think (I have not had the time to check yet) that these interval are not adjacent, but studying what happens in the remaining interval should not be a problem.

Why does the sequence $a_n = a_{n-1}^2 - 1$ end up in $0,-1,0,-1,\cdots$?

2 Answers2