How to prove a recursive formula converges.

[Polarbum]

Homework Statement

Prove that the recursive sequence, a_(n+1) = 2/ [ 1/3 + 1/ (4+ a_n ) ], converges.

Homework Equations

The Attempt at a Solution

The recursive formula converges very quickly, no matter where you start, but why? and how do I prove that it is so?

 

[HallsofIvy]

So this is
a_{n+1}= \frac{2}{\frac{1}{3}+\frac{1}{4+a_n}}
= \frac{2}{\frac{7+ a_n}{3(4+a_n)}}= \frac{6(4+ a_n)}{7+ a_n}

If that converges to, say, a, taking the limit on both sides of that equation gives
a= \frac{6(4+ a)}{7+ a}
so a(7+a)= 6(4+ a) or a^2+ 7a= 24+ 6a, a^2+ a- 24= 0 which means that the sequence converges to
a= \frac{-1\pm\sqrt{1+ 96}}{2}= \frac{-1\pm\sqrt{97}}{2}
depending on whether a₁ is greater than or equal to -4. (Assuming that I haven't made some silly arithmetic error which you had better check!)

In order to prove that it does converge you could probably use "monotone convergenc": if an increasing sequence has an upper bound, then it converges and if a decreasing sequence has a lower bound, then it converges.

\sqrt{97}< 10 so (-1+\sqrt{97})/2< 9/2< 5. You should be able to prove, probably by induction on n, that, if a₁> -4, then {a_n} is an increasing sequence and has 5 as an upper bound.

Similarly, (-1-\sqrt{97})/2&gt; -11/2&gt; -6. You should be able to prove that, if a₁< -4, then {a_n} is a decreasing sequence and has -6 as a lower bound.

 

[g_edgar]

So this is
a_{n+1} = \frac{6(4+ a_n)}{7+ a_n}

Once it is written this way, there is a standard technique for analysis. It involves using the matrix
A = \left[\begin{array} &amp;6\qquad 24&amp; 1\qquad 7\end{array}\right]
So it becomes a problem in linear algebra.

 

[kof9595995]

So this is
a_{n+1}= \frac{2}{\frac{1}{3}+\frac{1}{4+a_n}}
= \frac{2}{\frac{7+ a_n}{3(4+a_n)}}= \frac{6(4+ a_n)}{7+ a_n}

If that converges to, say, a, taking the limit on both sides of that equation gives
a= \frac{6(4+ a)}{7+ a}
so a(7+a)= 6(4+ a) or a^2+ 7a= 24+ 6a, a^2+ a- 24= 0 which means that the sequence converges to
a= \frac{-1\pm\sqrt{1+ 96}}{2}= \frac{-1\pm\sqrt{97}}{2}
depending on whether a₁ is greater than or equal to -4. (Assuming that I haven't made some silly arithmetic error which you had better check!)

In order to prove that it does converge you could probably use "monotone convergenc": if an increasing sequence has an upper bound, then it converges and if a decreasing sequence has a lower bound, then it converges.

\sqrt{97}&lt; 10 so (-1+\sqrt{97})/2&lt; 9/2&lt; 5. You should be able to prove, probably by induction on n, that, if a₁> -4, then {a_n} is an increasing sequence and has 5 as an upper bound.

Similarly, (-1-\sqrt{97})/2&gt; -11/2&gt; -6. You should be able to prove that, if a₁< -4, then {a_n} is a decreasing sequence and has -6 as a lower bound.

Is this proof valid?I don't think it's logical to take limit on both sides before you prove the squence is convergent.

 

[statdad]

"Is this proof valid?I don't think it's logical to take limit on both sides before you prove the squence is convergent."

This is a common "trick" - notice that Halls prefaced his comments by saying If this converges . You haven't formally proven it converges, but this approach can often give you

1) An idea as to the value of the limit
2) What type of initial conditions must hold in order for convergence to occur

As was noted, you must still show that convergence occurs.

 

[kof9595995]

So this is
\sqrt{97}&lt; 10 so (-1+\sqrt{97})/2&lt; 9/2&lt; 5. You should be able to prove, probably by induction on n, that, if a₁> -4, then {a_n} is an increasing sequence and has 5 as an upper bound.

Similarly, (-1-\sqrt{97})/2&gt; -11/2&gt; -6. You should be able to prove that, if a₁< -4, then {a_n} is a decreasing sequence and has -6 as a lower bound.

I doubt the validity of this part, since the limit may not exist, how could we use it to prove the sequence is bounded?

 

[cipher42]

I doubt the validity of this part, since the limit may not exist, how could we use it to prove the sequence is bounded?

He's not using the limit to prove the boundedness of the sequence (that would be faulty logic: assuming what you're trying to prove). Rather, he's using what the limit would have to be IF the sequence converges to help him pick a good candidate for an upper/lower bound (notice that he didn't even suggest using the tentative limit as the bound, but rather something slightly larger/smaller than that...doing the hypothetical side calculation about what the limit would need to be IF (big if!) it exists merely gives you a good place to start looking for hand-holds get get your proof going)

 

[kof9595995]

He's not using the limit to prove the boundedness of the sequence (that would be faulty logic: assuming what you're trying to prove). Rather, he's using what the limit would have to be IF the sequence converges to help him pick a good candidate for an upper/lower bound (notice that he didn't even suggest using the tentative limit as the bound, but rather something slightly larger/smaller than that...doing the hypothetical side calculation about what the limit would need to be IF (big if!) it exists merely gives you a good place to start looking for hand-holds get get your proof going)

Ok, got it, I misunderstood the post, thanks for the clarification.

 

[Polarbum]

So this is
a_{n+1}= \frac{2}{\frac{1}{3}+\frac{1}{4+a_n}}
= \frac{2}{\frac{7+ a_n}{3(4+a_n)}}= \frac{6(4+ a_n)}{7+ a_n}

If that converges to, say, a, taking the limit on both sides of that equation gives
a= \frac{6(4+ a)}{7+ a}
so a(7+a)= 6(4+ a) or a^2+ 7a= 24+ 6a, a^2+ a- 24= 0 which means that the sequence converges to
a= \frac{-1\pm\sqrt{1+ 96}}{2}= \frac{-1\pm\sqrt{97}}{2}
depending on whether a₁ is greater than or equal to -4. (Assuming that I haven't made some silly arithmetic error which you had better check!)

In order to prove that it does converge you could probably use "monotone convergenc": if an increasing sequence has an upper bound, then it converges and if a decreasing sequence has a lower bound, then it converges.

\sqrt{97}&lt; 10 so (-1+\sqrt{97})/2&lt; 9/2&lt; 5. You should be able to prove, probably by induction on n, that, if a₁> -4, then {a_n} is an increasing sequence and has 5 as an upper bound.

Similarly, (-1-\sqrt{97})/2&gt; -11/2&gt; -6. You should be able to prove that, if a₁< -4, then {a_n} is a decreasing sequence and has -6 as a lower bound.

Thank you, that worked well for proving that it converges. My next issue concerns determining a rate of convergence. I know how to treat a sequence in explicit form to determine what the rate of convergence is, but I don't know how to take a non-linear recurrence relation and make it explicit. Any thoughts?

 

[kof9595995]

There is a general technique for this kind of recursive formula, but since your example is a little
tedious to work out,I'll show you how this kind of question is solved using my example,say,
a_{n + 1} = \frac{4 + a_n }{1 + a_n }
then find the fix point for the formula,let
a = \frac{4 + a}{1 + a }
solve it you get a = \pm 2
take either value,say,-2
then
a_{n + 1} - ( - 2) = a_{n + 1} + 2 = \frac{4 + a_n }{1 + a_n } + 2 = \frac{3(2 + a_n )}{1 + a_n } = \frac{3(2 + a_n )}{2 + a_n - 1}<br />
take reciprocals on both sides:
<br /> \frac{1}{a_{n + 1} + 2} = \frac{1}{3} - \frac{1}{3}\frac{1}{(a_{n} + 2)}<br />
then let
b_n = \frac{1}{a_{n } + 2}
you'll get
<br /> b_{n + 1} = \frac{1}{3} - \frac{1}{3}b_n <br />
this is a linear recursive formula,then you know what to do with it.

 

[kof9595995]

I'm not quite familiar with the matrix technique, but I guess what g_edgar said indeed is the same with mine but in matrix language, probably it'll become a problem of matrix diagolization

 

[g_edgar]

I'm not quite familiar with the matrix technique, but I guess what g_edgar said indeed is the same with mine but in matrix language, probably it'll become a problem of matrix diagolization

Correct. Some expressions with \sqrt{97} in them are the eigenvalues of the matrix.