Recurring sequences are generally involved in the modeling of discrete systems. In fact, such sequences replace the differential equation by discretizing the time variable.
To well understand the material of this page, properties of convergent sequences are needed.
Facts about recurring sequences
Definition: Let $I$ be an interval of $\mathbb{R}$ and $f$ a function on $I$ such that $f(I)\subset I$. A recurrent sequence is defined by \begin{align*} u_0\in I,\qquad u_{n+1}=f(u_n),\qquad \forall n.\end{align*}
Suppose the interval is bounded. This implies that the recurring sequence $ (u_n) _n $ is bounded. Now to show that $ (u_n) _n $ is convergent, it suffices to prove that this sequence is monotonic, increasing or decreasing. This depends on the regularity of $f$. For instance, if $f$ increases and if $u_1ge u_0,$ then the sequence $ (u_n) _n $ is increasing, hence convergent.
Worksheet
Exercise: Consider the recurrent sequence \begin{align*} u_0\in [0,+\infty),\quad u_{n+1}=\sqrt{u_n},\;\forall n\in\mathbb{N}. \end{align*} Discuss the convergence of $(u_n)_n$ and determine the limit.
Solution: If we define the square function $f(x)=\sqrt{x}$ for $x\ge 0$, we then have $u_{n+1}=f(u_n)$. As $f([0,+\infty))\subset [0,+\infty)$ and $u_0\ge 0$ then the others terms of the sequence are positive as well. Thus the sequence $(u_n)_n$ is well defined. On the other hand, the function $f$ is increasing. Then $(u_n)_n$ is monotone depending on the sign of $u_1-u_0,$ if $u_1\ge u_0$ the sequence is increases and if $u_1\le u_0$ the sequence is decreases. On the other hand, as $f$ is continuous then if the sequence converges to $\ell$ then it is the solution of the algebraic equation $f(\ell)=\ell$, so that $\ell=0$ or $\ell=1,$ we say that $\ell$ is a fixed point of $f$.
Observe that \begin{align*} u_0\le u_1 \;\Longleftrightarrow\; u_0\le \sqrt{u_0} \;\Longleftrightarrow\; u_0\in [0,1]. \end{align*} Hence the sequence $(u_n)_n$ is increasing if $u_0\in [0,1],$ and decreasing if $u_0\ge 1$. We also have $f([0,1])\subset [0,1]$ and $f([1,+\infty))\subset [1,+\infty)$. We distinguish three cases
If $u_0=0$. Then $u_n=0$ for any $n\in\mathbb{N}$, and thus the sequence converges to $0$.
If $u_0\in (0,1]$ then the sequence is increasing and $0 < u_n\le 1,$ because $f((0,1])\subset (0,1]$. Then converge to $\ell\in (0,1]$. This $\ell=1$.
If $u_0\ge 1,$ then the sequence is decreasing and $u_n\ge 1,$ because $f((0,1])\subset (0,1]$. Thus the sequence converges to $1$.
Exercise: Let $(u_n)_n$ the recurring sequence defined by \begin{align*} u_0=\frac{1}{2} ,\quad u_{n+1}=\frac{2u_n}{1+u_n},\;\forall n\in\mathbb{N}. \end{align*}
- Calculate $u_1,u_2,u_3$ and $u_4$.
- Let $(v_n)_n$ be the sequence defined by \begin{align*} v_{n}=1-\frac{1}{u_n},\quad \forall n\in\mathbb{N}. \end{align*}
- First, calculate $v_{n+1}$ in function of $u_n$. Deduce that $(v_n)_n$ is a geometric sequence. Second, calculate $v_n$ in function of $n$ and deduce the expression of $u_n$. Finally, calculate the limit of $u_n$ as $n\to+\infty$.
Solution: 1) We have \begin{align*} \begin{array}{cc} u_1=\frac{2u_0}{1+u_0}=\frac{2}{3}, & u_2=\frac{2u_1}{1+u_1}=\frac{4}{5} \\ u_3=\frac{2u_2}{1+u_2}=\frac{8}{9}, & u_4=\frac{2u_3}{1+u_3}=\frac{16}{17}. \end{array} \end{align*}
2) Let us determine the expressions of $v_n$ and $u_n$: For any $n\in\mathbb{N},$\begin{align*} v_{n+1}&=1-\frac{1}{u_{n+1}}=1-\frac{1}{\frac{2u_n}{1+u_n}}\cr &= \frac{2u_n-u_n-1}{2u_n}\cr &= \frac{1}{2} \frac{u_n-1}{u_n}= \frac{1}{2}\left(1-\frac{1}{u_n}\right)\cr &= \frac{1}{2} v_n. \end{align*} This $(v_n)$ is a geometric sequence of ratio $r=\frac{1}{2}$ and initial term $v_0=1-\frac{1}{u_0}=-1$.
As $(v_n)$ is a geometric sequence of ratio $r=\frac{1}{2}$ and initial term $v_0=-1$, then \begin{align*} v_n=v_0 r^n= – \left(\frac{1}{2}\right)^n. \end{align*} Moreover, the relation $v_n=1-\frac{1}{u_n}$ implies that \begin{align*} u_{u}=\frac{1}{1-v_n}=\frac{1}{1+\left(\frac{1}{2}\right)^n}. \end{align*}
As $\frac{1}{2}\in (0,1),$ then \begin{align*} \lim_{n\to +\infty} \left(\frac{1}{2}\right)^n=0. \end{align*}Thus \begin{align*} \lim_{n\to +\infty} u_n=1.\end{align*}
