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:

1. Show the sequence converges
2. ...
• That the differences between successive terms approaches zero does not in general prove that the sequence is convergent (consider the harmonic series). – A "related" sequence is considered here math.stackexchange.com/questions/1260341/…. May 27 '15 at 16:42
• May 27 '15 at 16:45
• By convergence, I mean that the nth term in the sequence approaches a limit. If the difference between successive terms goes to 0 as n goes to infinity, does not the nth term converge to a value? I realise its sum is not convergent, but what about its nth term? May 27 '15 at 16:57
• @user2321: With $a_n = 1 + \frac 12 + \ldots + \frac 1n$ you have $a_{n+1} - a_n \to 0$, but the sequence $(a_n)$ is not convergent. May 27 '15 at 17:05
• Ah OK, so for that particular sequence (harmonic series 1/n) we don't say it converges to 0? Some reading required for me :) May 27 '15 at 17:09

$$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 \,$.