Convergence of the sequence $a_{{n+1}} = (1/3)(1+a_n+(a_{n-1})^2)$ Prove that $a_n$ converges:
$a_1 = 0$ , $a_2 = 1/2$, $a_{{n+1}} = (1/3)(1+a_n+(a_{n-1})^2)$ 

My game plan is to prove that this sequence is monotonic rising and then bounded to prove convergence, but I can't even prove that its monotonic rising. 
(My question is relating to first proving that the sequence is monotonic so please don't give me the answer for the rest of the proof I want to still try it myself)
I'm trying to prove this by induction. 
I've found the first few $n$'s : $(n_1 = 0,n_2 =  1/2,n_3= 1/2,n_4= 7/12)$ so it looks like this is indeed rising. 
I've decided to assume that for $n=k$, $a_{{k+1}}>a_{{k}}$ and to show that it's rising for all $k$'s and therefore all $n$'s. 
Not sure what to do now. I've searched online and on youtube for examples on proving convergence for recursive sequences but only found very trivial examples of induction (a method I admittedly don't completely understand)
again, don't post how to prove the convergence I want to try to figure this out still. 
Thanks, 
nofe
 A: Hint: Write down the recurrence you were given, and the recurrence for $a_{n+2}$, and look.
Added:
We were told that for all $n$,
(i) $a_{n+1}=\frac{1}{3}(1+a_n+a_{n-1}^2)$.
From this it follows immediately that
(ii) $a_{n+2}=\frac{1}{3}(1+a_{n+1}+a_n^2)$.
Suppose that we already know that $a_{k+1} >a_k$ for all $k \le n$. (Actually, we only need it for $k=n$ and $k=n-1$.) We want to show that $a_{n+2}>a_{n+1}$.
Compare the two expressions term by term, forgetting about the $\frac{1}{3}$, because it is common, so makes no difference in determining who is bigger.
First terms are $1$, equal. Second term is $a_{n+1}$ in (ii) and $a_n$ in (i), and we already know that $a_{n+1}>a_n$.  Third term is $a_n^2$ in (ii) and $a_{n-1}^2$ in (i). We already know that $a_n>a_{n-1}$. All our numbers are obviously non-negative, so $a_n^2>a_{n-1}^2$. 
Conclusion: $a_{n+2}>a_{n+1}$.
We have given a pretty full outline of a formal induction proof. But at the informal level, it is instant, first terms equal, second terms we went up, third terms we went up. So it's up.  And up. Forever.
Somewhat more formally, we know $a_1$ and $a_2$. Compute $a_3$. Observe that $a_2>a_1$ and $a_3>a_2$. this gives the base of the induction.
By what we did above, because $a_2>a_1$ and $a_3>a_2$, we have $a_4>a_3$.  But now because $a_3>a_2$ and $a_4>a_3$, we have $a_5>a_4$. But now because $a_4>a_3$ and $a_5>a_4$, we have $a_6>a_5$. And so on. Forever.
Remark: One can write down a fully persuasive argument that ostensibly doesn't use induction. However, induction is in principle unavoidable. Roughly speaking, whenever one sees $\dots$ in anything but a finite sequence, induction is n principle needed. And to prove anything general about a sequence defined by a recurrence, induction is in principle needed.
A: Hint:


*

*Prove by induction that $0\le a_n<1$ for all $n\ge1$.

*Using $a_n-a_{n-1}=\frac13(a_{n-1}-a_{n-2}+a_{n-2}^2-a_{n-3}^2)$, prove by induction that $a_{n+1}\ge a_n$ for all $n\ge1$.


What do you know about bounded increasing sequences in $\mathbb{R}$?
A: You can show that the sequence in monotonically increasing by using a somewhat stronger form of the induction principle.  Here, you need to show: 
$\ \ \ \ 1)\ a_1\le a_2$
and
$\ \ \ \ 2)\ $If $a_{m-1}\le a_{m }$ for all $2\lt m\le n$, then $a_{n }\le a_{n+1}$.
Note that in 2), you assume that the inequality is true for all terms of the sequence, up to the $(n-1)^{\rm st}$-term. Then, you must show that the inequality must be true for the $n^{\rm th}$ term. Once you show this can be done, and once you show 1) is true, it will follow that the  inequality is true for all $n$.
So:
Condition 1) is satisfied: $a_1=0<{1\over2}=a_2$.
Now, fix a value of $n\gt 2$, and  assume that 
$$a_{m-1}\le a_{m},\quad \text{ whenever }2\lt  m\le n .$$  We need to show that $a_n\le a_{n+1}$.
Towards this end, we have:
$$
a_n={1\over3}(1+a_{n-1}+(a_{n-2})^2 );
$$
and since we assumed $a_{n-1} \le a_n $ and $a_{n-2} \le a_{n-1}$, we have, noting that all the $a_j$ are nonnegative (which may require a separate proof), that
$$\eqalign{
a_n&={1\over3}(1+a_{n-1}+(a_{n-2})^2 )\cr
&\le{1\over3}(1+a_{n }+(a_{n-1})^2 )\cr
&=a_{n+1},

}
$$
as desired.
We have shown that 1) and 2) are satisfied; thus the sequence is monotone increasing.
A: The easiest way to prove an inequality like this is to simplify it as much as possible, collect all the terms to one side and see if something falls out (sometimes with a condition on your $a_n$.)  In this case, to show that $a_{n+1}\gt a_n$, multiply both sides by three, express in terms of $a_n$ and start collecting terms: $a_{n+1} \gt a_n$; $3a_{n+1} \gt 3a_n$; $1+a_n+a_n^2 \gt 3a_n$; $1-2a_n+a_n^2 \gt 0$.  Now, can you see why the last result is always zero or positive (and under what circumstances it's zero)?  Hint: what's a good condition on an expression that assures you it's always greater than or equal to zero?
