2
$\begingroup$

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. ...
$\endgroup$
  • 1
    $\begingroup$ 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/…. $\endgroup$ – Martin R May 27 '15 at 16:42
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Recurrence_relation#Solving $\endgroup$ – lab bhattacharjee May 27 '15 at 16:45
  • $\begingroup$ 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? $\endgroup$ – user2321 May 27 '15 at 16:57
  • $\begingroup$ @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. $\endgroup$ – Martin R May 27 '15 at 17:05
  • $\begingroup$ Ah OK, so for that particular sequence (harmonic series 1/n) we don't say it converges to 0? Some reading required for me :) $\endgroup$ – user2321 May 27 '15 at 17:09
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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