1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove recursive sequence to be contractive

  1. May 15, 2009 #1
    1. The problem statement, all variables and given/known data

    Consider the sequence (x(n)) defined recursively by x(1)=1 and x(n+1)=1+1/x(n).
    Prove that abs[x(n+2)-x(n+1)]<= 1/2 abs[x(n+1)-x(n)].

    2. Relevant equations



    3. The attempt at a solution


    Proof by induction.
    For n=1, abs(x(3)-x(2))<= 1/2 abs(x(2)-x(1))
    abs(-1/2)<=1/2 abs(1)
    1/2=1/2

    So, for n=1 is true.

    Suppose that n=k and that

    abs[x(k+2)-x(k+1)]<= 1/2 abs[x(k+1)-x(k)]. We have to show that


    abs[x((k+1)+2)-x((k+1)+1)]<= 1/2 abs[x((k+1)+1)-x(k+1)].



    I'm not sure if this is correct. If so, how can I continue?

    Thanks in advance!
     
    Last edited: May 15, 2009
  2. jcsd
  3. May 16, 2009 #2

    Mark44

    Staff: Mentor

    Looks OK, but you need to use the fact that
    [tex]x_{n + 1} = 1 + \frac{1}{x_n}[/tex]

    Have you looked at the numbers in this sequence?
    x1 = 1
    x2 = 1 + 1/1 = 2
    x3 = 1 + 1/2 = 3/2
    x4 = 1 + 1/(3/2) = 5/3
    x5 = 1 + 1/(5/3) = 8/5
    and so on.
     
  4. May 16, 2009 #3
    Yes,

    So far what I have is

    abs((x(n+2)-x(n+1))= abs(1/x(n) - 1/x(n+1)). I think what I have to prove by induction is
    x(n)>=1.
    So, for n=1 , x1=1 is true. Assuming n=k and x(k) is true, I have that
    x(k+1)= 1+ 1/x(k).
    Since x(k)>= 1, 1/x(k) < 1. So 1+ 1/x(k) >=1.

    I'm I in the right direction?
    Thanks!
     
  5. May 16, 2009 #4

    Mark44

    Staff: Mentor

    You were before, but now you aren't.
    As it turns out, xn >= 1 for all n, but that's not what you are asked to prove. You are supposed to show that the sequence is contractive, which if I'm remembering correctly means that successive pairs of sequence elements get closer and closer together. Specifically, you are asked to prove that for the given sequence, |xn+2 - xn+1| <= 1/2 * |xn+1 - xn|.

    Note: your work would be much easier to read if you use | | for absolute values and subscripts for your sequence terms (using sub and /sub pairs, with both tags surrounded by square brackets []).​

    You have established the base case; i.e., that |x3 - x2| <= 1/2 * |x2 - x1|.

    You are assuming in your induction hypothesis that the following is true:
    |xk+2 - xk+1| <= 1/2 * |xk+1 - xk|.

    You now need to show that this is true:
    |xk+3 - xk+2| <= 1/2 * |xk+2 - xk+1|.

    It's easy enough to establish that
    |xk+3 - xk+2| = |1/(xk+2) - 1/(xk+1)|, using the recursive definition for xn+1 in terms of xn.

    Now there are only two things left to do: 1) do some easy algebra on the fractions on the right side of the equation above; 2) establish (via induction?) that xn * xn+1 >= 2 for all n >= 1.
     
  6. May 16, 2009 #5
    Thank you for the typing suggestions. I'm still trying to put the subscripts.
    Here is my proof about
    xn * xn+1 >= 2 for all n >= 1.

    For n=1 , x1 * x2 = 2 so it's true.
    Suppose that xn * xn+1 >= 2 is true. Then,
    xn+2 * xn+1 =
    (1 + 1/xn) xn+1 =
    xn+1 + 1 =
    (1 + 1/xn) + 1 =
    1/xn + 2 >=2

    Hence,
    xn+2 * xn+1 >= 2 for all n>=1.

    This implies that
    1/(xn+2 * xn+1) <= 2 for all n>=1.

    So,
    |xk+3 - xk+2| = |1/(xk+2) - 1/(xk+1)|=
    |xn+1-xn+2|/(xn+2 * xn+1)|<= |xn+1-xn+2|/2

    Therefore,

    |xk+3 - xk+2|<= |xn+1-xn+2|/2


    How did I do?
    Thanks again!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook