# Prove recursive sequence to be contractive

glomar

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

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

Last edited:

Mentor
Looks OK, but you need to use the fact that
$$x_{n + 1} = 1 + \frac{1}{x_n}$$

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.

glomar
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!

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.

glomar
Thank you for the typing suggestions. I'm still trying to put the subscripts.
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!