<s>[INST] Show that $x_{n+2} = \frac{1}{3} x_{n + 1} + \frac{1}{6} x_n + 1$ is bounded, monotone, and find its limit Prove that $x_1 = 0, x_2 = 0, x_{n+2} = \frac{1}{3} x_{n + 1} + \frac{1}{6} x_n + 1$ is bounded and monotonic. Then find its limit.
My attempt at boundedness:
(Using induction) For the base case we have $0 \leq x_1 = 0 \leq 2$. Assume that the sequence is bounded for $n = k$. Then,
\begin{align*}
0 \leq x_k &\leq 2 \\
\vdots \\
\text{lower bound } \leq x_{k + 1} &\leq \text{upper bound}
\end{align*}
I am thrown off by the term $x_{n + 2}$ in the recursive formula and I can't see the algebra to produce the above steps without getting $x_{n + 2}$ in the expression of the upper / lower bound.
Thank you.
Update:
I have added this to the prove:
We have $0 \leq x_1 = 0 \leq 2$ and $0 \leq x_2 = 0 \leq 2$. Assume that the sequence is bounded for $k+1$,
\begin{align*}
0 &\leq x_{k + 1} \leq 2 \\
0 &\leq x_k + x_{k+1} \leq 4 \\
0 &\leq x_k + \frac{1}{3} x_{k+1} \leq 4 \\
0 &\leq \frac{1}{6} x_{k} + \frac{1}{3} x_{k+1} \leq 4 \\
0 &\leq x_{k+2} \leq 4 
\end{align*}
Therefore, by the principle of mathematical induction, the sequence is bounded.
Is this valid?
 [/INST] For boundedness we use Strong Induction, it is trivial that the sequence is positive.
We want to show that for all $n \in \mathbb{N}$ we have $x_{n} < 2$

*

*For k = 1 we have: $x_{1} = 0 < 2$

*Let $n \in \mathbb{N}$ and suppose that for all $k \leq n$ we have: $x_{k} < 2$

*We have:                  $x_{n-1} < 2$ and $x_{n} < 2$ 
Then: $\frac{1}{3}x_{n} + \frac{1}{6}x_{n-1} + 1 < \frac{2}{3} + \frac{2}{6} + 1$ 
Hence: $x_{n+1} < 2$
For monotony, Let use again induction to prove that for all $n \in \mathbb{N}$, $x_{n+1} \geq x_{n}$

*

*For n = 1, it is clearly that $x_{2} = 0 \geq x_{1}$ since $x_{1} = 0$

*Let $n \geq 2$ and suppose that for all $k \leq n$ we have: $x_{k+1} \geq x_{k}$ 
We have: $x_{n} \geq x_{n-1}$ and $x_{n+1} \geq x_{n}$ 
Hence: $\frac{1}{3}x_{n+1} + \frac{1}{6}x_{n} + 1 \geq \frac{1}{3}x_{n} + \frac{1}{6}x_{n-1} + 1$ 
Thus: $x_{n+2} \geq x_{n+1}$ 
We conclude that the sequence is increasing and thus it is monotone, And since it is bounded then the sequence converge.
Let $L$ be the limit of the sequence, then $L$ is solution to the equation $x = \frac{1}{3}x + \frac{1}{6}x + 1$, which gives that $L = 2$
</s>