• Support PF! Buy your school textbooks, materials and every day products Here!

Prove recursive sequence to be contractive

  • Thread starter glomar
  • Start date
  • #1
5
0

Homework Statement



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)].

Homework Equations





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:

Answers and Replies

  • #2
33,173
4,858
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.
 
  • #3
5
0
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!
 
  • #4
33,173
4,858
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.
 
  • #5
5
0
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!
 

Related Threads for: Prove recursive sequence to be contractive

Replies
6
Views
988
Replies
3
Views
3K
Replies
7
Views
7K
Replies
4
Views
892
Replies
5
Views
12K
  • Last Post
Replies
5
Views
9K
  • Last Post
Replies
6
Views
7K
Top