# How to rigorously prove the convergence of an iterative sequence

Suppose we have an iterative sequence defined by $x_{n+1} = g(x_n)$ where

$$g(x)= \frac{x^4 + 1}{3}$$

and we are looking at the two cases:

1. $x_1 = 0$
2. $x_1 = 1$

While I know that if $x_n \rightarrow a$ as $n \rightarrow \infty$ then $a$ is a fixed point of $g$, ie $g(a)=a$, this lead me to think along the lines of considering the properties of the function $f(x)=g(x) - x$ and trying to use this to help rigorously prove that the sequence does converge to some limit, I haven't much success in writing in argument which I find to be fully satisfactory.

Is this a good method to show that the sequence does converge to the same value for both starting points of $x_n$ - if so, could someone please give a few pointers for the general outline of a proof which can be made rigorously (so please don't talk about how $|g'(a)|< 1$ will suffice, because I fail to see how this can be made rigorous).

Alternatively, if a proof can be done by just using algebra and the definition of the sequence, that would be much more preferable (we were asked this question a while ago before we had came across continuity/differentiability, so I assume it can be done without these ideas rigorously).

-
Convergence can be proved in each case by using induction to show monotonicity and boundedness. Then one can use continuity to evaluate the limits. Alternately, let $(a_n)$ be the first sequence, $(b_n)$ the second. One can estimate $b_n-a_n$. –  André Nicolas Mar 16 '13 at 18:10

Show by induction on $n$ that if $x_1=0$, then $\langle x_n:n\in\Bbb Z^+\rangle$ is non-decreasing and bounded above by $1$, and if $x_1=1$, the sequence is non-increasing and bounded below by $0$. Every bounded monotone sequence in $\Bbb R$ converges, so at that point you’ll know that the limit $a$ exists, and you can use a continuity argument to identify it as a fixed point of $g$.

Take the case $x_1=0$. Note that $x_{n+1}\ge x_n$ iff $\frac13\left(x_n^4+1\right)\ge x_n$ iff $3x_n-x_n^4\le 1$. Suppose that this is the case for some $n\ge 1$. Then $x_n^4+1\ge 3x_n$, and

\begin{align*} 3x_{n+1}-x_{n+1}^4&=x_n^4+1-\frac1{81}\left(x_n^4+1\right)^4\\ &\le x_n^4+1-\frac1{81}(3x_n)^4\\ &=1\;, \end{align*}

and therefore $x_{n+2}\ge x_{n+1}$. It follows by induction that $\langle x_n:n\in\Bbb Z^+\rangle$ is monotone non-decreasing.

-

Let $\{a_n\}$ be the sequence we obtain by starting at $0$, and $\{b_n\}$ be the sequence we obtain by starting at $1$.

Straightforward inductions show that the first sequence is increasing and bounded above by $1$, and the second is decreasing and bounded below. So each has a limit. Let the limits be $a$ and $b$.

We want to show that $a=b$. To do this, we show by induction that $0\lt b_n-a_n\le \left(\frac{1}{3}\right)^{n-1}$. We have $$b_{n+1}-a_{n+1}=\frac{1}{3}(b_n^4-a_n^4)=\frac{1}{3}(b_n-a_n)(b_n^3+b_n^2a_n+b_na_n^2+a_n^3).$$ Compute separately $a_2$, $a_3$, and $b_2$, $b_3$. For $n\ge 3$, we have $b_n \lt 0.4$, So $b_n^3+b_n^2a_n+b_na_n^2+a_n^3\lt 1$.

-