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?

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$
