3

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. ...
user2321
  • 699
  • 1
    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 http://math.stackexchange.com/questions/1260341/compute-lim-limitsn-to-inftya-n-where-a-n2-sqrta-n-a-n1. – Martin R May 27 '15 at 16:42
  • 1
    See http://en.wikipedia.org/wiki/Recurrence_relation#Solving – lab bhattacharjee 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? – user2321 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. – Martin R 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 :) – user2321 May 27 '15 at 17:09
  • This is what I am thinking with the sequence defined by 1/n. lim n-> infinity (1/n) = 0 Proof let e>0. Then for all n>1/e, 1/n < 1/(1/e) = e. Therefore limit is 0? – user2321 May 27 '15 at 17:17
  • @user2321: $\frac 1n \to 0$ is correct. But $a_n$ is not convergent. – Martin R May 27 '15 at 17:19

2 Answers2

3

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

Community
  • 1
Martin R
  • 113,040
0

Just to add another solution that I think might be insightful for some. You can use your computation to show this sequence is Cauchy also to find the limit: $$ a_{n}-a_{n-1} = -\frac{1}{2} ( a_{n-1} - a_{n-2}) = \cdots = \left( -\frac{1}{2} \right)^{n-1} $$ and now we note that $a_n$ can be written as a telescoping sum $$ a_n = a_n - a_0 = \sum_{k=1}^n ( a_k - a_{k-1}) = \sum_{k=1}^n \left( -\frac{1}{2} \right)^{k-1}, $$ which directly leads to the limit of the sequence being $$ \lim_{n\to \infty} a_n = \sum_{k=1}^\infty \left( -\frac{1}{2} \right)^{k-1} = \sum_{k=0}^\infty \left( -\frac{1}{2} \right)^{k} = \frac{1}{1- (-1/2)} = \frac{2}{3} $$ as this is a geometric series.

Hrodelbert
  • 1,029