Limit of a Recursive Sequence I'm having a really hard time finding the limit of a recursive sequence - 
$$ \begin{align*}
&a(1)=2,\\
&a(2)=5,\\
&a(n+2)=\frac12 \cdot \big(a(n)+a(n+1)\big).
\end{align*}$$
I proved that the sequence is made up from a monotonically increasing sequence and a monotonically decreasing sequence, and I proved that the limits of the difference of these sequences is zero, so by Cantor's Lemma the above sequence does converge. I manually found out that it converges to $4$, but I can't seem to find any way to prove it.
Any help would be much appreciated! 
Thank you.
 A: It never hurts to look at some data. Calculate the first few terms:
$$2,5,\frac72,\frac{17}4,\frac{31}8,\frac{65}{16},\frac{127}{32}$$
We can even fit the first two numbers into the apparent pattern:
$$\frac1{1/2},\frac51,\frac72,\frac{17}4,\frac{31}8,\frac{65}{16},\frac{127}{32}$$
The denominator of $a(n)$ appears to be $2^{n-2}$, and the numerators are alternately one less and one more than a power of $2$. Specifically, it appears that the numerator of $a(n)$ is $2^n-1$ when $n$ is odd and $2^n+1$ when $n$ is even or, more simply, $2^n+(-1)^n$. We conjecture, therefore, that
$$a(n)=\frac{2^n+(-1)^n}{2^{n-2}}\;.$$
Now prove this by induction on $n$, and observe that it’s now trivial to calculate the limit of the sequence.
A: We can write the general term as 
$$\tag1 a(n) = u+\left(-\frac12\right)^n\cdot v$$
(because $1$ and $-\frac12$ are the two solutions of $x^2=\frac12(x+1)$).
From $a(1)=2=u-\frac12 v$ and $a(2)=5=u+\frac14 v$, we find $u=v=4$.
From (1) it is clear that $$\lim_{n\to\infty} a(n)=u=4$$
A: First, given $\mathbf{a}_i=[a_i,a_{i+1}]^T$, you can express the sequence as $\mathbf{a}_{i+1}=M\mathbf{a}_i$. Find the infinite power of $M$ by diagonalizing it and raising the diagonal term to an infinite power. Then the limit is $M^\infty\mathbf{a}_0$.
A: giving a little elaboration to Hagen's answer: note that what we have here is a linear recurrence relation and assume a solution of the form $a(n)=x^n$. Observe:$$a(n+2)=\frac12(a(n)+a(n+1))\\x^{n+2}=\frac12(x^n+x^{n+1})\\x^{n+2}-\frac12x^{n+1}-\frac12x^n=0\\x^n\left(x^2-\frac12x-\frac12\right)=0$$... which yields the trivial solution $x=0$ but also the solutions $x=1,-1/2$, i.e. $a(n)=1$ and $a(n)=(-1/2)^n$ are two solutions to the above recurrence.
Because our problem is linear it follows any linear combination of $1,(-1/2)^n$ satisfies our equation, giving the general solution $a(n)=u+v(-1/2)^n$.
Imposing our initial conditions $a(1)=2,a(2)=5$ we determine our coefficients $u=v=4$ giving the solution $a(n)=4+4(-1/2)^n$. Clearly $a(n)\to4$ in the limit as $n\to\infty$.
