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