1. Not finding help here? Sign up for a free 30min 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!

Contractive sequence

  1. Nov 7, 2013 #1
    1. The problem statement, all variables and given/known data
    If ##x_1 < x_2## are arbitrary real numbers and ##x_n=\frac{1}{2}(x_{n-2}+x_{n-1})## for## n > 2##, show that ##(x_n)## is convergent.


    2. Relevant equations

    Definition of Contractive Sequence: We say that a sequence ##X=(x_n)## of real numbers is contractive if there exists a constant ##C##; ##0 < C < 1##, such that ##|x_{n+2}-x_{n+1}|\leq C|x_{n+1}-x_{n}|## for all ##n\in\mathbb{N}##. The number ##C## is called the constant of the contractive sequence.


    3. The attempt at a solution
    I know this sequence is not monotone so I think I need to use contraction. All I have is that ## |x_{n+2}-x_{n+1}|=| \frac{1}{2}(x_{n}+x_{n+1}-\frac{1}{2}(x_{n-1}+x_n|=|\frac{1}{2}x_{n+1}-\frac{1}{2}x_{n-1}|## and ##|x_{n+1}-x_n|=|\frac{1}{2}(x_{n-1}+x_n)-\frac{1}{2}(x_{n-2}+x_{n-1}|=\frac{1}{2}|x_n-x_{n-2}|##. But I can't seem to show that ##\frac{1}{2}|x_{n+1}-x_n|\leq \frac{1}{2}|x_n-x_{n-2}|## which I think is not possible but I am not sure. I think cauchy might work too but not sure how to apply it here.
     
    Last edited: Nov 7, 2013
  2. jcsd
  3. Nov 7, 2013 #2
    You've show that |##x_{n+2} -x_{n+1}##| = 1/2|##x_{n+1} -x_{n-1}##| and you wish that last ##x_{n-1}## were ##x_{n}## because then you would have it. I messed around with that a bit and didn't immediately see anything too promising.

    I think I would try induction. Show it's true for n =2. Then see if you can do an induction step.
     
  4. Nov 7, 2013 #3
    I think I might have to prove that it is a Cauchy Sequence instead. So what I would have is then for scratchwork is that there exists a ##h\in\mathbb{N}## such that if ##n>m## and ##n,m \geq h## then ##|x_n-x_m|=|\frac{1}{2}x_{n-2}+\frac{1}{2}x_{n-1}-\frac{1}{2}x_{m-2}+\frac{1}{2}x_{m-1}|##. But from here I don't know what to do.
     
  5. Nov 7, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Start with a numerical example to try to see what to do in the general case. Suppose x0=0 and x1=1. So |x1-x0|=1. x2=1/2, so |x2-x1|=1/2. x3=3/4, so |x4-x3|=1/4. Etc etc. Now see if you can figure out what going on and generalize that. And I think you have a typo in your problem statement. You mean ##x_n=\frac{1}{2}(x_{n-2}+x_{n-1})##, right? The induction brmath suggests might be helpful.
     
  6. Nov 7, 2013 #5
    Well this problem is located in the Cauchy Sequence section and im think this sequence does look Cauchy to me. I'm thinking if I can somehow bound ##|x_n-x_m|## by ##\frac{1}{2^{n-1}}## because of the ##\frac{1}{2}## then I would have it since ##\frac{1}{2^{n-1}}## is convergent. Oh yeah thanks I fixed the problem.
     
  7. Nov 7, 2013 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, and an extension of that argument would show any contractive sequence is Cauchy and hence convergent, right?
     
  8. Nov 7, 2013 #7
    Yes but I doubt I can get anywhere with it proving its contractive. I think im stuck pretty badly.
     
  9. Nov 7, 2013 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I thought from your last comment in post 5 that you had the solution. What's bugging you? How far did you get?
     
  10. Nov 7, 2013 #9
    The bounding part. Showing that ##|x_n-x_m|= |(\frac{1}{2}x_{n-2}+\frac{1}{2}x_{n-1})-(\frac{1}{2}x_{m-2}+\frac{1}{2}x_{m-1})|\leq \frac{1}{2^{n-1}}##.
     
    Last edited: Nov 7, 2013
  11. Nov 7, 2013 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's not. The difference |xn-xm| is dependent on what x0 and x1 are. If |x1-x0|=C can you show |x2-x1|=C/2? Extend that. It's going to boil down to a geometric series argument to show it's Cauchy.
     
  12. Nov 7, 2013 #11
    Ahh ok I will try to take it from here and post what I get when im finished.
     
  13. Nov 8, 2013 #12
    If ##|x_2-x_1|=c## and ##x_1<x_2##. Then ##x_3=\frac{1}{2}(x_1+x_2)##. It follows ##\frac{1}{2}|x_3-x_2|=\frac{c}{2}##. So I from here what I see is that if ##|x_1-x_2|=c## then ##|(x_1-x_2)+(x_2-x_3)+...+(x_{n-1}-x_n)|\leq |x_1-x_2|+|x_2-x_3|+...+|x_{n-1}-x_n|= c+\frac{1}{2}c+...+\frac{1}{2^{n-1}}c=2c(1-\frac{1}{2^n})## which I know that ##2c(1-\frac{1}{2^n})## converges. I hope I got this part right. And for the first part I think I can use induction to prove it.

    Proof:
     
    Last edited: Nov 8, 2013
  14. Nov 8, 2013 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Proving it's Cauchy means you want to show |xn-xm| can be made small by making n and m large. An estimate of |x1-xn| won't help with that. Don't start from x1.
     
  15. Nov 8, 2013 #14
    Proof:
    This is what I have so far.
    Let ##\epsilon>0## and let ##h\in\mathbb{N}## such that if ##m,n \geq h## and ##m>n## then ##|x_m-x_n|=|(x_m-x_{m-1})+(x_{m-1}-x_{m-2})+....+(x_{n-1}-x_n)| \leq |x_m-x_{m-1}|+...+|x_{n-1}-x_n|##. Suppose ##|x_m-x_{m-1}|=c##. It follows from my previous statement that ##|x_m-x_{m-1}|+...+|x_{n-1}-x_n|=c+\frac{c}{2}+...+\frac{c}{2^{n-1}}=2c(1-\frac{1}{2^n})<\epsilon## since we know ##2c(1-\frac{1}{2^n})## converges. I think this might be right maybe my indexes are off. Not sure.
     
  16. Nov 8, 2013 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I didn't check the details of the indices yet. The problem with showing that that is less than ε is that ##2c(1-\frac{1}{2^n})## converges alright, but it doesn't converge to 0. Think about it a bit.
     
  17. Nov 8, 2013 #16
    Oh yeah it converges to ##2c## and we need something that converges to ##0## since ##\epsilon## is arbitrary. But I don't think there is another sequence bigger than ##2c(1-\frac{1}{2^n})## that converges to 0 because if it did then some of the terms of that sequence would be smaller than ##2c(1-\frac{1}{2^n})##. Oh could I just do this ##2c(1-\frac{1}{2^n})=(2c-\frac{2c}{2^n})=\frac{1}{2^n}(2c*2^n-2c)## and since ##\frac{1}{2^n}## converges to 0 the whole thing must converge to 0.
     
    Last edited: Nov 8, 2013
  18. Nov 8, 2013 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, no. Define c=|x2-x1| once and for all. What's |x3-x2|? What's ##|x_m-x_{m-1}|##? Remember that inductive proof you were going to do?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Contractive sequence
  1. Contraction mapping, (Replies: 1)

  2. Is this a sequence? (Replies: 1)

Loading...