Show Convergence of Contractive Sequence Homework

[bonfire09]

Homework Statement

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.

Homework 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.

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.

 

[brmath]

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.

 

[bonfire09]

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.

 

[Dick]

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.

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.

 

[bonfire09]

Well this problem is located in the Cauchy Sequence section and I am 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.

 

[Dick]

Well this problem is located in the Cauchy Sequence section and I am 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.

Yes, and an extension of that argument would show any contractive sequence is Cauchy and hence convergent, right?

 

[bonfire09]

Yes but I doubt I can get anywhere with it proving its contractive. I think I am stuck pretty badly.

 

[Dick]

Yes but I doubt I can get anywhere with it proving its contractive. I think I am stuck pretty badly.

I thought from your last comment in post 5 that you had the solution. What's bugging you? How far did you get?

 

[bonfire09]

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}}##.

 

[Dick]

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}}##.

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.

 

[bonfire09]

Ahh ok I will try to take it from here and post what I get when I am finished.

 

[bonfire09]

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:

 

[Dick]

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.

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.

 

[bonfire09]

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.

 

[Dick]

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.

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.

 

[bonfire09]

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.

 

[Dick]

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.

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?