# How to prove a recursive formula converges.

1. Jul 7, 2009

### Polarbum

1. The problem statement, all variables and given/known data
Prove that the recursive sequence, a_(n+1) = 2/ [ 1/3 + 1/ (4+ a_n ) ], converges.

2. Relevant equations

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

2. Jul 7, 2009

### HallsofIvy

Staff Emeritus
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 a1 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 a1> -4, then {an} is an increasing sequence and has 5 as an upper bound.

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

3. Jul 7, 2009

### g_edgar

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

4. Jul 7, 2009

### kof9595995

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

5. Jul 7, 2009

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

6. Jul 7, 2009

### kof9595995

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

7. Jul 7, 2009

### cipher42

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)

8. Jul 7, 2009

### kof9595995

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

9. Jul 7, 2009

### Polarbum

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?

10. Jul 8, 2009

### 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}$$
take reciprocals on both sides:
$$\frac{1}{a_{n + 1} + 2} = \frac{1}{3} - \frac{1}{3}\frac{1}{(a_{n} + 2)}$$
then let
$$b_n = \frac{1}{a_{n } + 2}$$
you'll get
$$b_{n + 1} = \frac{1}{3} - \frac{1}{3}b_n$$
this is a linear recursive formula,then you know what to do with it.

Last edited: Jul 8, 2009
11. Jul 8, 2009

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

12. Jul 8, 2009

### g_edgar

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