Convergence and limits of recusive sequences. I want to ask a question about recursive sequences. They have been pretty easy to handle for me, if you have one variable in it. To give you an example, if you have a sequence like:
$x_o = 1, x_{n+1}=\frac{a+x_n}{1+x_n}, n \in \mathbb{N},( 0<a<1 )$. 
You can proove convergence easily by induction and calculate the limit x by solving $ x =\frac{a+x}{1+x}$, $x = \sqrt{a}$. Not too hard so far, but no i am facing one with 2 variables:
$$a_o = a , a_1 = b, a_{n} = \frac{1}{2}(a_{n-1}+a_{n-2}), $$$$a,b \in \mathbb{R}, n ≥ 2, n\in\mathbb{N}$$
My thoughts:
Series looks somehow like this.
$a, b, \frac{a+b}{2} (:=c), \frac{c+b}{2} (:=d),\frac{c+d}{2} (:=e)...$
So the limit must be something like:
$\frac{b+a}{2}=b \rightarrow b = a $ ??? Of course, if the terms of the sum in the numerator are the same, the series will stay the same for every n+1th item. But will this be its limit? 
As you see i am a bit unsure here, if you have an idea can you leave a quick post here on how to prove convergence, and how to calculate the limit ? Thanks for all input..
 A: You don’t need the general techniques in order to deal with this problem. Note that each term is simply the average of the two preceding terms. Thus, $a_2$ is the midpoint of the segment between $a$ and $b$; $a_3$ is the midpoint of the segment between $a_2$ and $b$, and so on. This is a relationship that shouldn’t be changed if we shift and scale the sequence into a more convenient location, so let’s try that.
Let $b_n=a_n-a$. Then the recurrence $a_n=\frac12(a_{n-1}+a_{n-2})$ can be rewritten
$$b_n+a=\frac12\Big((b_{n-1}+a)+(b_{n-2}+a)\Big)=\frac12(b_{n-1}+b_{n-2})+a\;,$$
and therefore $b_n=\frac12(b_{n-1}+b_{n-2})$; the shifted sequence satisfies the same recurrence as the original. Then let $c_n=\frac{b_n}{b-a}$ and do the same thing:
$$(b-a)c_n=\frac12\Big((b-a)c_{n-1}+(b-a)c_{n-2}\Big)=\frac12(b-a)(c_{n-1}+c_{n-2})\;,$$
so $c_n=\frac12(c_{n-1}+c_{n-2})$. 
Now $c_0=0$ and $c_1=1$. Calculate the first few values of $c_n$: if you go as far as $c_6$ or so, you should be able to spot the pattern and be able to write $c_n$ as a function of $n$. (If you get stuck, leave a comment.) You may alternatively recognize that the $c_n$’s are partial sums of a simple series, whose sum you can easily find. This will give you convergence and limit of the $c_n$’s, hence of the $a_n$’s, which are just a scaled and shifted version of the $c_n$’s.
A: To solve this with generating functions, let $f(x)=\sum_{n=0}^\infty a_n x^n$. Multiply each side of the recurrence by $x^n$ and sum over all values of $n$ for which it is valid (i.e. $n\geqslant 2$). On the left-hand side we get
$$\sum_{n=2}^\infty a_nx^n = \sum_{n=0}^\infty a_n x^n - (a_0 + a_1x) = f(x) - a - bx. $$
On the right-hand side we get
$$\sum_{n=2}^\infty\frac12 a_{n-1}x^n +\sum_{n=2}^\infty a_{n-2}x^n. $$
After manipulating the indices we get that this is equal to
$$\frac12 x(f(x)-a) + \frac12 x^2f(x). $$
Therefore
$$ f(x) - a - bx = \frac12 x(f(x)-a) + \frac12 x^2f(x)$$
and
$$f(x) = \frac{a + \left(b-\frac a2\right)x}{1 - \frac12 x - \frac12 x^2}=\frac{2a + (2b-a)x}{(1-x)(2+x)}. $$
After partial fraction decomposition and some simplification, this becomes
$$\frac13(a+2b)\frac1{1-x} +\frac23(a-b)\frac1{1-\left(-\frac12 x\right)}. $$
Now, using the power series representation $\frac1 {1-z} = \sum_{n=0}^\infty z^n$, we get
$$ f(x) = \frac13(a + 2b)\sum_{n=0}^\infty x^n + \frac23(a-b)\sum_{n=0}^\infty\left(-\frac12 x\right)^n,$$
and this simplifies to
$$f(x) = \sum_{n=0}^\infty \left[ \frac13(a+2b) + \frac23(a-b)\left(-\frac12\right)^n\right]x^n. $$
Hence
$$ a_n = \frac13(a+2b) + \frac23(a-b)\left(-\frac12\right)^n, n\geqslant 0.$$
From this is it evident that
$$ \lim_{n\to\infty} a_n = \frac13(a+2b). $$
