# Homework Help: Contractive sequence

1. Nov 7, 2013

### bonfire09

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. Nov 7, 2013

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

3. Nov 7, 2013

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

4. Nov 7, 2013

### Dick

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.

5. Nov 7, 2013

### bonfire09

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.

6. Nov 7, 2013

### Dick

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

7. Nov 7, 2013

### bonfire09

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

8. Nov 7, 2013

### Dick

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

9. Nov 7, 2013

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

Last edited: Nov 7, 2013
10. Nov 7, 2013

### Dick

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.

11. Nov 7, 2013

### bonfire09

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

12. Nov 8, 2013

### 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:

Last edited: Nov 8, 2013
13. Nov 8, 2013

### Dick

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.

14. Nov 8, 2013

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

15. Nov 8, 2013

### Dick

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.

16. Nov 8, 2013

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

Last edited: Nov 8, 2013
17. Nov 8, 2013

### Dick

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?