Results 1 to 5 of 5

Math Help - Inductive Hypothesis

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    93

    Inductive Hypothesis

    When doing problems that tends to these 3 steps: Basis Step, Inductive Hypothesis and proving the Inductive Step, I am having difficuly understanding the Inductive Hypotheses. How do you know what to assume for the Hypothesis? This is what I have.

    Q: Prove that 1 1! + 2 2! + n n! = (n + 1)! 1 whenever n is a positive integer?

    I have this:
    Basis step:
    Let n = 1
    n n! = (n + 1)! 1
    1 1! = (1 + 1)! 1
    1 1 = (2)! 1
    1 = 1
    Since they both equal, the basis step holds.
    Inductive Hypothesis:
    1 1! + 2 2! + (k + 1) (k + 1)! = ((k + 1) + 1)! 1

    Would I add a (k + 2)! to both the LHS and RHS?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2009
    Posts
    36
    it is very simple!!!!!!!!!

    1.1!+2.2!+............+k.k!+(k+1).(k+1)!={(k+1)!-1}+(k+1).(k+1)!

    =(k+1)!.(k+2)-1

    =(k+2)!-1

    hence the proof
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Grillakis View Post
    When doing problems that tends to these 3 steps: Basis Step, Inductive Hypothesis and proving the Inductive Step, I am having difficuly understanding the Inductive Hypotheses. How do you know what to assume for the Hypothesis? This is what I have.

    Q: Prove that 1 1! + 2 2! + n n! = (n + 1)! 1 whenever n is a positive integer?

    I have this:
    Basis step:
    Let n = 1
    n n! = (n + 1)! 1
    1 1! = (1 + 1)! 1
    1 1 = (2)! 1
    1 = 1
    Since they both equal, the basis step holds.
    Inductive Hypothesis:
    1 1! + 2 2! + (k + 1) (k + 1)! = ((k + 1) + 1)! 1 Mr F says: No. This is NOT the inductive hypothesis required in Step 2. The inductive hypothesis is 1 1! + 2 2! + kk! = (k + 1)! 1

    Would I add a (k + 2)! to both the LHS and RHS?
    Step 3: Show that it follows from step 2 that 1 1! + 2 2! + (k + 1) (k + 1)! = ((k + 1) + 1)! 1.

    1 1! + 2 2! + k k! + (k + 1) (k + 1)! = (k + 1)! - 1 + (k + 1) (k + 1)! = (k + 1)! [1 + (k + 1)] - 1 = (k + 1)! [(k + 1) + 1] - 1 = ((k + 1) + 1)! 1

    and the job is almost done. Now you dot the i's and cross the t's by making the final statement about having proved the result.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,389
    Thanks
    1324
    Quote Originally Posted by Grillakis View Post
    When doing problems that tends to these 3 steps: Basis Step, Inductive Hypothesis and proving the Inductive Step, I am having difficuly understanding the Inductive Hypotheses. How do you know what to assume for the Hypothesis? This is what I have.
    The "inductive hypothesis" is simply that whatever your theorem is, it is true for some specific number, k, say. Notice that the theorem says that it is true for ALL numbers while the inductive hypothesis is only that it is true for SOME number.

    Q: Prove that 1 1! + 2 2! + n n! = (n + 1)! 1 whenever n is a positive integer?

    I have this:
    Basis step:
    Let n = 1
    n n! = (n + 1)! 1
    1 1! = (1 + 1)! 1
    1 1 = (2)! 1
    1 = 1
    Since they both equal, the basis step holds.
    Inductive Hypothesis:
    1 1! + 2 2! + (k + 1) (k + 1)! = ((k + 1) + 1)! 1
    It would be better to write just exactly what your equation is with "k" rather than "n": 1 1! + 2 2! + k k! = (k + 1)! 1

    Would I add a (k + 2)! to both the LHS and RHS?
    No. You write the left hand side of the original equation, 1 1! + 2 2! + n n!, with k+1 rather than k- which means you would add (k+1)(k+1)! to both sides:
    1 1!+ 2 2!+ + kk!+ (k+1)(k+1)!= (k+1)!- 1+ (k+1)(k+1)!
    You want to make the right side look like ((k+1)+ 1)!- 1. I suggest that you factor (k+1)! out of two parts of you previous equation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2009
    Posts
    93
    I understand now...thanks guys
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Null Hypothesis, Alternative hypothesis, Critical Region..
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: August 8th 2011, 10:46 PM
  2. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 01:09 PM
  3. Inductive Hypothesis help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 12th 2008, 08:06 AM
  4. inductive
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2008, 12:08 PM
  5. Inductive Hypothesis
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 16th 2007, 07:29 AM

Search Tags


/mathhelpforum @mathhelpforum