Results 1 to 10 of 10

Math Help - Infinite sequence (recursive)

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    151

    Infinite sequence (recursive)

    Let x_0 and k be positive real numbers.
    <br />
x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1<br />

    Now prove that either of the sequences x_1 , x_3, x_5 \dotsb or x_2 , x_4 , x_6 , \dotsb is increasing and the other one is decreasing.

    Then prove that x_1 , x_2 , \dotsb x_n is convergant.

    I have no idea how to work with recursive sequences, so if someone could tell me how do I start?
    Last edited by hjortur; September 20th 2009 at 12:02 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2
    Quote Originally Posted by hjortur View Post
    Let x_0 and k be positive real numbers.
    <br />
x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq0<br />

    Now prove that either of the sequences x_1 , x_3, x_5 \dotsb or x_2 , x_4 , x_6 , \dotsb is increasing and the other one is decreasing.

    Then prove that x_1 , x_2 , \dotsb x_n is convergant.

    I have no idea how to work with recursive sequences, so if someone could tell me how do I start?
    Do we know that x_{-1}>0?, otherwise there may occur some problems...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    151
    I fixed typo in original post. Now it is no problem like you said.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2
    Quote Originally Posted by hjortur View Post
    Let x_0 and k be positive real numbers.
    <br />
x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1<br />

    Now prove that either of the sequences x_1 , x_3, x_5 \dotsb or x_2 , x_4 , x_6 , \dotsb is increasing and the other one is decreasing.

    Then prove that x_1 , x_2 , \dotsb x_n is convergant.

    I have no idea how to work with recursive sequences, so if someone could tell me how do I start?
    I am not very sure, since I am also new to rational difference equations. But the clue must be hidden in defining f(x):=\frac{(1+x)k}{1+k+x}>0 for x>0. Then, f^{\prime}>0>f^{\prime\prime}. Moreover, we have x(n)=f\big(x(n-2)\big) for n\geq2. Also note that the equilibrium of the given equation is x=\frac{1}{2}\big(-1+\sqrt{1+4k}\big).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2009
    Posts
    151
    Hmmm...

    If you define
    <br />
f(x):=\frac{(1+x)k}{1+k+x}>0<br />

    and then define:

    <br />
g(x):=\frac{k}{1+f(x)}=\frac{k+kx+k^2}{1+2k+x+kx}<br />

    then g'(x)<0

    Then say something along the line that f(x) gives every other (e.g. even) numbers and g(x), the others. Now the derivative of g(x) is negative so that sequence is decreasing, and f(x) is positive so it is increasing?

    I dont know, still doesnt help to prove that the whole sequence is convergant.

    What does it mean when you say:
    Also note that the equilibrium of the given equation is x=\frac{1}{2}\big(-1+\sqrt{1+4k}\big).
    Lets assume the limit excists, call it L. Now:
    <br />
x_n = \frac{k}{1+x_{n-1}}<br />
    <br />
L = \frac{k}{1+L}<br />

    So the limit is the positive solution to L^2 +L =k
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Wink Proof of the second part

    Quote Originally Posted by hjortur View Post
    Let x_0 and k be positive real numbers.
    <br />
x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1<br />

    Now prove that either of the sequences x_1 , x_3, x_5 \dotsb or x_2 , x_4 , x_6 , \dotsb is increasing and the other one is decreasing.

    Then prove that x_1 , x_2 , \dotsb x_n is convergant.

    I have no idea how to work with recursive sequences, so if someone could tell me how do I start?
    I will give a proof for the highlighted part, because I don't have any idea how to prove the first part yet, but I will write if I can find.
    Using the recursion formula
    x(n)=\frac{k}{1+x(n-1)}....for n\geq1,....(1)
    where x(0)>0 and k>0, we learn that
    x(n)<k....for all n\geq1, i.e., \{x(n)\}_{n\in\mathbb{N}_{0}} is bounded.
    Set
    \ell_{*}:=\liminf_{n\to\infty}x(n)....and.... \ell^{*}:=\limsup_{n\to\infty}x(n).
    Clearly,
    0\leq\ell_{*}\leq\ell^{*}\leq k.....(2)
    Taking now inferior and superior limits on both sides of (1), we obtain
    \ell_{*}\geq\frac{k}{1+\ell^{*}}....and.... \ell^{*}\leq\frac{k}{1+\ell_{*}} (actually they are equal, but I prefer inequalities for a general proof),
    which yields
    \ell_{*}(1+\ell^{*})\geq k\geq\ell^{*}(1+\ell_{*}),
    or equivalently
    \frac{\ell_{*}}{1+\ell_{*}}\geq\frac{\ell^{*}}{1+\  ell^{*}}.....(3)
    Set \nu(\lambda):=\lambda/(1+\lambda) for \lambda>0, and note that \nu is increasing on [0,\infty).
    From (3), we have
    \nu(\ell_{*})\geq\nu(\ell^{*}),
    which yields
    \ell_{*}\geq\ell^{*}.....(4)
    It follows from (2) and (4) that \ell_{*}=\ell^{*}, i.e., \{x(n)\}_{n\in\mathbb{N}_{0}} has a finite limit at infinity (more precisely this limit value lies in the interval [0,k]).
    Let
    \ell:=\lim_{n\to\infty}x(n).
    Taking limit on both sides of (1), we obtain
    \ell=\frac{k}{1+\ell},....(5)
    and solving this we obtain
    \ell:=\frac{1}{2}\big(-1+\sqrt{1+4k}\big) (note that we took the positive solution of (5) since the solutions we consider are positive),
    which is called the equilibrium of the recursive equation (1).
    Every solution of (1) with positive initial value and positive k, tends to the equilibrium \ell.

    You should refer to the following books for rational difference equations:
    [1] M. R. S. Kulenovic and G. Ladas, Dynamics of Second Order Rational Difference Equations with Open Problems and Conjectures, Champman & Hall, 2002.
    [2] E. Camouzis and G. Ladas, Dynamics of Third-Order Rational Difference Equations with Open Problems and Conjectures, Champman & Hall, 2008.


    Mathematica codes for plotting a graphic of the solution of the rational sequence
    Code:
    s=30; "Number of iterations";
    x=Table[0,{i,1,s+1}];
    k=1; "Coefficient";
    x[[1]]=1; "Initial Value";
    For[i=1,i<=s,i++,x[[i+1]]=k/(1+x[[i]])]
    eq=l/.Solve[l==k/(1+l),{l}];
    eq=If[eq[[1]]>0,eq[[1]],eq[[2]]];
    xtab=Table[{i,x[[i+1]]},{i,0,s}];
    Show[ListPlot[xtab,PlotStyle->{Red,PointSize[0.02],Opacity[1]},PlotRange->Full,AxesOrigin->{0,0}],ListPlot[xtab,PlotStyle->{Blue,Dashed,Thickness[0.001],Opacity[1]},Joined->True],Plot[eq,{i,0,s},PlotStyle->{Green,Thickness[0.001]}]]
    Last edited by bkarpuz; September 21st 2009 at 06:48 AM. Reason: Mathematica codes are included
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Cool Proof for the first part

    Quote Originally Posted by hjortur View Post
    Let x_0 and k be positive real numbers.
    <br />
x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1<br />

    Now prove that either of the sequences x_1 , x_3, x_5 \dotsb or x_2 , x_4 , x_6 , \dotsb is increasing and the other one is decreasing.

    Then prove that x_1 , x_2 , \dotsb x_n is convergant.

    I have no idea how to work with recursive sequences, so if someone could tell me how do I start?
    I will show you the proof only for the case where either \{x(2k+1)\}_{k\in\mathbb{N}} or \{x(2k)\}_{\in\mathbb{N}} is decreasing by leaving some open problems.

    From the second part of the proof, we now know that every solution of the rational difference equation
    x(n)=\frac{k}{1+x(n-1)}....for n\in\mathbb{N}....(1)
    converges to the equilibrium point of the equation \ell:=\big(-1\sqrt{1+4k}\big)/2.
    Now define g(u):=k/(1+u) and f(u):=(g\circ g)(u)=k(1+u)/(1+k+u) for u\geq0.
    It is clear that g>0>g^{\prime} on [0,\infty) and \ell is the only positive fixed point of g the equation, i.e., u=\ell is the only solution of g(u)=u for u\geq0.
    Moreover,
    f,f^{\prime}>0>f^{\prime\prime} on [0,\infty)....(2)
    and \ell is the only positive fixed point of f too.
    From (2), we see that
    f(u)\geq f(\ell)=\ell for all u\geq\ell.....(3)

    Open Problem 1. Prove that f(u)\leq u for all u\in[\ell,\infty).
    Note. For this open problem, Mathematica 7.0 returns empty set when trying to find some u\geq\ell such that f(u)>u.
    Below you will find the code, but you have to prove it yourself.
    Code:
    f[u_,k_]=(k(1+u))/(1+k+u);
    l[k_]=l/.Solve[l ==k/(1+l),{l}][[2]];
    FindInstance[f[u,k]>u&&k>0&&u>l[k],{u,k}]

    I assume that the proof for the open problem is given and continue the proof for the original problem.
    Hence, (3) can be rewritten as
    u\geq f(u)\geq f(\ell)=\ell for all u\geq\ell,....(4)
    Rewrite now (1) as
    x(n)=f\big(x(n-2)\big)....for n\geq2.....(5)
    If x(n)\geq\ell for some n\in\mathbb{N}, then from (4) and (5), we have
    x(n)\geq f\big(x(n)\big)=x(n+2)\geq f(\ell)=\ell.....(6)
    This proves that if a term is above the equilibrium then succeeding second term is not greater than this term and not less than the equilibrium point.
    By mathematical induction, we can say that if x(0)>\ell, then \{x(2n)\}_{n\in\mathbb{N}_{0}} decreases to \ell, and if x(1)>\ell, then \{x(2n+1)\}_{n\in\mathbb{N}_{0}} decreases to \ell also.

    You can show by using very similar arguments that the subsequences increase to the equilibrium provided that their initial values are not greater than the equilibrium.
    In this case you need to prove the following problem.

    Open Problem 2. Prove that f(u)\geq u for all u\in[0,\ell].
    Again see the solution by Mathematica 7.0.
    Code:
    f[u_,k_]=(k(1+u))/(1+k+u);
    l[k_]=l/.Solve[l ==k/(1+l),{l}][[2]];
    FindInstance[f[u,k]<u&&k>0&&u<l[k]&&u>0,{u,k}]

    Please let me know when you have proofs for the open problems.
    Last edited by bkarpuz; September 21st 2009 at 09:21 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2009
    Posts
    151
    Wow, thank you bkarpuz. But I am pretty sure your solution is much to complicated. Most of what you are talking about, I have never even heard of. This was supposed to be an easy excercise at the end of the chapter on sequences.

    But thank you very much, for taking your time to answer my question.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Wink

    Quote Originally Posted by hjortur View Post
    Wow, thank you bkarpuz. But I am pretty sure your solution is much to complicated. Most of what you are talking about, I have never even heard of. This was supposed to be an easy excercise at the end of the chapter on sequences.

    But thank you very much, for taking your time to answer my question.
    I don't believe Please let me know which book is it!
    Also please let me know if you find a simple solution.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Sep 2009
    Posts
    151
    It is an Icelandic textbook written by my teacher, so you will probably never find it.
    Because we have a different system here in Iceland, it is hard to say what course my course corresponds to.
    But I think it is somewhere along the lines of Calculus I and Mathematical analysis I. (First year, BSc (in mathematics) student).

    But I will tell you when I find a simple solution.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursive Sequence Convergence
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 5th 2010, 02:24 PM
  2. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  3. recursive sequence
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 29th 2009, 05:15 AM
  4. recursive sequence
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 14th 2009, 06:33 AM
  5. recursive sequence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 5th 2008, 11:21 PM

Search Tags


/mathhelpforum @mathhelpforum