Results 1 to 9 of 9

Math Help - Proof by induction

  1. #1
    LHS
    LHS is offline
    Member
    Joined
    Feb 2009
    From
    Oxford
    Posts
    84

    Exclamation Proof by induction



    I know roughly what has to be done here, but for some reason its not working out like the other questions, any help would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,004
    Thanks
    1660
    T_n= \frac{1}{2}+ \frac{2}{3}+ \cdot\cdot\cdot+ \frac{n}{n+1}
    and you want to show that T_n< n.

    Okay, if n= 1, T_n= \frac{1}{2}< 1.

    Now suppose that, for some k, T_k< k. Now T_{k+1}= T_k+ \frac{k+1}{k+2}< k+ \frac{k+1}{k+2}. And you want to show that that is less than k+1.

    Looks to me that you just need to show that \frac{k+1}{k+2}< 1!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    LHS
    LHS is offline
    Member
    Joined
    Feb 2009
    From
    Oxford
    Posts
    84
    Ah I see, yes, it was at that stage I got confused.
    I thought to prove it you would have to rearrange the RHS to show that the summation + the next term < k+1
    Why do you need to show that (k+1)/(k+2) is less than one?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jul 2009
    Posts
    152
    Here is the "rearrangement" version you wanted:

    T_{k+1}=T_k+\frac{k+1}{k+2}<k+\frac{k+1}{k+2}

    =\frac{k^2+3k+1}{k+2}=\frac{(k+2)(k+1)}{k+2}=k+1

    and you are done.

    HallsofIvy's point was somewhat more elegant.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote Originally Posted by AlephZero View Post

    =\frac{k^2+3k+1}{k+2}=\frac{(k+2)(k+1)}{k+2}=k+1
    you made a mistake

    k^2+3k+1=(k+2)(k+1)

    which is not true.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2009
    Posts
    152
    Whoops, forgot to type a step. Here's the "rearrangment" proof:

    T_{k+1}=T_k+\frac{k+1}{k+2}<k+\frac{k+1}{k+2}

    =\frac{k^2+3k+1}{k+2}<\frac{k^2+3k+2}{k+2}=\frac{(  k+2)(k+1)}{k+2}=k+1.

    Thanks for pointing that out, malaygoel.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jan 2009
    Posts
    715
     T_n = \frac{1}{2} + \frac{2}{3} + ... + \frac{n}{n+1}

     = 1 - \frac{1}{2} + 1 - \frac{1}{3} + 1 - ... + 1 \frac{1}{n+1}

     = 1+1+1+1 +...  - \frac{1}{2} - \frac{1}{3} - ... - \frac{1}{n+1}

     = n - \sum_{k=2}^{n+1} \frac{1}{k} < n

    for  n \geq 1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    LHS
    LHS is offline
    Member
    Joined
    Feb 2009
    From
    Oxford
    Posts
    84
    I think I see why that fraction has to be less than one. That right hand side should be k+1, or whenever you add the next term to the LHS you only add one to the RHS? So that fraction we gained from the LHS has to be less than 1 for the RHS to still be greater?
    Thanks guys for your help!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,678
    Thanks
    1500
    \frac{k + 1}{k + 2} = \frac{k + 2 - 1}{k + 2}

     = 1 - \frac{1}{k + 2} < 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum