Results 1 to 7 of 7

Math Help - Recurrence relation

  1. #1
    Super Member
    Joined
    Dec 2009
    Posts
    755

    Recurrence relation

    A sequence of real numbers {U_n} satisfies the recurrence relation

    U_{n+1}=\frac{1}{2}U_n+1 for all positive integer n.

    a) Given that {U_n} converges to l, find the value of l

    b) If U_n < l, show that U_n<U_{n+1}<l






    I was able to find that l=2 for part a.

    For (b), what I have done is:

    2U_{n+1}-2=U_n

    2U_{n+1}-2<2

    U_{n+1}<0

    How do I continue? Or am I going in the wrong direction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Recurrence relation

    Quote Originally Posted by Punch View Post
    2U_{n+1}-2<2

    U_{n+1}<0
    The last line should be 2U_{n+1}<4.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Recurrence relation

    The recurrence relation can be written as...

    \Delta_{n}=u_{n+1}-u_{n}= 1-\frac{u_{n}}{2}= f(u_{n}) (1)

    As explained in...

    http://www.mathhelpforum.com/math-he...-i-188482.html

    ... has only one 'atrractive fixed point' in x=2 and because for all x is |f(x)|\le |x_{0}-x| all initial value u_{0} will produce a sequence monotonically convergent to 2...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2009
    Posts
    755

    Re: Recurrence relation

    Quote Originally Posted by emakarov View Post
    The last line should be 2U_{n+1}<4.
    Then U_{n+1}<2, how do I continue to show that U_n<U_{n+1}<l?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Recurrence relation

    U_n<2\implies U_n+U_n<2+U_n\implies U_n<1+U_n/2=U_{n+1}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2009
    Posts
    755

    Re: Recurrence relation

    Quote Originally Posted by emakarov View Post
    U_n<2\implies U_n+U_n<2+U_n\implies U_n<1+U_n/2=U_{n+1}
    Thank you, how did you think of that?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Recurrence relation

    Good question. I just solved the inequality U_n<U_n/2+1 and found that it is equivalent to U_n<2, so in particular the latter implies the former.

    I have a feeling that solving two inequalities to prove U_{n+1}<2 and U_n<U_{n+1} is repeating some work, but to understand it better I probably need to read chisigma's tutorial...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum