# Convergence/Divergence of Sequence defined by a recurrence relation

Given the following sequence: $$a_{n+1} = a_n(2 - a_n)$$ for which values $a_1 \in \mathbb{R}$ does this sequence converges or diverges.

By trial and error I found that for $a_1 \in (0, 2)$ it converges to $1$, for $a_1 \in \{ 0 , 2 \}$ it converges to $0$ and for all other values it goes to $-\infty$.

But how can we prove these facts? If a limit exists then I can show that it must be $1$ or $0$ by the following calculation. It holds \begin{align*} \lim_{n \to \infty} a_{n+1} = \lim_{n\to \infty} a_n(2-a_n) \end{align*} So if $\lim_{n\to \infty} a_n = a$, then $$a = 2a - a^2 \Leftrightarrow a^2 = a \Leftrightarrow a = 1 \lor a = 0.$$ But how to show that a limit exists when $a_1 \in (0,2)$, and there is no limit when $a_1 < 0$ or $a_1 > 2$?

-
how about investigating fixed points of $y=x(2-x)$ – Maesumi Feb 11 '13 at 19:04
fixed points are points such that $x = x(2-x)$, and from this it follows that $x = 1$ or $x = 0$. I already done this analysis to determine the possible limits, I posted it too. – Stefan Feb 11 '13 at 19:08
@Stefan I believe Maesumi may have meant something slightly more subtle, namely, to investigate the dynamic behavior of your map, meaning, checking for which $x$, iterating the map $x\mapsto x(2-x)$ leads to the fixed point $1$, for which it leads to the fixed point $0$, and for which it does something different. This, naturally amounts to the same thing as what you are asking, but thinking of this as a question about dynamical systems and fixed points may give you a different set of tools that may be useful to solve your problem. – Andrés Caicedo Feb 11 '13 at 19:39
I meant this type of graphical analysis . – Maesumi Feb 11 '13 at 21:37

Now that you have a guess for what the limit should be, try making a substitution to reflect that. In this case, let

$$a_n = 1 + b_n$$

for all $n$. Substituting this in, the original recurrence $a_{n+1} = a_n(2 - a_n)$ becomes

$$1 + b_{n+1} = (1 + b_n)(1 - b_n) = 1 - b_n^2,$$

so that

$$b_{n+1} = -b_n^2.$$

By iterating this recurrence we can solve it explicitly as

$$b_{n+1} = -b_1^{2n}.$$

Thus if $|b_1| > 1$ we see that $b_n \to -\infty$. This is equivalent to the statement

$$a_1 \in (-\infty,0) \cup (2,\infty) \Longrightarrow a_n \to -\infty.$$

If $|b_1| = 1$ then $b_n = -1$ for all $n > 1$. This is equivalent to the statement

$$a_1 \in \{0,2\} \Longrightarrow a_n = 0 \text{ for all } n > 1.$$

Finally if $|b_1| < 1$ then $b_n \to 0$, and this is equivalent to

$$a_1 \in (0,2) \Longrightarrow a_n \to 1.$$

-
Essentially this is taking advantage of the symmetry of the right-hand side $a_n(2-a_n)$ about the point $a_n = 1$. – Antonio Vargas Feb 11 '13 at 19:28
really like your approach, not what I expected by the usual convergence criteria I know. – Stefan Feb 11 '13 at 19:45

You can show that if you ever get a negative number, the sequence will be monotonically decreasing from that point onwards. If it had a limit, that would therefore be negative, and you have proved that the only possible limits are $0$ and $1$. Therefore it cannot have a limit.

You can show that for $a_n\in(0,1)$ the next element in the sequence is still in $(0,1)$ but larger. Since the sequence is bounded and monotonic it must converge to something, and you have proved that $1$ is the only possible limit that's larger than $a_n$.

$a_0=0$ obviously converges to itself, and for symmetry reasons a sequence starting at $a_0>1$ joins with that starting at $2-a_0$ after one step, and therefore has the same limit.

Together, these cases cover everything.

-
I think in your previous to last paragraph you meant "$a_0\in\{0,1\}$ obviously ..." – Andrés Caicedo Feb 11 '13 at 19:42
Actually I meant to leave the $a_0=1$ case unsponen about. There had to be something for the OP to add himself. :-) – Henning Makholm Feb 11 '13 at 19:51