Why does the sequence $a_n = a_{n-1}^2 - 1$ end up in $0,-1,0,-1,\cdots$? 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?

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