Prove recursive sequence to be contractive

[glomar]

1. The problem statement, all variables and given/known data

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

2. Relevant equations



3. 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!

[Mark44]

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!

[Mark44]

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