# Showing that a recurrently defined sequence is convergent.

This is a text book question.

Show that the sequence $$\{u_n\}$$ is convergent where $$0 and $$u_{n+2}=\frac{2u_{n+1}+u_n}{3}$$.

I am aware that it's possible to find the formula of this sequence using the roots of the characteristic equation $$x^2=\frac{2x+1}{3}$$ and following that apply limit $$n\to\infty$$. I found that $$\lim\limits_{n\to \infty} u_n=\frac{u_1+3u_2}{4}$$.

However, I want to show the existence of this limit analytically. Here's my attempt.

Given that $$0, these results follow.

$$u_3=\frac{2u_2+u_1}{3}\implies u_1

$$u_4=\frac{2u_3+u_2}{3}\implies u_3

$$u_5=\frac{2u_4+u_3}{3}\implies u_3

The idea is that, for a given list of numbers (not all equal) $$a_1, a_2, \cdots , a_n$$, the arithmetic mean i.e., $$\overline a=\frac{1}{n}\sum a_i$$ lies somewhere between $$\min(a_i)$$ and $$\max(a_i)$$.

$$\therefore 0u_4>u_6>\cdots>u_{2n}>\cdots>u_1\tag*{}$$

Conclusion:

• The odd subsequence of $$u$$ is monotone increasing and it is bounded above by $$u_2$$.
• The even subsequence of $$u$$ is monotone decreasing and it is bounded below by $$u_1$$.
• By monotone convergence theorem, both these subsequences are convergent.

At this point, I think it's sufficient to show that these two subsequences converge to the same limit. I am not sure how to do this.

Initially, I tried to do this proof with the Cauchy criterion for convergence, but I couldn't work it out. I would be interested to see anyone accomplishing it.

• Use that $u_{n+2}-u_{n+1}=(u_n-u_{n+1})/3$
– NDB
Jul 24, 2023 at 23:48
• OK, so say the odd subsequence has limit $L_o$ and the even subsequence has limit $L_e$. Then from $u_{n+2} = \frac{2 u_{n+1} + u_n}{3}$, if you restrict to even $n$ and take the limit as $n \to \infty$, you get... Jul 24, 2023 at 23:50
• @DanielSchepler Oh, yes, that makes sense! I didn't think about this simple substitution and was trying to figure out sups and infs of these subsequences in my mind and got confused. We get $L_e = \frac{2L_o+L_e}{3}\tag*{}$ I think, we are through. $\blacksquare$ Jul 24, 2023 at 23:55
• note that there are constants $A,B$ such that $u_n = A+ B \left( \frac{-1}{3} \right)^n$ Jul 25, 2023 at 1:08

THe sequence defined in the OP can be considered as a linear dynamical system on $$\mathbb{R}^2$$ as follows: $$\begin{pmatrix} x_{n+2}\\ x_{n+1}\end{pmatrix} =\begin{pmatrix} \frac23 & \frac13\\ 1 & 0 \end{pmatrix}\begin{pmatrix} x_{n+1}\\ x_n\end{pmatrix}=\begin{pmatrix} \frac23 & \frac13\\ 1 & 0 \end{pmatrix}^{n+1}\begin{pmatrix} x_1\\ x_0\end{pmatrix}$$

The matrix $$A=\begin{pmatrix} \frac23 & \frac13\\ 1 & 0 \end{pmatrix}$$ has eigenvalues $$\lambda_1=-\frac13$$, $$\lambda_2=1$$. It follows that $$A=\begin{pmatrix} \frac23 & \frac13\\ 1 & 0 \end{pmatrix}= \begin{pmatrix} 1 & 1\\ -3 & 1 \end{pmatrix}\begin{pmatrix} -\frac13 & 0\\ 0 & 1 \end{pmatrix}\frac14\begin{pmatrix} 1 & -1\\ 3 & 1 \end{pmatrix}$$

Consequently \begin{align} A^n&= \begin{pmatrix} 1 & 1\\ -3 & 1 \end{pmatrix}\begin{pmatrix} \big(-\frac13\big)^n & 0\\ 0 & 1 \end{pmatrix}\frac14\begin{pmatrix} 1 & -1\\ 3 & 1 \end{pmatrix}\\&\xrightarrow{n\rightarrow\infty}\begin{pmatrix} 1 & 1\\ -3 & 1 \end{pmatrix}\begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}\frac14\begin{pmatrix} 1 & -1\\ 3 & 1 \end{pmatrix}=\frac14\begin{pmatrix} 3 & 1\\ 3 & 1\end{pmatrix} \end{align}

Thus, the sequence $$\mathbf{x}_n=[x_{n+1},x_n]^\intercal$$ converges to $$\frac14\begin{pmatrix} 3 & 1\\ 3 & 1\end{pmatrix}\begin{pmatrix} x_1\\ x_0\end{pmatrix}=\begin{pmatrix} \frac{3x_1+x_0}{4} \\ \frac{3x_1+x_0}{4} \end{pmatrix}$$

I had asked this question on my Quora space as well and got response from Lai there. Link to his answer. I'm sharing his proof which reveals some ingenious insights to this sequence.

The key insight from his algebraic manipulation is that absolute difference between successive terms is being reduced to one-third every time as we move along the sequence! So we can intuitively think that eventually the terms will become arbitrarily close.

I am going to prove $$\{u_n\}$$ is convergent by Cauchy Criterion. First of all, we make use of the relation. For convenience, let $$\Delta=u_2-u_1>0$$. \begin{aligned}& u_{n+2}= \frac{2 u_{n+1}+u_n}{3} \\\Leftrightarrow \quad &3 u_{n+2}=2 u_{n+1}+u_n \\ \Leftrightarrow \quad & 3\left(u_{n+2}-u_{n+1}\right)=(-1)\left(u_{n+1}-u_n\right) \\\Leftrightarrow \quad & u_{n+2}-u_{n+1}=-\frac{1}{3}\left(u_{n+1}-u_n\right)= \cdots &=\left(-\frac{1}{3}\right)^n \Delta\cdots (*) \end{aligned}\tag*{} Use the formula (*) repeatedly, we get $$\displaystyle u_{n+1}-u_n=\left(-\frac{1}{3}\right)^{n-1}\Delta\tag*{}$$ For any positive integers $$p>q$$, we have $$\displaystyle |u_p-u_q|=\left|\sum_{k=q}^{p-1}\left(u_{k+1}-u_k\right)\right|=\left|\sum_{k=q}^{p-1}\left(-\frac{1}{3}\right)^{k-1}\Delta \right|<\Delta \sum_{k=q}^{p-1}\left(\frac{1}{3}\right)^{k-1}=\frac{9 \Delta}{2}\left(3^{-q}-3^{-p}\right)<\frac{9\Delta}{2\cdot 3^q} \rightarrow 0 \textrm{ as }q\rightarrow \infty \tag*{}$$ By Cauchy Criterion for convergence of a sequence, $$\{u_n\}$$ is convergent. With epsilon- delta notation, we can say that for any $$\epsilon >0$$, take $$\displaystyle N =\left[\log _3\left(\frac{9 \Delta}{2 \varepsilon}\right)\right]+1\tag*{}$$ such that for any natural number $$p>q>N$$, then $$\displaystyle |u_p-u_q|<\epsilon \tag*{}$$

• IT is simpler to use basic linear algebra to get the growth and decay components of the sequence. After all, this is a linear system. The $-1/3$ term corresponds to an eigenvalue of a matrix $A$ that defines the iterative dependance $\mathbf{x}_{n+1}=A\mathbf{x}_n$. your sequence coverges tp $\frac{3u_1+u_0}{4}$. Jul 26, 2023 at 15:11
• @Mittens you are right but the original post is intended to be a homework question for an analysis course. University students are expected to rely only on the theorems in a typical analysis syllabus (like Cauchy criterion, monotone convergence, etc.) to accomplish the proof. Jul 26, 2023 at 15:49
• Linear algebra, or even matrix algebra is usually studied before analysis (multivariate calculus for example) so this 2x2 metric methods are well known by then. At least in the place I teach. Jul 26, 2023 at 15:52
• @Mittens I guess it depends on the country and the varsity too. In my uni, they teach calc 1, group theory 1 and real analysis 1 in the fresh year. :) Jul 26, 2023 at 15:56