# On convergence of a recursively defined sequence

For $\alpha \in \mathbb{R}$, define the sequence $\{x_n \}$ by $x_1 = \alpha$, and $x_{n+1} = x_n^2 - 1$. It is true that if the sequence converges, then it must converge to $(1 \pm \sqrt{5} ) /2$. Find all values of $\alpha$ s.t. the sequence converges to $(1 + \sqrt{5} ) /2$.

My main line of attack that I kept returning to was to try to express $x_n$ as a function of $\alpha$, so as to determine what properties $\alpha$ must have for the desired convergence. But the sequence becomes very unweilding as an explicit function of $\alpha$. I've also discovered that convergence will fail for values of $\alpha \in \{1, -1, 0, \}$, but also have trouble determining the all the bad values of $\alpha$. Hints appreciated.

-

Let $\displaystyle \varphi = \frac{1 + \sqrt{5}}{2}$

I get that $\displaystyle \varphi$ and $\displaystyle -\varphi$ are the only two starting values where the sequence converges to $\displaystyle \varphi$.

Consider

$x_{n+1} - x_n = (x_n + \frac{1}{\varphi})(x_n - \varphi)$

Now

If $x_n \gt \varphi$, then $x_{n+1} \gt x_n$. So if the sequence ever goes greater that $\varphi$, it will keep increasing.

If $-\frac{1}{\varphi} \lt x_n \lt \varphi$, then $x_{n+1} \lt x_n$.

If $x_n \lt -\frac{1}{\varphi}$ then $x_{n+1} \gt x_n$.

If the sequence ever goes below $\varphi$ (except for $-\varphi$), then the sequence is "pulled" towards the left or right of $\varphi$, but never towards it (basically always away from it).

Also notice that, there is no starting value for which $x_{n+1} = -\varphi$, as $-\varphi = c^2 -1$ has no real solutions.

Also the only value for $x_n$ which makes $x_{n+1} = \varphi$, is $x_n = \pm \varphi$.

-
The possible limits of the sequence are the roots of $x^2 - x - 1 = 0$, i.e., $x = 1/2 \pm \sqrt{5}/2$. Your $\phi$ is the positive root, but $-\phi$ isn't the negative root. Perhaps you meant the negative root?. –  Patrick Feb 28 '12 at 0:40
@Patrick: No worries, I have deleted my comment. –  Aryabhata Feb 28 '12 at 0:45

There are only two values such that $x_n$ converges to $\alpha = \frac{1 +\sqrt{5}}{2}$ wich are $\alpha$ and $- \alpha$ .

$f(\alpha + h ) = \alpha + h.f'(\alpha) + o(h)$ so there exists $\epsilon$ such that for $|h|<\epsilon$

$$\alpha + h.\frac{(f'(\alpha) +1 )}{2} \leq f(\alpha + h) \leq \alpha + h.(f'(\alpha) +1 )$$

since $f'(\alpha) > 1$ if $0 <|x_n - \alpha| < \epsilon$ there exists $k \geq n$ such that $| x_k - \alpha| \geq \epsilon$ so the only way $x_n$ converges to $\alpha$ is that $(x_n)$ is eventually constant. This happens only for $x_0 =\alpha$ or $-\alpha$

-

$\bf Hint:$ If $(x_n)$ converges then $\lim_{n\to\infty}x_{n+1}=\lim_{n\to\infty}x_n=\alpha$.

-
The question seems a little more complicated. The study of the dynamic associated to a function $f : X \longrightarrow X$ where $X$ is a metric space depends both on the topology of $X$ and the properties of $f$. For example, near a fixed point, the sequences defined by $u_{n+1} = f(u_n)$ will converge to this fixed point if $f$ is "atractive enough". If $f$ is differentiable and $|f'(x)| < 1$ for x our fixed point, the sequence will converge to $x$ for all $u_0$ close enough to $x$. You should try those kinds of ideas... –  Selim Ghazouani Feb 27 '12 at 21:03

An alternate way to illustrate this is to note that the limits are the fixed points of $f(x) = x^2 -1$. A fixed point $x$ is attracting iff $|f'(x)|<1$. The fixed points in this problem are solutions of $x^2 - x - 1 = 0$, and $|f'(x)|= |2x|\ge 1$ for both of those roots, hence they are repelling fixed points. Therefore any other seed value will not lead to a convergent sequence.

-