Results 1 to 2 of 2

Math Help - recursive sequence

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

    recursive sequence

    Suppose a sequence is defined by  a_0 = 0 ,  a_1 = 1 , and  a_{n+1} = \frac{1}{2}\left(a_{n}+a_{n-1}\right) for  n \geq 2 . Prove  a_n converges and determine its limit.

    So  a_n = \frac{1}{2}\left(a_{n-1}+a_{n-2} \right) . This means that for all  \varepsilon > 0 , there exists  N \in \mathbb{N}, such that whenever  n \geq N , then  |a_{n}-L| < \varepsilon and  |a_{n+1}-L| < \varepsilon .

    Is this the right way to go about proving it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by particlejohn View Post
    So  a_n = \frac{1}{2}\left(a_{n-1}+a_{n-2} \right) . This means that for all  \varepsilon > 0 , there exists  N \in \mathbb{N}, such that whenever  n \geq N , then  |a_{n}-L| < \varepsilon and  |a_{n+1}-L| < \varepsilon .

    Is this the right way to go about proving it?
    Yes I believe thats ok... Its induction isnt it?


    Quote Originally Posted by particlejohn View Post
    Suppose a sequence is defined by  a_0 = 0 ,  a_1 = 1 , and  a_{n+1} = \frac{1}{2}\left(a_{n}+a_{n-1}\right) for  n \geq 2 . Prove  a_n converges and determine its limit.

    Well there could be different ways to the limit, i tried the hardest way out there. I actually found out the sequence explicitly

    There are different approaches, one of them is using generating functions and the other is by redefining the sequence and simple algebraic tricks.

    I will do it using generating functions,

    Let f(x) = \sum_{k=0}^{k=\infty} a_k x^k

    This means f(x) - \frac{xf(x)+x^2f(x)}2 = a_0 + \left(a_1 - \frac{a_0}{2}\right)x+ \sum_{k=2}^{k=\infty} \left(a_k - \frac{a_{k-1} + a_{k-2}}2\right) x^k

    But for our series, \forall k \ge 2, a_k - \frac{a_{k-1} + a_{k-2}}2 = 0. And a_1 = 1, a_0 = 0.

    Thus,
    f(x) - \frac{xf(x)+x^2f(x)}2 = x

    f(x) = \dfrac{2x}{2 - x - x^2} = \dfrac{2x}{(1-x)(x+2)} = \frac23\left(-\dfrac{1}{1 + \frac{x}2} + \dfrac{1}{1-x}\right)

    Clearly both can be represented as geometric progressions. And also the above function exists for some values of x(its called the region of convergence)

    -\dfrac{1}{1 + \frac{x}2} = -\sum_{k=0}^{k=\infty} \left(\frac{-x}{2}\right)^k

     \dfrac{1}{1-x} = \sum_{k=0}^{k=\infty} x^k

    Thus:

    f(x)=-\sum_{k=0}^{k=\infty}\frac23 \left(\frac{-x}{2}\right)^k + \sum_{k=0}^{k=\infty} \frac23 x^k

    f(x)=\frac23\sum_{k=0}^{k=\infty} \left(1-\left(\frac{-1}{2}\right)^k\right)x^k = \sum_{k=0}^{k=\infty} a_k x^k

    By polynomial equality,

    a_k = \frac23\left(1-\left(\frac{-1}{2}\right)^k\right)



    Now very clearly, \lim_{k \to \infty} a_k = \frac23.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursive sequence of primes
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 9th 2011, 06:44 AM
  2. Recursive sequence and limits help
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 6th 2010, 01:39 AM
  3. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  4. recursive sequence
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 29th 2009, 05:15 AM
  5. recursive sequence
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 14th 2009, 06:33 AM

Search Tags


/mathhelpforum @mathhelpforum