# Recurrence relation, monotonicity and convergence

I was looking for some exercise on recurrence and I found this:

Let \begin{equation} \begin{cases} x_{n+1} = e^{-x^2_{n}}\\ x_0 = a\in\mathbb{R} \end{cases} \end{equation} be a recurrence relation with the parameter $a$.

1. Discuss monotonicity of $\{x_n\}_{n\in\mathbb{N}}$
2. Determine whether $\{x_n\}_{n\in\mathbb{N}}$ is convergent or not

Now, I really can't figure out ho to proof whether $\{x_n\}_{n\in\mathbb{N}}$ is monotonic or not.

I saw on Mathematica and saw for any $a$ I typed the function was neither crescent nor decrescent, but how to prove it? What's the best path to follow for a Calculus I student?

# EDIT:

As I really can't made my mind up about this exercise, does anyone can provide a full rigorous mathematic proof for the answer (which basically we all know: the recursion is not monotonic and it is convergent)? Thanks in advance.

• It clearly can't be always monotonic, since $x_1\in(0,1]$ and $x_1$ is the same if we replace $a$ with $-a$. So, for example, $a=1$ gives $x_1<x_0$ and $a=-1$ gives $x_1>x_0$. But beyond the first term, it might be monotonic. Jul 6, 2017 at 14:32
• Yes, I know, but besides the problem of the parameter there's the one of the proof that's monotonic (or that it is not)... Jul 6, 2017 at 14:41

As $x_n>0$ for $n\geq 1$, we may suppose that $a\geq 0$. Let $f(x)=\exp(-x^2)$ on $I=[0,+\infty[$.

Note that $f$ is strictly decreasing; one can show that the equation $f(x)-x=0$ has only one solution on $I$, say $L$.

a) Suppose now that $x_n$ is increasing. Then we have $x_{n+1}\geq x_n$, and $x_{n+2}\geq x_{n+1}$. Applying the (decreasing) function $f$ to the first inequality gives $x_{n+2}\leq x_{n+1}$. So we have $x_{n+2}=x_{n+1}=f(x_{n+1})$. This show that $x_{n+1}=L$. Now $L=\exp(-x_n²)=\exp(-L^2)$ gives $x_n=L$, and finally $x_0=a=L$. Same thing if $x_n$ is decreasing. So $x_n$ is monotonic if and only if $a=L$, and then $x_n=L$ for all $n$.

b) One can show that for any $a$, $x_{2n}$ and $x_{2n+1}$ are monotonic, one increasing, the other decreasing. To see why, note that $g(x)=f(f(x))$ is increasing and that $x_{2n+2}=g(x_{2n})$. If you suppose that $x_4\geq x_2$, an easy induction show that $x_{2n+2}\geq x_{2n}$ for all $n$, and $x_{2n}$ is increasing. If $x_4\leq x_2$, $x_{2n}$ is decreasing. As $x_{2n+1}=f(x_{2n})$, this show that $x_{2n+1}$ is monotonic too.

c) Note that $x_n\in [0,1]$ for all $n\geq 1$. So by b) $x_{2n}$ and $x_{2n+1}$ are bounded monotonic sequences, hence convergents, say to $L_1$ and $L_2$. To show that $x_n$ is convergent, we have to show that $L_1=L_2$; this seems complicated.

d) Another way to prove the convergence: Compute $f^{\prime}(x)=-2x\exp(-x^2)$. Then we see that $|f^{\prime}(x)|\leq k=\sqrt{2}\exp(-1/2)<1$. Then $|x_{n+1}-L|=|f(x_n)-f(L)|\leq k|x_n-L|$, and it is easy to prove the convergence.

• In point c) how could you say that as the two functions are bounded they are convergent? Jul 6, 2017 at 17:42
• Look at $x_{2n}$. We have $0\leq x_{2n}\leq 1$. If $x_{2n}$ is increasing, then as $x_{2n}\leq 1$, it is convergent. If $x_{2n}$ is decreasing, then as $x_{2n}\geq 0$, it is convergent. The same for $x_{2n+1}$. Jul 7, 2017 at 6:16

If you draw the function $e^{-x^2}$ and the line $y=x$,

you can easily realize that your recurrence is given by the abscissas of the points $P_0,\;P_1,\; P_2,\; \cdots$.

Whatever be the starting point $x_0$, you will enter, from $x_1$, onwards into the "spiral" which is fully contained within the square $(0,0),(1,1)$.

The sequence will always converge to $F_{\infty}=(\exp{(-W(2)/2)},\exp{(-W(2)/2)})$, where

• W(x) indicates the Lambert W function;
• $x_{\infty}=\exp{(-W(2)/2)}$ is the solution to $x=\exp{(-x^2)}$.

If the absolute value of entry point $|x_0|$ is to the left of $x_{\infty}$ then $x_{2n} \le x_{\infty} \le x_{2n+1}$, and viceversa.

Note :

The above is one of the classical methods to compute the zeros of a function.
However it is "rigorous" based on the mathematical backgrounds / conditions provided by Numerical Analysis, and standing that $y_1=e^{-x^2}$ is decreasing in $0 < x < \infty$ and $0<y \le 1$, while $y_2=x$ is increasing with derivative $=1$ greater than $|y_1'|$, and the existence of the fixed point $P_{\infty}$ is so guaranteed, etc. (I am not going to expose the full theoretical background here)

• Can't understand what $F_{\infty}=(\exp{(-W(2)/2)},\exp{(-W(2)/2)})$ is and whether is there a more "rigorous" method to determine the non monotonicity of the recursion. Thanks anyway. Jul 6, 2017 at 17:28
• I mean who are those $W$? Jul 6, 2017 at 17:59
• @opisthofulax I added some more explanations, hope they are clear Jul 6, 2017 at 18:08