Page 1 of 2 12 LastLast
Results 1 to 15 of 23

Math Help - showing a sequence converges

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    14

    showing a sequence converges

    Hey guys,

    I have a function y=(x+2)/(x+1) and I have performed iterations to show that for any initial value other than -sqrt{2} the sequence converges to sqrt{2}.

    So I have found that sqrt{2} is a stable fixed point and -sqrt{2} is an unstable fixed point.

    Now I have to prove my findings using a standard test for convergence?

    Can anyone help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Would I be right in considering that you are setting up an iteration scheme as follows:

    y=f(x)=\frac{x+2}{x+1},

    x_{n+1}=f(x_{n})?

    In this case, can I ask if you've ever heard of the Banach fixed point theorem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    14
    yes that is how I am setting up the scheme, and no I haven't heard of that sorry. The only 'standard' tests we have studied have been things like ratio test, limit theorem test, comparison test, nth term test etc
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Ok, so what have you tried so far?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    14
    Most of them to be honest, but none of them seem to work as I can't let n tend to infinity
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2009
    Posts
    14
    I know that the limits of s_{n+1} and s_n are the same, so I have solved the equation L=\frac{L+10}{L+1} to find the limits to be \pm \sqrt{10}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Ok, let me just think out loud here for a bit. You've got a sequence

    a_{n+1}=\frac{a_{n}+2}{a_{n}+1}.

    If we think of using the ratio test, we're looking at

    L=\lim_{n\to\infty}\left|\frac{a_{n+1}}{a_{n}}\rig  ht|=<br />
\lim_{n\to\infty}\left|\frac{a_{n}+2}{a_{n}+1}\cdo  t\frac{1}{a_{n}}\right|.

    Nothing jumps out. As you said, there's no real way to let n tend to infinity.

    In addition, the sequence is not monotone. I just tried the sequence starting out with the number 1, and the sequence oscillated about \sqrt{2}.

    That gives me one idea: instead of looking at a_{n+1}=\frac{a_{n}+2}{a_{n}+1}, let's look at the sequence a_{n+1}-\sqrt{2}=\frac{a_{n}+2}{a_{n}+1}-\sqrt{2}. If you can prove the sequence is an alternating sequence, then you could use the alternating series test, perhaps.

    Or, here's another idea. Start with a_{0}, and see if you can find a general equation of the nth term.

    We have

    a_{1}=\frac{a_{0}+2}{a_{0}+1},

    a_{2}=\frac{a_{1}+2}{a_{1}+1}=\frac{\frac{a_{0}+2}  {a_{0}+1}+2}{\frac{a_{0}+2}{a_{0}+1}+1}<br />
=\frac{3a_{0}+4}{2a_{0}+3},

    a_{3}=\frac{a_{2}+2}{a_{2}+1}=\frac{\frac{3a_{0}+4  }{2a_{0}+3}+2}{\frac{3a_{0}+4}{2a_{0}+3}+1}=\frac{  7a_{0}+10}{5a_{0}+7},

    a_{4}=\frac{a_{3}+2}{a_{3}+1}=\frac{\frac{7a_{0}+1  0}{5a_{0}+7}+2}{\frac{7a_{0}+10}{5a_{0}+7}+1}=\fra  c{17a_{0}+24}{12a_{0}+17}.

    That's all I have time for right now. What you'd like to do is write the sequence as a function of a_{0} and n, but without any a_{n}'s in it. If you could do that, you could take the limit.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2009
    Posts
    14
    I have just spoken to someone I know, and the easiest way is too show that it is a decreasing sequence bounded below and then it converges to its infimum?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    It has occurred to me that the original iteration scheme is nonlinear, hence impervious to the z-transform technique. However, it may be that the four numbers that show up in each iteration can be resolved by a linear recurrence relation.

    The last step I wrote was

    a_{4}=\frac{17a_{0}+24}{12a_{0}+17}. The next step would be

    a_{5}=\frac{a_{4}+2}{a_{4}+1}=\frac{\frac{17a_{0}+  24}{12a_{0}+17}+2}{\frac{17a_{0}+24}{12a_{0}+17}+1  }=\frac{41a_{0}+58}{29a_{0}+41}.

    So you have, it looks like three numbers (two of the numbers appear always to be identical) to determine for each n. Can you set up a recurrence relation that determines each of those numbers?

    Incidentally, I would agree that often the bounded monotone sequence converges theorem is a nice one to use. However, it does not apply here, because, as I mentioned above, this sequence is not monotone. It oscillates about \sqrt{2}, as it gets closer and closer.

    I should also point out that the computations I have done above show that there is an infinite sequence of numbers that is not in the domain of the iteration scheme: those points where all the denominators of various terms in the sequence are equal to zero.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    So, let's assume the following ansatz:

    a_{n}=\frac{f_{n}a_{0}+g_{n}}{h_{n}a_{0}+f_{n}}.

    Then we have

    <br />
a_{n+1}<br />
=\frac{a_{n}+2}{a_{n}+1}<br />
=\frac{\frac{f_{n}a_{0}+g_{n}}{h_{n}a_{0}+f_{n}}+2  }{\frac{f_{n}a_{0}+g_{n}}{h_{n}a_{0}+f_{n}}+1}<br />
=\frac{\frac{(f_{n}+2h_{n})a_{0}+(g_{n}+2f_{n})}{h  _{n}a_{0}+f_{n}}}{\frac{(f_{n}+h_{n})a_{0}+(g_{n}+  f_{n})}{h_{n}a_{0}+f_{n}}}<br />
=\frac{(f_{n}+2h_{n})a_{0}+(g_{n}+2f_{n})}{(f_{n}+  h_{n})a_{0}+(g_{n}+f_{n})}<br />
.

    But, we also have that

    a_{n+1}=\frac{f_{n+1}a_{0}+g_{n+1}}{h_{n+1}a_{0}+f  _{n+1}}.

    Setting

    \frac{f_{n+1}a_{0}+g_{n+1}}{h_{n+1}a_{0}+f_{n+1}}=  \frac{(f_{n}+2h_{n})a_{0}+(g_{n}+2f_{n})}{(f_{n}+h  _{n})a_{0}+(g_{n}+f_{n})}

    shows us that it must be the case that the following equations hold:

    f_{n+1}=f_{n}+2h_{n}
    g_{n+1}=g_{n}+2f_{n}
    h_{n+1}=f_{n}+h_{n}
    f_{n+1}=g_{n}+f_{n}.

    Two of these must be redundant (if the system is consistent, that is).

    We also have the initial conditions:
    f_{0}=1
    g_{0}=2
    h_{0}=1.

    At this point, I must admit, I handed off the solution to Mathematica (using the RSolve command). I got the following:

    f_{n}=\frac{1}{2}\left((1-\sqrt{2})^{n+1}+(1+\sqrt{2})^{n+1}\right),
    g_{n}=\frac{-(1-\sqrt{2})^{n+1}+(1+\sqrt{2})^{n+1}}{\sqrt{2}}, and
    h_{n}=\frac{-(1-\sqrt{2})^{n+1}+(1+\sqrt{2})^{n+1}}{2\sqrt{2}}.

    The presence of all those \sqrt{2}'s is encouraging, to say the least. If you plug in these values of the coefficients, you obtain the following rather nasty expression:

    a_{n+1}=\frac{2\,{\left( 1 - {\sqrt{2}} \right) }^n\,<br />
     \left( -2 + {\sqrt{2}} + \left( -1 + {\sqrt{2}} \right) \,{a_0} \right)  - <br />
    2\,{\left( 1 + {\sqrt{2}} \right) }^n\,<br />
     \left( 2 + {a_0} + {\sqrt{2}}\,\left( 1 + {a_0} \right)  \right) }{<br />
     {\left( 1 - {\sqrt{2}} \right) }^n\,<br />
     \left( -2\,\left( 1 + {a_0} \right)  + {\sqrt{2}}\,\left( 2 + {a_0} \right)  \right)<br />
        - {\left( 1 + {\sqrt{2}} \right) }^n\,<br />
     \left( 2\,\left( 1 + {a_0} \right)  + {\sqrt{2}}\,\left( 2 + {a_0} \right)  \right) <br />
    }.

    If you want to take the limit of this as n\to\infty, I would notice that essentially you have the following limit:

    \lim_{n\to\infty}\frac{C_{1}(1-\sqrt{2})^{n}+C_{2}(1+\sqrt{2})^{n}}{C_{3}(1-\sqrt{2})^{n}+C_{4}(1+\sqrt{2})^{n}},

    where

    C_{1}=2(-2+\sqrt{2}+(-1+\sqrt{2})a_{0}),
    C_{2}=-2(2+a_{0}+\sqrt{2}(1+a_{0})),
    C_{3}=(-2(1+a_{0})+\sqrt{2}(2+a_{0})),
    C_{4}=-(2(1+a_{0})+\sqrt{2}(2+a_{0})).

    This may seem like an awful lot of work, but I think that you're almost there. I've probably posted more than I should. Can you finish?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Those numbers not in the domain of the iteration scheme are the following:

    x=-\frac{f_{n}}{h_{n}}=<br />
-\left( \frac{{\sqrt{2}}\,\left( {\left( 1 - {\sqrt{2}} \right) }^{1 + n} + {\left( 1 + {\sqrt{2}} \right) }^{1 + n} \right) }<br />
    {-{\left( 1 - {\sqrt{2}} \right) }^{1 + n} + {\left( 1 + {\sqrt{2}} \right) }^{1 + n}} \right), for all n\ge 0.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Mar 2009
    Posts
    14
    I have just been to see my lecturer and he said the only clue he can give is that I should be able to just use this :

    1.16 PROPOSITION. Suppose that (an) is an increasing sequence. Then:
    (i) if (an) is bounded above, then it converges to its supremum;
    (ii) if (an) is not bounded above, then it tends to infinity.
    Similar statements apply to decreasing sequences.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Mar 2009
    Posts
    14
    I can see where you are coming from with your working out but I think its a bit too complex, from what I can tell it should be a fairly simple answer
    Follow Math Help Forum on Facebook and Google+

  14. #14
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I must disagree with your lecturer, then. The proposition he quoted simply does not apply to your sequence, because your sequence is not increasing or decreasing, no matter what initial point you choose. Here's an example:

    Choose some initial value less than \sqrt{2}, say, 1.

    So,

    a_{0}=1,
    a_{1}=1.5,
    a_{2}=1.4,
    a_{3}=1.41\overline{6},
    etc.

    The actual value of \sqrt{2}=1.41421356237...

    Hence, you can see that the sequence oscillates about the limit, and is NOT increasing or decreasing.

    The same thing happens if you were to choose a value larger than the limit.

    In order to use the theorem your lecturer mentioned, your sequence MUST be monotone. Since yours is not, the theorem does not apply.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    The theorem does not apply to the sequence as is. However, if you take the subsequence consisting of every other value, and show that it is monotone, you might be able to get somewhere with that theorem.

    If I skip every other term, then I essentially have an iteration scheme as follows:

    a_{n+1}=\frac{3a_{n}+4}{2a_{n}+3}.

    If you can show that that one is monotone (either increasing or decreasing), then you're in business. So maybe you could show that the evens are increasing (for the numerical example I gave above) and the odds are decreasing (where even and odd apply to the number n).

    But you're still going to have to show that it converges to \sqrt{2}. You'd have to show that \sqrt{2} is the supremum of the increasing subsequence, and the infimum of the decreasing subsequence, in order to make it work.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: July 22nd 2011, 12:16 PM
  2. prove that a sequence converges
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: May 1st 2010, 06:48 PM
  3. Prove this sequence converges
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 6th 2010, 12:18 PM
  4. How to show this sequence converges
    Posted in the Calculus Forum
    Replies: 13
    Last Post: November 3rd 2009, 11:38 AM
  5. How to show this sequence converges
    Posted in the Calculus Forum
    Replies: 6
    Last Post: November 2nd 2009, 11:44 AM

Search Tags


/mathhelpforum @mathhelpforum