• Dec 31st 2008, 04:41 PM
Kat-M
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.
• Dec 31st 2008, 05:12 PM
Jester
Quote:

Originally Posted by Kat-M
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 $\displaystyle 1 + x_{n+1}$ gives

$\displaystyle x_{n+1} (1+x_{n+1})=1 + x_{n+1}+x_n$ or $\displaystyle 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 $\displaystyle x_n > 0$

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

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

thus,

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

so

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

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

(ii) It is bounded by 2

The first few terms suggest this. Assume that

$\displaystyle x_{k} < 2$

then

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

thus,

$\displaystyle 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.
• Jan 1st 2009, 09:59 AM
Jester
Here's one very similar that I think can be solved exactly

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

Any ideas?
• Jan 1st 2009, 03:45 PM
Kat-M
thanks
i made a typo in the original question and i fixed it which is posted below.
• Jan 1st 2009, 03:57 PM
Kat-M
oops i had a typo in the question.
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.
• Jan 2nd 2009, 04:41 AM
HallsofIvy
Quote:

Originally Posted by Kat-M
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 [tex]\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, $\displaystyle x^2+ x= 2x+ 2- 1$ or $\displaystyle x^2- x- 1= 0$. The quadratic formula gives two possible values for x, $\displaystyle \frac{1- \sqrt{5}}{2}$ and $\displaystyle \frac{1+\sqrt{5}}{2}$. Since x(n) is positive for all x, the limit must be $\displaystyle \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 $\displaystyle \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 $\displaystyle 2+ 2x(n)- x(n)> x(n)^2+ x(n)$ or $\displaystyle x(n)^2- x(n)- 1< 0$. We have already seen that $\displaystyle x^2- x- 1= 0$ only for $\displaystyle x= \frac{1- \sqrt{5}}{2}$ and $\displaystyle x= \frac{1+ \sqrt{5}}{2}$. If x= 0, which is between those two values, then $\displaystyle (0)^2- 0 - 1= -1< 0$ so $\displaystyle x^2- x- 1< 0$ for all x between those values. x(n) is positive for all n so if we can prove that $\displaystyle 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< $\displaystyle \frac{1+\sqrt{5}}{2}$, which is about 1.47. Suppose x(k)< $\displaystyle \frac{1+\sqrt{5}}{2}$
Then x(k)+ 1< $\displaystyle \frac{3+ \sqrt{5}}{2}$, $\displaystyle \frac{1}{x(k)+1}> \frac{2}{3+ \sqrt{5}}$, and $\displaystyle 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 $\displaystyle 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 $\displaystyle \frac{1- \sqrt{5}}{2}$ and $\displaystyle \frac{1+\sqrt{5}}{2}$, it is, as we saw above, an increasing sequence. Further, since it has $\displaystyle \frac{1+ \sqrt{5}}{2}$ as upper bound, and is increasing, it is a convergent sequence.
• Jan 2nd 2009, 06:25 AM
Jester
Quote:

Originally Posted by Kat-M
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

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

for suitable $\displaystyle a$ (guess what number see HallsofIvy reply) the difference equation will become a linear difference equation which can be solved exactly.
• Jan 2nd 2009, 03:09 PM
Kat-M
Thank you very much
HollsofIvy and danny arrigo. you two helped me a lot. Thank you so much.