mathematical analysis problem. please help.

Kat-M · #1 $Old$ December 31st, 2008, 06:41 PM

suppose {x(n)} is a sequence such that
x(1)=1 and
x(n+1)=1+x(n)/(1+x(n+1)) ; n>=1

Prove that this sequence converges and find the limit.

I know how to find the limit of this sequence but dont know how to show that {x(n)} is a convergent sequence. Please help me on this.

Danny · #2 $Old$ December 31st, 2008, 07:12 PM

Quote:

Originally Posted by Kat-M $View Post$

suppose {x(n)} is a sequence such that
x(1)=1 and
x(n+1)=1+x(n)/(1+x(n+1)) ; n>=1

Prove that this sequence converges and find the limit.

I know how to find the limit of this sequence but dont know how to show that {x(n)} is a convergent sequence. Please help me on this.

First, multiplying the series by $1 + x_{n+1}$ gives

$x_{n+1} (1+x_{n+1})=1 + x_{n+1}+x_n$ or $x^2_{n+1} =1 + x_n$

To prove that the sequence converges we will prove two things

(i) the sequence is increasing and

(ii) it is bounded above

First off, I think it's clear that $x_n > 0$

(i) writing out the first few terms suggests its increasing. To prove this assume that

$x_{k} < x_{k+1}$

thus,

$x_{k} + 1 < x_{k+1} + 1\;\;\; \Rightarrow\;\;\;x^2_{k+1} < x^2_{k+2}$

so

$x_{k+1} < x_{k+2}$

and by induction, $x_{n} < x_{n+1}\;\; \forall n$

(ii) It is bounded by 2

The first few terms suggest this. Assume that

$x_{k} < 2$

then

$x_{k} + 1 < 2 + 1 = 3 < 4$

thus,

$x^2_{k+1} < 4\;\;\; \Rightarrow \;\;x_{k+1} < 2$

so again by induction, it is ture for all n. Since the sequence is increasing and bounded above, it must converge.

Danny · #3 $Old$ January 1st, 2009, 11:59 AM

Here's one very similar that I think can be solved exactly

$2 x^2_{n+1} = x_n + 1,\;\;\;x_0 = 0.$

Any ideas?

Kat-M · #4 $Old$ January 1st, 2009, 05:45 PM

i made a typo in the original question and i fixed it which is posted below.

Kat-M · #5 $Old$ January 1st, 2009, 05:57 PM

here is the correct problem. In the original question i had 1+x(n)/(1+x(n+1)) but it should be 1+x(n)/(1+x(n)).

suppose {x(n)} is a sequence such that
x(1)=1 and
x(n+1)=1+x(n)/(1+x(n)) ; n>=1

Prove that this sequence converges and find the limit.

I know how to find the limit of this sequence but dont know how to show that {x(n)} is a convergent sequence. Please help me on this.

HallsofIvy · #6 $Old$ January 2nd, 2009, 06:41 AM

Quote:

Originally Posted by Kat-M $View Post$

here is the correct problem. In the original question i had 1+x(n)/(1+x(n+1)) but it should be 1+x(n)/(1+x(n)).

I wondered about that! What you had originally seemed a strange way to write the formula.

Quote:

suppose {x(n)} is a sequence such that
x(1)=1 and
x(n+1)=1+x(n)/(1+x(n)) ; n>=1

Prove that this sequence converges and find the limit.

I know how to find the limit of this sequence but dont know how to show that {x(n)} is a convergent sequence. Please help me on this.

x(n+1)= 1+ x(n)/(1+ x(n)) which we can rewrite as [math]\frac{1+ 2x(n)}{1+ x(n)}= 2- 1/(1+ x(n)).

Assuming that the limit exists and is "x", we must have lim x(n+1)= 2- 1/(1+ lim x(n) or x= 2- 1/(x+1). Multiplying on both sides by x+1, $x^2+ x= 2x+ 2- 1$ or $x^2- x- 1= 0$ . The quadratic formula gives two possible values for x, $\frac{1- \sqrt{5}}{2}$ and $\frac{1+\sqrt{5}}{2}$ . Since x(n) is positive for all x, the limit must be $\frac{1+ \sqrt{5}}{2}$ . I presume that is what you got.

That is assuming the limit exists. We still need to prove that. Since x(1)= 1 is less than $\frac{1+ \sqrt{5}}{2}$ , the sequence has to increase to it and it seems reasonable to show that the sequence is increasing and has an upper bound- that is sufficient to show that it converges.

So, first we want to prove that the sequence is increasing: that x(n+1)> x(n) for all n. x(n+1)= 2- x(n)/(1+ x(n))> x(n), multiplying on both sides by the positive number 1+ x(n), is equivalent to $2+ 2x(n)- x(n)> x(n)^2+ x(n)$ or $x(n)^2- x(n)- 1< 0$ . We have already seen that $x^2- x- 1= 0$ only for $x= \frac{1- \sqrt{5}}{2}$ and $x= \frac{1+ \sqrt{5}}{2}$ . If x= 0, which is between those two values, then $(0)^2- 0 - 1= -1< 0$ so $x^2- x- 1< 0$ for all x between those values. x(n) is positive for all n so if we can prove that $x(n)< \frac{1+ \sqrt{5}}{2}$ for all n, we will have proved both that the sequence is increasing and that it has an upper bound and so converges.

Let's try induction. Clearly x(1)= 1< $\frac{1+\sqrt{5}}{2}$ , which is about 1.47. Suppose x(k)< $\frac{1+\sqrt{5}}{2}$
Then x(k)+ 1< $\frac{3+ \sqrt{5}}{2}$ , $\frac{1}{x(k)+1}> \frac{2}{3+ \sqrt{5}}$ , and $x(k+1)= 2- 1/(x(k)+1)< 2- \frac{2}{3+ \sqrt{5}}= \frac{4+\sqrt{5}}{3+ \sqrt{5}}$

Rationalizing the denominator, we have $x(n+1)< \frac{4+ 2\sqrt{5}}{3+ \sqrt{5}}\frac{3-\sqrt{5}}{3-\sqrt{5}}= \frac{2+ 2\sqrt{5}}{4}= \frac{1+ \sqrt{5}}{2}$ , exactly what was needed.

That is, since x(n) lies between $\frac{1- \sqrt{5}}{2}$ and $\frac{1+\sqrt{5}}{2}$ , it is, as we saw above, an increasing sequence. Further, since it has $\frac{1+ \sqrt{5}}{2}$ as upper bound, and is increasing, it is a convergent sequence.

Danny · #7 $Old$ January 2nd, 2009, 08:25 AM

Quote:

Originally Posted by Kat-M $View Post$

here is the correct problem. In the original question i had 1+x(n)/(1+x(n+1)) but it should be 1+x(n)/(1+x(n)).

suppose {x(n)} is a sequence such that
x(1)=1 and
x(n+1)=1+x(n)/(1+x(n)) ; n>=1

Prove that this sequence converges and find the limit.

I know how to find the limit of this sequence but dont know how to show that {x(n)} is a convergent sequence. Please help me on this.

Another way is to solve your problem directly. The substitution

$x_n = \frac{a y_n}{y_n + 1}$

for suitable $a$ (guess what number see HallsofIvy reply) the difference equation will become a linear difference equation which can be solved exactly.

Kat-M · #8 $Old$ January 2nd, 2009, 05:09 PM

HollsofIvy and danny arrigo. you two helped me a lot. Thank you so much.