# Prove convergence and find limit of $a_{n+2}=\frac{1}{2}(a_n+a_{n+1})$

I need to prove the convergence and find the limit of the following recursive sequence:

$$a_1=2,a_2=5$$

$$a_{n+2}=\frac{1}{2}(a_n+a_{n+1})$$

*Similar problems were solved by showing the sequence is monothonic and limited.

• Not quite a duplicate of this question: the problem is the same, but the earlier question asked only for help proving that the limit is $4$, not for help with the entire problem. – Brian M. Scott Aug 28 '13 at 19:18

The characteristic polynomial is $$r^2-\frac{1}{2}r-\frac{1}{2}$$ and its roots are $$r_1=1\quad;\quad r_2=-\frac{1}{2}$$ so the sequence is $$a_n=\alpha r_1^n+\beta r_2^n$$ and $\alpha$ and $\beta$ are determined by $a_1$ and $a_2$ and the limit of $a_n$ is clearly $\alpha$.

• The characteristic polynomial is usually the best way to go. Thanks for reminding. (But r cannot be more than 1 of course) – imranfat Aug 28 '13 at 19:42
• You're welcome. – user63181 Aug 28 '13 at 19:43
• How do we find/know the characteristic polynomial? – NightRa Sep 3 '13 at 12:23
• If we have the recursive sequence: $$\alpha a_{n+2}+\beta a_{n+1}+\delta a_n=0$$ then the characteristic equation is $$\alpha r^2+\beta r+\delta=0$$ – user63181 Sep 3 '13 at 17:04

Sometimes it helps to look at the differences $b_n = a_n - a_{n-1}$, so that $$a_n = \sum_{k=2}^n b_n + a_1$$ In the current situation, your given condition says for $n \geq 3$ you have $$b_n = -{1 \over 2}b_{n-1}$$ Since $b_2 = 3$, for any $n \geq 2$ one has $$b_n = (-{1 \over 2})^{n-2}b_2$$ $$= 12(-{1 \over 2})^n$$ So $$a_n = \sum_{k=2}^n b_n + a_1$$ $$= 12\sum_{n = 2}^n (-{1 \over 2})^n + 2$$ The geometric series converges and the limit is $$12 \sum_{n = 2}^\infty (-{1 \over 2})^n + 2$$ $$= 12{{1 \over 4} \over {1 + {1 \over 2}}} + 2$$ $$=4$$

Related techniques: (I), (II). To prove the convergence, it is enough to prove that the sequence is a contraction, that is

A sequence is a contraction if $|a_{n+2}-a_{n+1}| \leq k\, |a_{n+1}-a_{n}|$, for some $0<k<1$.

$$a_{n+2}=\frac{1}{2}(a_n+a_{n+1}) \implies a_{n+2}-a_{n+1}=\frac{1}{2}(a_n+a_{n+1})-a_{n+1}$$

$$\implies a_{n+2}-a_{n+1}=\frac{1}{2}(a_n-a_{n+1}) \implies |a_{n+2}-a_{n+1}|=\frac{1}{2}|a_{n+1}-a_{n}|$$

$$\implies |a_{n+2}-a_{n+1}| < \frac{2}{3}|a_{n+1}-a_{n}|,$$

which proves that the sequence is a contraction and hence it converges. To Solve the recurrence relation, see here for a general technique.

One way to show that it converges is to prove what the author of this question proved:

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.

However, you’ll still have to find the limit and prove that it really is the limit, and it turns out that you can do that without first proving that the sequence converges: my answer to that question suggests a straightforward way of doing so, and there are other answers to explore as well.

Do you know Banach's Fixed Point Theorem?