Show that a sequence satisfying $ x_{n+2} \leq \frac{1}{3} x_{n+1} + \frac{2}{3} x_{n} $ converges 
Suppose a $\{ x_n \}$ is a bounded sequence that satisfies
$$ x_{n+2} \leq \frac{1}{3} x_{n+1} + \frac{2}{3} x_{n} $$
for $n \geq 1$. Show that $\{ x_n \}$ ${\bf converges}$

attempt:
We can write $x_{n+2} - x_{n+1} \leq 2(x_n - x_{n+2} ) $.
Since $x_n$ is bounded then there is some $M$ so that $|x_n| \leq M $ for all $n$.
My goal is to prove monotonicty and we'll be done. I also recognize that the RHS of hte inequality is of them $t x_{n+1} + (1-t) x_n $ for $0 < t < 1$ so it is a convex combination of two succesive. I am trying to make the connection but I am not clear. Any hint how wecan use this to prove our goal?
 A: We define $z_n=\max(x_n, x_{n + 1})$.
It is clear that $z_n$ does not increase. Thus by boundedness, we know that the sequence $(z_n)_n$ converges. We denote by $z$ the limit.
For any $\epsilon > 0$, pick a sufficiently large $N$ such that $z \leq z_n \leq z + \epsilon$ for all $n \geq N$.
Now for any $n \geq N$, I claim that $x_{n + 1} \geq z - 2\epsilon$.
In fact, if $x_{n + 1} < z - 2\epsilon$, then we would have $$x_{n + 2} \leq \frac23x_n + \frac13 x_{n + 1} < \frac23 (z + \epsilon) + \frac13 (z - 2\epsilon) = z.$$ This implies that $z_{n + 1} = \max(x_{n + 1}, x_{n + 2}) < z$, a contradiction.
Hence we have $z - 2\epsilon \leq x_n \leq z + \epsilon$ for all $n \geq N + 1$. Since $\epsilon$ is arbitrary, we see that the limit of the sequence $(x_n)_n$ is $z$.
A: While WhatsUp's solution is very nice and elegant, there is another approach. 
We have
$$
x_{n+2}+\frac23x_{n+1}\leq x_{n+1}+\frac23 x_n. 
$$
So, $\{x_{n+1}+\frac23 x_n\}$ is a monotone and bounded sequence. 
This shows that 
$$
x_{n+1}+\frac23x_n\rightarrow a \ \mathrm{as} \ n\rightarrow\infty.
$$
Let $b_n=x_n-\frac35a$. Then we have
$$
b_{n+1}=-\frac23 b_n+\epsilon_n
$$
where $\epsilon_n\rightarrow 0$ as $n\rightarrow\infty$. 
It follows that
$$
b_{n+1}=\left(-\frac23\right)^{n+1}b_0 + \sum_{i=0}^n\left(-\frac23\right)^{n-i}\epsilon_i.
$$
As $\epsilon_n$ converges to $0$, the sequence $\{\epsilon_n\}$ is bounded. Therefore, the sequence $\{b_{n+1}\}$ converges. 
Necessarily, $\{x_n\}$ must converge. 
A: Assume equality. 
Consider the roots of $x^2 - \frac{1}{3} x -\frac{2}{3}$
the roots can be calculated to be $\frac{3}{2}$ and $-\frac{2}{3}$
If you let $x_0 = 1 $ and $x_1= \frac{3}{2}$ then we have:
$x_n = {\frac{3}{2}}^n$ which doesn't converge.
Reason if $r = \frac{3}{2}$ and $r^0 = x_0, r^1 = x_1$ then it should be clear by the equation:
$r^n - \frac{1}{3} r^{n-1} -\frac{2}{3}r^{n-2} = 0$ that inductively $x_n = r^n$.
So it is clear for some series convergence fails.
