Here is Prob. 11, Sec. 3.5, in the book Introduction to Real Analysis by Robert G. Bartle and Donald R. Sherbert, 4th edition:
If $y_1 < y_2$ are arbitrary real numbers and $y_n \colon= \frac{1}{3}y_{n-1} + \frac{2}{3} y_{n-2} $ for $n > 2$, show that $\left( y_n \right)$ is convergent. What is its limit?
My Attempt:
As $y_1 < y_2$, so $$ y_1 < \frac{ y_2 + 2 y_1 }{3} < y_2,$$ that is, $$ y_1 < y_3 < y_2; \tag{1*} $$ also $$ \left\lvert y_3 - y_2 \right\rvert = y_2 - y_3 = \frac{ 2 \left( y_2 - y_1 \right) }{3}. \tag{1} $$
As $y_3 < y_2$, so $$ y_3 < \frac{ y_3 + 2 y_2 }{3} < y_2,$$ that is, $$ y_3 < y_4 < y_2; \tag{2*} $$ also $$ \left\lvert y_4 - y_3 \right\rvert = y_4 - y_3 = \frac{2 \left( y_2 - y_3 \right) }{3} = \frac{ 2^2 \left( y_2 - y_1 \right) }{3^2}. \tag{2} $$
As $y_3 < y_4$, so $$ y_3 < \frac{ 2y_3 + y_4 }{3} < y_4, $$ that is, $$ y_3 < y_5 < y_4; \tag{3*} $$ also $$ \left\lvert y_5 - y_4 \right\rvert = y_4 - y_5 = \frac{ 2 \left( y_4 - y_3 \right) }{3} = \frac{ 2^3 \left( y_2 - y_1 \right) }{3^3}. \tag{3} $$
As $y_5 < y_4$, so $$ y_5 < \frac{ y_5 + 2 y_4}{3} < y_4, $$ that is, $$ y_5 < y_6 < y_4; \tag{4*} $$ also $$ \left\lvert y_6 - y_5 \right\rvert = y_6 - y_5 = \frac{ 2 \left( y_4 - y_5 \right) }{3} = \frac{ 2^4 \left( y_2 - y_1 \right) }{3^4}. \tag{4} $$
From (1*), (2*), (3*), and (4*), we get $$ y_1 < y_3 < y_5 < y_6 < y_4 < y_2. \tag{A} $$
Suppose, for some $k \in \mathbb{N}$, that $$ y_1 < y_3 < y_5 < \cdots < y_{2k-1} < y_{2k} < \cdots < y_6 < y_4 < y_2. \tag{B*} $$ and $$ \left\lvert y_{2k} - y_{2k-1} \right\rvert = \frac{ 2^{2k-2} \left( y_2 - y_1 \right) }{3^{2k-2}}. \tag{B} $$
As $y_{2k-1} < y_{2k}$, so $$ y_{2k-1} < \frac{ 2y_{2k-1} + y_{2k} }{3} < y_{2k}, $$ that is, $$ y_{2k-1} < y_{2k+1} < y_{2k}; \tag{5*} $$ also, $$ \left\lvert y_{2k+1} - y_{2k} \right\rvert = y_{2k} - y_{2k+1} = \frac{ 2 \left( y_{2k} - y_{2k-1} \right) }{3} = \frac{ 2^{2k-1} \left( y_2 - y_1 \right) }{3^{2k-1}}. \tag{5} $$
As $y_{2k+1} < y_{2k}$, so $$ y_{2k+1} < \frac{ y_{2k+1} + 2 y_{2k} }{3} < y_{2k},$$ that is, $$ y_{2k+1} < y_{2k+2} < y_{2k}; \tag{6*} $$ also $$ \left\lvert y_{2k+2} - y_{2k+1} \right\rvert = y_{2k+2} - y_{2k+1} = \frac{ 2 \left( y_{2k} - y_{2k+1} \right) }{3} = \frac{ 2^{2k} \left( y_2 - y_1 \right) }{ 3^{2k} }. \tag{6} $$
From (B*), (5*), and (6*), we can conclude that $$ y_1 < y_3 < y_5 < \cdots < y_{2k-1} < y_{2k+1} < y_{2k+2} < y_{2k} < \cdots < y_6 < y_4 < y_2 \tag{C*} $$ for all $k \in \mathbb{N}$.
And, from (B), (5), and (6), we get $$ \left\lvert y_{n+1} - y_n \right\rvert = \frac{2^{n-1} \left( y_2 - y_1 \right) }{3^{n-1}}. \tag{C} $$ for all $n \in \mathbb{N}$.
So for any natural numbers $m$ and $n$ such that $m > n$, we have $$ \begin{align} \left\lvert y_n - y_m \right\rvert &\leq \left\lvert y_n - y_{n+1} \right\rvert + \cdots + \left\lvert y_{m-1} - y_m \right\rvert \\ &= \left[ \left( \frac{2}{3} \right)^{n-1} + \cdots + \left( \frac{2}{3} \right)^{m-2} \right] \left( y_2 - y_1 \right) \\ &= \left( \frac{2}{3} \right)^{n-1} \left[ 1 + \frac{2}{3} + \cdots + \left( \frac{2}{3} \right)^{m-n-1} \right] \left( y_2 - y_1 \right) \\ &= \left( \frac{2}{3} \right)^{n-1} \frac{ 1 - \left( \frac{2}{3} \right)^{m-n} }{ 1 - \frac{2}{3} }\left( y_2 - y_1 \right) \\ &< 3 \left( \frac{2}{3} \right)^{n-1} \left( y_2 - y_1 \right). \end{align} $$
As $\left(2/3\right)^{n-1} \to 0$ as $n \to \infty$, so it follows that $\left( y_n \right)_{n \in \mathbb{N}}$ is a Cauchy sequence of real numbers and therefore converges to some real number $y$.
Now $$ y_3 = \frac{ y_2 + 2 y_1 }{3}, $$ and so $$ y_4 = \frac{ y_3 + 2 y_2 }{3} = \frac{ \frac{ y_2 + 2 y_1 }{3} + 2 y_2 }{3} = \frac{ 7 y_2 + 2 y_1 }{3^2}, $$ and hence $$ y_5 = \frac{ y_4 + 2y_3 }{3} = \frac{ \frac{ 7 y_2 + 2 y_1 }{3^2} + 2 \frac{ y_2 + 2 y_1 }{3} }{3} = \frac{ 13 y_2 + 14 y_1 }{3^3}, $$ which gives $$ y_6 = \frac{ y_5 + 2 y_4 }{3} = \frac{ \frac{ 13 y_2 + 14 y_1 }{3^3} + 2 \frac{ 7 y_2 + 2 y_1 }{3^2} }{3} = \frac{55 y_2 + 26 y_1 }{3^4}, $$ and thence $$ y_7 = \frac{ y_6 + 2y_5 }{3} = \frac{ \frac{55 y_2 + 26 y_1 }{3^4} + 2 \frac{ 13 y_2 + 14 y_1 }{3^3} }{3} = \frac{ 133 y_2 + 110 y_1 }{3^5}, $$ and $$ y_8 = \frac{ y_7 + 2 y_6 }{3} = \frac{ \frac{ 133 y_2 + 110 y_1 }{3^5} + 2 \frac{55 y_2 + 26 y_1 }{3^4} }{3} = \frac{ 463 y_2 + 266 y_1 }{3^6}. $$
Is what I've done so far correct? If so, then how to proceed from this point? How to find the general formula for $y_n$, or for that matter $y_{2k+1}$ and $y_{2k}$ for $k \geq 2$?
Your proof about the convergence is correct, but I think that you can show it in a much shorter way (and find the limit too!!).
The homogeneous linear recurrence with constant coefficients $$y_n \colon= \frac{1}{3}y_{n-1} + \frac{2}{3} y_{n-2}$$ has an explicit solution of the form $$y_n=A+B\cdot (-2/3)^n.$$ You can verify easily that this formula satisfies the given recurrence. See also above link to see how this kind of recurrences can be solved. Therefore $y_n$ converges to $A$.
Note that the constants $A$ and $B$ depend on $y_1$ and $y_2$: $$\begin{cases}A-\frac{2B}{3}=y_1\\A+\frac{4B}{9}=y_2 \end{cases}\implies \begin{cases} A= \frac{2y_1+3y_2}{5}\\ B=\frac{9(y_2-y_1)}{10} \end{cases}$$ Therefore $$\lim_{n\to \infty}y_n=A=\frac{2y_1+3y_2}{5}\in (y_1,y_2).$$