# Thread: Factorial induction problem

1. ## 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)

Rijsthoofd

2. (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.

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.

4. (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.

5. You've been very helpful
I finished the assignment

Thank you

6. Originally Posted by Rijsthoofd
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)