Define $x_{2n}=\frac{x_{2n-1}+2x_{2x-2}}{3}\,\,\,\,\,,x_{2n+1}=\frac{2x_{2n}+x_{2n-1}}{3}$ for $n \in \mathbb{N^+}$. Let $x_0=a$ and $x_1=b$ with $b>a$. Define $$x_{2n}=\frac{x_{2n-1}+2x_{2n-2}}{3}\,\,\,\,\,,x_{2n+1}=\frac{2x_{2n}+x_{2n-1}}{3}$$ for $n \in \mathbb{N^+}$. Show that the sequence $(x_n)$ converges. my attempt is to prove that $(x_{2n})$ is increasing and $(x_{2n+1})$ is decreasing. But I don know how to prove it. Anyone can help ?
 A: Let $a_n=x_{2n},b_n=x_{2n+1}$. Now it follows that:
$$a_n=\frac{1}{3}b_{n-1}+\frac{2}{3}a_{n-1}...(1)$$
$$b_n=\frac{2}{3}a_{n}+\frac{1}{3}b_{n-1}....(2)$$
From (1) we get: $b_{n-1}=3a_n-2a_{n-1}$. Substitute in reccurence (2) to get:
$$(3a_{n+1}-2a_n)=\frac{2}{3}a_n+\frac{1}{3}(3 a_{n}-2a_{n-1})$$
Solve this reccurence relation to get $a_n$ (which will let you find $b_n$). Using a closed form of $a_n,b_n$ its easy to check if they converge.

If they converge:
Let $\lim_{n\rightarrow\infty}a_n=A, \lim_{n\rightarrow\infty}b_n=B$
one can show that they converge to the same limit because the recurrence relations lead to:
$$A=\frac{1}{3}B+\frac{2}{3}A$$
This leads to $A=B$, hence $x_n$ converges.
A: Show by induction that $x_{2n}<x_{2n+2}<x_{2n+3}<x_{2n+1}$.
To do so, note that each element of the sequence is a convex combination of its two predecessors.
A: Very often the reason why we are getting stuck in induction proof, is that we try to prove something a little bit to weak to rely on later during induction step. Let's show that:


*

*Even terms form increasing subsequence.

*Odd terms form decreasing subsequence.

*Odd terms are greater than even terms.


For $x_0$ and $x_1$ it's ok. Assume that these conditions are satisfied for terms up to $x_{2n-1}$. We have that $x_{2n}=\frac{x_{2n-1}+2x_{2n-2}}3$. By induction hypothesis $x_{2n-1} > x_{2n-2}$, thus $x_{2n-1}>x_{2n}>x_{2n-2}$, and then after repeating it for $x_{2n+1}$ we conclude that $$x_{2n-1}>x_{2n+1}>x_{2n}>x_{2n-2}$$ Which implies all three conditions for terms up to $x_{2n+1}$. So both of these subsequences converge, and by Amr argument - to the same limit.
A: Closed forms for linear recurrence relations can be found using matrices and diagonalization.
Let $v_i = \begin{bmatrix}x_i & x_{i - 1}\end{bmatrix}^\intercal$. We have $v_1 = \begin{bmatrix}b & a\end{bmatrix}^\intercal$ and for any positive integer $n$,
$$\begin{align}
v_{2n} &= \begin{bmatrix}1/3 & 2/3\\1 & 0\end{bmatrix}v_{2n - 1}\\
v_{2n + 1} &= \begin{bmatrix}2/3 & 1/3\\1 & 0\end{bmatrix}v_{2n}\\
\end{align}$$
It is interesting to note that both matrices are right-stochastic (rows sum to 1).
Let $M = \begin{bmatrix}2/3 & 1/3\\1 & 0\end{bmatrix}\begin{bmatrix}1/3 & 2/3\\1 & 0\end{bmatrix} = \begin{bmatrix}5/9 & 4/9\\1/3 & 2/3\end{bmatrix}$;
$$\begin{align}
v_{2n} &= \begin{bmatrix}1/3 & 2/3\\1 & 0\end{bmatrix}M^{n - 1}\begin{bmatrix}b\\a\end{bmatrix}\\
v_{2n + 1} &= M^n\begin{bmatrix}b\\a\end{bmatrix}\\
\end{align}$$
We may diagonalize $M = \begin{bmatrix}-4/3 & 1\\1 & 1\end{bmatrix}\begin{bmatrix}2/9 & 0\\0 & 1\end{bmatrix}\begin{bmatrix}-4/3 & 1\\1 & 1\end{bmatrix}^{-1}$
Substitute $u_i = \begin{bmatrix}-4/3 & 1\\1 & 1\end{bmatrix}^{-1}v_i$ to get
$$\begin{align}
u_{2n + 1} &= \begin{bmatrix}(2/9)^n & 0\\0 & 1\end{bmatrix}u_1 = \frac{1}{7}\begin{bmatrix}3(2/9)^n(a - b)\\4a - 3b\end{bmatrix}\\
\implies \begin{bmatrix}x_{2n + 1}\\x_{2n}\end{bmatrix} = v_{2n + 1} &= \begin{bmatrix}-4/3 & 1\\1 & 1\end{bmatrix}\begin{bmatrix}3(2/9)^n(a - b)\\4a - 3b\end{bmatrix}
\end{align}$$
This should answer your questions.
