Finding the limit of a recursively defined sequence (recurrence relation). Specifically and generally Whilst reading Goldrei's Classic Set Theory, I have come across a recursively defined sequence
$a_0=0, a_1=1, a_n=\frac{1}{2}\left(a_{n-1} + a_{n-2} \right) $
The first few terms of which are:
$0, 1, \frac{1}{2}, \frac{3}{4}, \frac{5}{8}, \frac{11}{16}, ... $
It is easy to show the successive terms get closer to one another
$ |a_n - a_{n-1} |= | \frac{1}{2}\left(a_{n-1} + a_{n-2}\right) - a_{n-1} |$
$ = \frac{1}{2}|a_{n-1} - a_{n-2}|  $
Inducting on the "first difference" gives
$ |a_n - a_{n-1} | = \frac{1}{2}^{n-1}|a_1 - a_0| $
$ = \frac{1}{2}^{n-1} $
So I have shown that the difference between each successive term approaches zero, i.e. the sequence approaches a limit.
How do I find the limit of the recursively defined sequence?
How are these types of problems (recursively defined functions) generally approached? It is:


*

*Show the sequence converges

*...

 A: $$
a_0=0, a_1=1, a_n=\frac{1}{2}\left(a_{n-1} + a_{n-2} \right) \tag 1
$$
is a Linear homogeneous recurrence relations with constant coefficients of the order $2$. As explained in that Wikipedia article, the
solution has the form
$$
a_n = C \lambda_1^n + D \lambda_2^n
$$ 
where $\lambda_{1,2}$ are solutions of the "characteristic equation",
in this case
$$
 r^2  = \frac 12 (r + 1) \, , \tag 2
$$
and $C, D$ are determined from the initial values $a_0, a_1$.
$(2)$ has the solutions $\lambda_1 = 1$, $\lambda_2 = -\frac 12$,
and together with $a_0 = 0$, $a_1 = 1$ it follows that 
$$
a_n = \frac 23 - \frac 23 \bigl(-\frac 12 \bigr)^n \, . \tag 3
$$

Another approach is the "generating function". Here is a very brief
sketch of that method: You define formally the power series
$$
f(z) = \sum_{n=0}^\infty a_n z^n
$$
and use the recurrence relation $(1)$ to conclude that
$$
\bigl(1 - \frac 12 z - \frac 12 z^2 \bigr) f(z) = z \, .
$$
Therefore
$$
f(z) = \frac{z}{1 - \frac 12 z - \frac 12 z^2 }
 = \frac{z}{\bigl( 1-z \bigr)\bigl(1 + \frac z2 \bigr)}
 = \frac 23 \frac{1}{1-z} - \frac 23 \frac{1}{1+\frac z2} \, .
$$
Using the well-known formula for the geometric series, the
explicit formula $(3)$ for the coefficients $a_n$ can be derived.

For this particular sequence, the limit can be determined easier.
You already observed that
$$
a_n - a_{n-1} = -\frac 12 (a_{n-1} - a_{n-2})
$$
and therefore
$$
\lim_{n \to \infty} \bigl(a_n - a_{n-1}\bigr) = 0 \, . \tag 4
$$
Another observation (taken from https://math.stackexchange.com/a/1260371/42969) is
that 
$$
a_n + \frac 12 a_{n-1} = a_{n-1} + \frac 12  a_{n-2} = \ldots
= a_1 + \frac 12 a_0 = 1 
$$
and therefore
$$
\lim_{n \to \infty} \bigl(a_n + \frac 12 a_{n-1} \bigr)= 1 \, . \tag 5
$$
Now combine $(4)$ and $(5)$ to conclude that $\lim_{n \to \infty}
a_n = \frac 23 \, $.
