Results 1 to 6 of 6

Math Help - Factorial induction problem

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    3

    Factorial induction problem

    Hello,

    I'm studying Discrete mathematics and am stuck at a particular point in an assisgnment where i have to use mathematical induction to prove that

    every n > 0 is true

    the assignment is:

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

    so we enter P(o) which comes out 0.

    This implies that P(o) --> P(n+1)

    so we have an induction hypothesis and we want to prove:

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

    simplify and replace the summation with the original data:

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

    so this is where I'm stuck because I don't know how to simplify the LHS to be equal to the right handside because the math includes factorial terms which I have never used before.

    (The anwser is not at the back of the book)

    Thanks in advance,

    Rijsthoofd
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    (n+1)! - 1 + (n+1) . (n+1)! = (n+2)! - 1
    Factor out (n + 1)! on the left. The LHS then is (n + 1)!(1 + n + 1) - 1 = (n + 1)!(n+2) - 1. Now recall the definition of (n + 2)!.

    the assignment is:

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

    so we enter P(o) which comes out 0.
    What do you mean "so we enter P(0)"? What is P and what is P(0)?

    I am asking this not because proofs by induction usually don't contain some "P(0)" but because your proof should be a valid mathematical text, which introduces all concepts it uses.

    This implies that P(o) --> P(n+1)
    This is not clear at all. What is n? The base case is just P(0).

    (One of many) right way(s) to start the proof is like this. Let P(n), for each fixed n, be a proposition 1! + 2 . 2! + ... + n . n! = (n+1)! - 1. We need to show "For all n, P(n)", by induction on n.

    Note that P(n) is, for each particular n, a proposition; therefore, it is wrong to write P(n) = 0 or P(n) = 5 or P(n) + (n + 1).(n + 1)! = ... and so on. P(n) can be either true of false; that's all.

    The base case is P(0), which is 0 . 0! = (0 + 1)! - 1. This is true.

    For the induction step, one needs to prove "For all n, P(n) implies P(n + 1)". So, fix n and assume P(n); this is induction hypothesis (IH). The rest of the proof you did more or less right.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    3
    Factor out (n + 1)! on the left. The LHS then is (n + 1)!(1 + n + 1) - 1 = (n + 1)!(n+2) - 1. Now recall the definition of (n + 2)!.
    When I factor out (n+1)! I get:

    (n+1)!(n+1)-1

    I don't understand where you get the extra +1 to make it:

    (n+1)!(n+1+1)-1

    What do you mean "so we enter P(0)"? What is P and what is P(0)?

    I am asking this not because proofs by induction usually don't contain some "P(0)" but because your proof should be a valid mathematical text, which introduces all concepts it uses.
    You're right. As you explained in the last paragraph, the P(0) is used for the base case. I don't know how to convey these things in English properly as my study is done in Holland.

    The thing I don't understand is why there is an extra +1 after factorizing. It does prove the hypothesis if there is an extra +1 but I dont see where it comes from.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    (n+1)! - 1 + (n+1) . (n+1)!
    You have two occurrences of (n + 1)!. One is multiplied by (n + 1), the other by nothing, i.e., 1. Therefore, when you factor out (n + 1)!, what left is (n + 1) + 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2010
    Posts
    3
    You've been very helpful
    I finished the assignment

    Thank you
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Rijsthoofd View Post
    Hello,

    I'm studying Discrete mathematics and am stuck at a particular point in an assisgnment where i have to use mathematical induction to prove that

    every n > 0 is true

    the assignment is:

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

    so we enter P(o) which comes out 0.

    This implies that P(o) --> P(n+1)


    The base case is 1.1!=(1+1)!-1, as the first n (or k) is 1

    so we have an induction hypothesis and we want to prove:

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

    simplify and replace the summation with the original data:

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

    (n+1)!(1)+(n+1)!(n+1)=(n+1)!(n+1+1)=(n+1)!(n+2)

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



    so this is where I'm stuck because I don't know how to simplify the LHS to be equal to the right handside because the math includes factorial terms which I have never used before.

    (The anwser is not at the back of the book)

    Thanks in advance,

    Rijsthoofd
    P(K)

    1.1!+2.2!+....n.n!=(n+1)!-1

    P(k+1)

    1.1!+2.2!+....n.n!+(n+1)(n+1)!=(n+1+1)!-1 utilising P(k)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Factorial Problem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: August 19th 2011, 05:49 AM
  2. Factorial Problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: February 23rd 2010, 02:18 PM
  3. factorial problem.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 12th 2009, 08:57 AM
  4. induction factorial
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: June 10th 2008, 11:04 AM
  5. Factorial problem! Help!
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 24th 2008, 10:19 PM

Search Tags


/mathhelpforum @mathhelpforum