Page 1 of 2 12 LastLast
Results 1 to 15 of 16
Like Tree9Thanks

Math Help - proof by induction

  1. #1
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    94
    Thanks
    15

    proof by induction

    sorry, not sure which subforum this should go to.

    Sequence u1, u2, u3,... is know to converge to the limit m and is such that u_{n+1}=\frac{9u_n+3}{u_n+7}

    a) find the value of m.
    b) it is given that  u_n=1. by first writing u_n in terms of u_{n+1}, and considering 3-u_n, prove by induction that u_n<3 for all positive integers n.

    for a.

    i substitute m, giving m=\frac{9m+3}{m+7}
    solving this gives m=-1,3
    how do i immediately know whether it is -1 or 3 that it converges to? i know i can draw a graph of u_{n+1} against u_n, and draw a line of y=x, and based on the gradient of the curve determine which it converges to. but i believe im not supposed to do that, this topic is only induction. and also this is a short question which probably carries very little marks. there must be some direct and quick way to immediately see which it converges to?

    for b.
    i proved that it is valid for n=1.
    i assumed that it is valid for n=k.
    that gives u_k<3
    expressing u_n in terms of u_{n+1}, u_n=-\frac{7u_{n+1}-3}{u_{n+1}-9}
    considering 3-u_n,
    3-u_n=\frac{10u_{n+1}-30}{u_{n+1}-9}
    since it is assumed u_k<3,
    then \frac{10u_{n+1}-30}{u_{n+1}-9}>0
    this is where my problem starts. i can't show from here that u_{n+1}<3
    how? in fact what i get is u_{n+1}<3,u_{n+1}>9. theres this u_{n+1}>9, which shouldn't be if i were to prove this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,454
    Thanks
    944

    Re: proof by induction

    You are aware of how this behaves?

    $u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

    $u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$

    Proving the first statement by induction should be pretty trivial.

    You seem to know enough of what's going on to take a stab at proving the second statement.
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2014
    From
    Poland
    Posts
    40
    Thanks
    7

    Re: proof by induction

    Consider monotonicity. It may help to waste u_{n+1}>0
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    94
    Thanks
    15

    Re: proof by induction

    Quote Originally Posted by romsek View Post
    You are aware of how this behaves?

    $u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

    $u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$
    no. what do you refer to by u_0?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,454
    Thanks
    944

    Re: proof by induction

    Quote Originally Posted by muddywaters View Post
    no. what do you refer to by u_0?
    I guess you call it $u_1$, just the first element of the sequence. It's defined recursively so you can assign anything to the initial value.
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    94
    Thanks
    15

    Re: proof by induction

    Quote Originally Posted by romsek View Post
    I guess you call it $u_1$, just the first element of the sequence. It's defined recursively so you can assign anything to the initial value.
    oh k. now i understand what
    $u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

    $u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$
    says, but how do you know that it's like that?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2014
    From
    Poland
    Posts
    40
    Thanks
    7

    Re: proof by induction

    From equation for m and monotonicity of u_{n}
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    94
    Thanks
    15

    Re: proof by induction

    Quote Originally Posted by Cartesius24 View Post
    From equation for m and monotonicity of u_{n}
    how do u find out the monotonicity of u_n? Differentiate? With respect to what? And how will it tell me where is converges to?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    126
    Thanks
    56

    Re: proof by induction

    Quote Originally Posted by muddywaters View Post
    how do u find out the monotonicity of u_n? Differentiate? With respect to what? And how will it tell me where is converges to?
    This might help

    u_{n+1}-u_n=\frac{9u_n+3}{u_n+7}-u_n=\frac{\left(3-u_n\right)\left(u_n+1\right)}{u_n+7}
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    126
    Thanks
    56

    Re: proof by induction

    Quote Originally Posted by romsek View Post
    You are aware of how this behaves?

    $u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

    $u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$

    Proving the first statement by induction should be pretty trivial.

    You seem to know enough of what's going on to take a stab at proving the second statement.
    the second statement is not true

    for u_0=-3.25 the sequence does not converge
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    94
    Thanks
    15

    Re: proof by induction

    Quote Originally Posted by Idea View Post
    This might help

    u_{n+1}-u_n=\frac{9u_n+3}{u_n+7}-u_n=\frac{\left(3-u_n\right)\left(u_n+1\right)}{u_n+7}
    Sorry, i still cant tell if it converges to 3 or -1 from that.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    126
    Thanks
    56

    Re: proof by induction

    Quote Originally Posted by muddywaters View Post
    Sorry, i still cant tell if it converges to 3 or -1 from that.
    no you can't tell convergence from this

    But I was hoping it would help you in showing monotonicity
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Mar 2012
    From
    malaysia
    Posts
    94
    Thanks
    15

    Re: proof by induction

    Quote Originally Posted by Idea View Post
    no you can't tell convergence from this

    But I was hoping it would help you in showing monotonicity
    How to show monotonicity???
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    126
    Thanks
    56

    Re: proof by induction

    I will do this in the case where the first term in the sequence is between -1/3 and 3

    -1/3<u_1<3 \Rightarrow 0<u_n<3\text{  }(n\geq  2)

    Proof is by induction using the following

    3-u_{n+1}=\left(3-u_n\right)\frac{6}{u_n+7}


    Next use

    u_{n+1}-u_n=\frac{\left(3-u_n\right)\left(u_n+1\right)}{u_n+7}

    to show that the sequence is monotone increasing and since it is bounded above, it converges (to 3)
    Last edited by Idea; August 16th 2014 at 10:43 PM.
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466

    Re: proof by induction

    Quote Originally Posted by muddywaters View Post
    Sorry, i still cant tell if it converges to 3 or -1 from that.
    Yes, that's the point every one has been trying to make. Just this equation can't tell you what it converges to. You need to know some starting value also.
    Thanks from muddywaters
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 12th 2010, 04:01 AM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  3. Induction Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 7th 2009, 10:50 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. induction proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 21st 2008, 12:48 AM

Search Tags


/mathhelpforum @mathhelpforum