# Proof of the limit of a recursive sequence

Problem:

Let $a_1=0$, $a_2 = 1$, $a_{n+2}$ = $\frac12$($a_n$ + $a_{n+1}$)$; n = 1,2,3,...$ Prove that $\lim_{n\to \infty}a_n = \frac23$

I did a couple of calculations to get a feel for the sequence's behaviour, it being:

{$0,1,\frac12,\frac34,\frac58,\frac{11}{16},\frac{21}{32},\frac{43}{64},...$}

All odd indices seem to be monotonically increasing and bounded from above, and the even indices are monotonically decreasing and bounded from below. I suspect that this may be the key to solving this problem, however, I'm not exactly sure to mathematically construct my argument or if this approach is a fool's errand.

I'm not necessarily asking for a full solution, but rather some feedback or perhaps a hint. Thanks for taking the time to consider my problem.

Write: $2\cdot a_{n+2} - a_{n+1} - a_n = 0$, and consider the characteristic equation:
$2x^2 - x - 1 = 0$ has $x = 1$ and $x = -\dfrac{1}{2}$ as real roots. So the general formula for $a_n$ is:
$a_n = A\cdot 1^n + B\cdot \left(\dfrac{-1}{2}\right)^n$. So $a_1 = 0 \to A - \dfrac{B}{2} = 0$, and $a_2 = 1 \to A + \dfrac{B}{4} = 1$. Solve this system we have: $A = \dfrac{2}{3}$. Thus taking limit we have: $a_n \to \dfrac{2}{3}$ as claimed.
Prove by induction on $n$ that $$a_n=\frac23+(-1)^n\frac43\frac1{2^n}.$$