Convergence and limits of recusive sequences.

Question

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..

Answer 1

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.

Answer 2

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). $$