# Compute the limit of a recursively defined sequence in terms of its initial values [duplicate]

This question already has an answer here:

Consider the sequence $\{ a_n \}$ defined recurisvely in terms of $a_1$ and $a_2$ by $$a_{n+1} = \frac{a_n + a_{n-1}}{2}$$ for $n \geq 2$. Assuming this sequence converges, find the limit in terms of $a_1$ and $a_2$.

The book provides the answer as $\frac{1}{3} a_1 + \frac{2}{3} a_2$, but I don't see how to arrive at this. Usually, for recursive sequences if we can assume the limit exists, then we say it is $L$ and then use the recursion to solve for $L$. I don't see how to accomplish that in this case.

## marked as duplicate by Alex M., user147263, choco_addicted, Daniel W. Farlow, ShaileshMar 22 '16 at 0:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

Jack D’Aurizio’s solution is nice and short, but the idea for it may seem to come out of thin air. Here’s another way to think about it that might occur to you fairly naturally if you recognize that by averaging at each step you’re moving halfway from $a_n$ to $a_{n-1}$ in order to reach $a_{n+1}$. Each step is half the size of the previous one, so the sequence should certainly converge, and the cumulative effect of the steps ought to be fairly easy to sort out.

To do this a bit more formally, let $d=a_2-a_1$, so that $a_1=a_2-d$. You start at $a_1$ and visit $a_2,a_3$, and so on in turn. Your first step is to add $d$ to reach $a_2$. Your second step takes you to

$$a_3=\frac{a_1+a_2}2=\frac{(a_2-d)+a_2}2=a_2-\frac{d}2\;.$$

Note that $a_2=a_3+\frac{d}2$. Thus, your third step takes you to

$$a_4=\frac{a_2+a_3}2=\frac{\left(a_3+\frac{d}2\right)+a_3}2=a_3+\frac{d}4\;.$$

Note that $a_3=a_4-\frac{d}4$. Thus, your fourth step takes you to

$$a_5=\frac{a_3+a_4}2=\frac{\left(a_4-\frac{d}4\right)+a_4}2=a_4-\frac{d}8\;.$$

In general it appears that the $n$-th step is of length $\dfrac{d}{2^n}$ but with an alternating sign:

$$a_{n+1}=a_n+(-1)^{n+1}\frac{d}{2^{n-1}}\;.$$

This is easily verified by induction, and the path is therefore

$$a_1+d-\frac{d}2+\frac{d}{2^2}-\frac{d}{2^3}+\ldots\;,$$

where the partial sum after $n$ terms is simply $a_n$. The limit of the sequence $\langle a_n:n\in\Bbb Z^+\rangle$ must then be

$$a_1+d\sum_{n\ge 0}\frac{(-1)^n}{2^n}=a_1+d\sum_{n\ge 0}\left(-\frac12\right)^n\;,$$

and you can easily evaluate the geometric series to express this in terms of $a_1$ and $a_2$.

You may easily check that $a_n+2 a_{n+1}$ does not really depend on $n$, since:

$$a_n+2 a_{n+1} = a_n + \left(a_n + a_{n-1}\right) = a_{n-1} + 2 a_n. \tag{1}$$ On the other hand, $$\left|a_{n+1}-a_n\right| = \frac{1}{2}\cdot\left|a_n-a_{n-1}\right|, \tag{2}$$ hence the sequence is convergent for sure.

By assuming $\lim_{n\to +\infty} a_n = L$ and exploiting $(1)$ we get: $$a_1 + 2a_2 = 3L\quad \Longrightarrow\quad L=\frac{a_1+2a_2}{3}.\tag{3}$$