How can I find the limit of the following recursive formula?

$a, b \in \mathbb{R}$

$a_0=a; a_1=b; a_n= \frac{1}{2}(a_{n-1}+a_{n-2})$

$\lim\limits_{n \rightarrow \infty}{a_n} = ?$

Many thanks in advance.


closed as off-topic by Did, Shailesh, heropup, iadvd, Claude Leibovici Sep 16 '16 at 10:10

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, Shailesh, heropup, iadvd, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.


Think what happens if $a=0$, $b=1$. You can draw a line and see what happens, by drawing the points of the sequence $$0,1,1/2,3/4,5/8,11/16,\ldots$$ In other words, we start at zero, go $1$ unit to the rigth, $1/2$ unit to the left, $1/4$ of unit to the right, $1/8$ unit to the left, $\ldots$, $1/2^n$ unit to the left, is $n$ is odd and to the right if $n$ is odd.

This gives us the formula (in the case $a=0$, $b=1$) $$a_0=0,\qquad a_n=\sum_{i=0}^{n-1}(-2^{-1})^i$$ therefore the limit point is $\lim a_n=\sum_{i=0}^{\infty}(-2^{-1})^i=\frac{1}{1-(-2^{-1})}=\frac{2}{3}$.

In the case of general $a$ and $b$, we are not working on the unit interval, but rather on an interval of length $(b-a)$, and $a$ units to the right (left? Anyway...), so scaling gives us, for general $a$ and $b$, $$\lim a_n=a+\frac{2}{3}(b-a)=\frac{a+2b}{3}$$

If you want to be formal in the general case, show by induction that $a_n=a+(b-a)\sum_{i=0}^{n-1}(-2^{-1})^i$.


I learned to solve these using linear algebra.

$\begin {bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix}\begin{bmatrix}a_n\\a_n-1\end{bmatrix}$

$\begin {bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix}^n\begin{bmatrix}a_1\\a_0\end{bmatrix}$

diagonalize the matrix

$\begin {bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \frac 13\begin{bmatrix}1 &-1\\1&2\end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0& (-\frac 12)^n\end{bmatrix}\begin{bmatrix}2 &1\\-1&1\end{bmatrix}\begin{bmatrix}b\\a\end{bmatrix}$

We an apply the limit here, and and take $n$ to infinty. It will reduce the algebra that follows, but it is worth seeing how to come up with a general fromula for $a_n$

$\begin {bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \frac 13\begin{bmatrix}1 &-1\\1&2\end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0& (-\frac 12)^n\end{bmatrix}\begin{bmatrix}2b+a\\-b+a\end{bmatrix}$

$\begin {bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \frac 13\begin{bmatrix}1 &-1\\1&2\end{bmatrix}\begin{bmatrix}2b+a\\(-\frac 12)^n(-b+a)\end{bmatrix}$

$a_n = \frac 13 (2b+a + 2(-\frac12)^n(-b+a))$

As $n$ goes to infnity $\frac 13 (2b+a)$

  • $\begingroup$ In the end it should be $\frac{1}{3}(2b+a)$ (it's just a typo). $\endgroup$ – Luiz Cordeiro Sep 15 '16 at 19:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.