## Induction Formulation

Hi all, been struggling with my course material regarding Induction. My prof is really not great at explaining this proof method. I don't know what the learning curve or expectations here are like but I'm really struggling with this conceptually.

Any assistance with these problems would be much appreciated:

1. Prove that 3 divides n^3+2n whenever n is a positive integer.
I know I can't use a summation progression so how do I solve this induction?
(n+1)^3+2(n+1) is the next step but I get lost when I try to factor out the (n+1)^3
This is as far as I can take this one.

2. Prove that 1x1! + 2x2! + ... + nxn! = (n+1)!-1
Let P(n) be 1x1!+…+nxn!=(n+1)!-1
Basis Step: 1 x 1! = (1+1)!+1
1 = 1
Therefore our basis step is true.
Inductive Step: We know that P(n) is true thus we must prove P(n+1)
1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!)
1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1]+((n+1)(n+1)!)
1x1!+…+nxn!+((n+1)(n+1)!)= ((n+1)(n+1)!)

I believe this one is solved however I'm not sure if I must take it further?

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target
 Recognitions: Science Advisor Well, line 1 is correct: 1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!) And then it's correct to notice that P(n) tells us that the expression in square brackets can be replaced by [(n+1)!-1]. But in your line 2, you also change ((n+1)(n+1)!) to ((n+1)+1)!-1, which is wrong. Perhaps this is a typo?

Recognitions:
Gold Member
Staff Emeritus
 Quote by gcarson1 Hi all, been struggling with my course material regarding Induction. My prof is really not great at explaining this proof method. I don't know what the learning curve or expectations here are like but I'm really struggling with this conceptually. Any assistance with these problems would be much appreciated: 1. Prove that 3 divides n^3+2n whenever n is a positive integer. I know I can't use a summation progression so how do I solve this induction? (n+1)^3+2(n+1) is the next step but I get lost when I try to factor out the (n+1)^3 This is as far as I can take this one.
You can't factor out (n+1)^3, it's not a factor! n+1, however is: you have (n+1)((n+1)^2+ 2). By the way, what do you plan to do with that? Specifically, you are assuming that n^3+ 2n is divisible by 3 for some n and want to prove that (n+1)^3+ 2(n+1) is also divisible by 3. What does "divisible by 3" mean in terms of a formula?

 2. Prove that 1x1! + 2x2! + ... + nxn! = (n+1)!-1 Let P(n) be 1x1!+…+nxn!=(n+1)!-1 Basis Step: 1 x 1! = (1+1)!+1 1 = 1 Therefore our basis step is true. Inductive Step: We know that P(n) is true thus we must prove P(n+1) 1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!) 1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1]+((n+1)+1)!-1
How did you get that? certainly, by the "induction hypothesis", that P(n) is true, you know that the sum of all except the last term is [(n+1)!-1] but the part you are adding on is (n+1)(n+1)!, not ((n+1)+1)!- 1)

 1x1!+…+nxn!+((n+1)(n+1)!)= ((n+1)+1)!-1 I believe this one is solved however I'm not sure if I must take it further?

## Induction Formulation

 Quote by Avodyne Well, line 1 is correct: 1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!) And then it's correct to notice that P(n) tells us that the expression in square brackets can be replaced by [(n+1)!-1]. But in your line 2, you also change ((n+1)(n+1)!) to ((n+1)+1)!-1, which is wrong. Perhaps this is a typo?
Yes thankyou, I was copying and pasting and missed that line. Thankyou still for pointing that out. I'm still confused that, as all I have done than is repeat the line in the geometric progression on the right side of the equation.

Ex. 1x1!+…+nxn!+((n+1)(n+1)!)= ((n+1)(n+1)!) the right side does not equal the left side in fact when considering n=2 and n+1=3 BUT [(n+1)!-1]+((n+1)(n+1)!) which can be found in line 2 does equal the left side of the equation. So why am I supposed to remove? Is it because the point is to show the progression and not solve the problem?

 Quote by HallsofIvy You can't factor out (n+1)^3, it's not a factor! n+1, however is: you have (n+1)((n+1)^2+ 2). By the way, what do you plan to do with that? Specifically, you are assuming that n^3+ 2n is divisible by 3 for some n and want to prove that (n+1)^3+ 2(n+1) is also divisible by 3. What does "divisible by 3" mean in terms of a formula?
Well it implies that 3 divides the equation so I'm thinking maybe I need to apply modular arithmetic but it doesn't fit the division algorithim formula so.. I'm back to proving using sums of a geometric progressions. So in response to what divisible by 4 means, it implies that when divided by 3, the formula (n+1)^3+ 2(n+1) should be reduced to a single positive integer. I think I understand the logic, but I don't know how to prove it.

 Recognitions: Homework Help Science Advisor You've assumed n^3+2n is divisible by three. You want to prove (n+1)^3+2(n+1) is divisible by three. What the difference ((n+1)^3+2(n+1))-(n^3+2n)? Expand it out.

Recognitions:
 Quote by gcarson1 I'm still confused that, as all I have done than is repeat the line in the geometric progression on the right side of the equation.
That's what you're trying to prove; you can't use it. Your edited line 2 is now correct:

1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1] + ((n+1)(n+1)!)

But your line 3 is wrong; you seem to have just dropped the bracketed term entirely.

What you want to do with line 2 is to show that the right-hand side equals (n+2)!-1. You must do this just with ordinary algebraic manipulations, not by using P(n). Can you see how to do this? Can you see why this what you should do?

 Quote by Avodyne That's what you're trying to prove; you can't use it. Your edited line 2 is now correct: 1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1] + ((n+1)(n+1)!) But your line 3 is wrong; you seem to have just dropped the bracketed term entirely. What you want to do with line 2 is to show that the right-hand side equals (n+2)!-1. You must do this just with ordinary algebraic manipulations, not by using P(n). Can you see how to do this? Can you see why this what you should do?

line 1 1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!)
line 2 1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1]+((n+1)(n+1)!)
line 3 1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1]+((n+1)(n+1)!)
So the next line should be
line 4 1x1!+…+nxn!+((n+1)(n+1)!)=(n+2)!-1

I see logically why that makes sense, as it is the formula for the original statement, so n+1 should become n+2 when it is considering the next term. But as to your statement, no, I don't see how to get from line 3 to line4 .

Recognitions:
 Quote by gcarson1 I see logically why that makes sense, as it is the formula for the original statement, so n+1 should become n+2 when it is considering the next term.
Yes, but again that is what you are trying to prove, so you can't use it.

The right-hand side of line 3 is [(n+1)!-1]+((n+1)(n+1)!). Let A=(n+1)!. Then the right-hand side is [A-1]+(n+1)A = A-1+nA+A=(n+2)A-1. Now replace A with (n+1)!, and notice that (n+2)(n+1)!=(n+2)!.

You're done! (Using A wasn't really necessary, I just thought it would make it clearer how things should be grouped.)

So, it was just some algebra that you needed to do (though a little tricky in this case). Can you do the other problem now?

 Quote by Avodyne Yes, but again that is what you are trying to prove, so you can't use it. The right-hand side of line 3 is [(n+1)!-1]+((n+1)(n+1)!). Let A=(n+1)!. Then the right-hand side is [A-1]+(n+1)A = A-1+nA+A=(n+2)A-1. Now replace A with (n+1)!, and notice that (n+2)(n+1)!=(n+2)!. You're done! (Using A wasn't really necessary, I just thought it would make it clearer how things should be grouped.) So, it was just some algebra that you needed to do (though a little tricky in this case). Can you do the other problem now?
A yes!!! Brilliant, the A made things so much clearer, I resolved the other problem in class today while reading this, thankyou very much!