Mastering Induction: Proving Divisibility and Factorial Equations

[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.

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?

 

[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?

 

[HallsofIvy]

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?

 

[gcarson1]

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?

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.

 

[Dick]

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.

 

[Avodyne]

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?

 

[gcarson1]

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 .

 

[Avodyne]

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?

 

[gcarson1]

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!

 

[Avodyne]

You're welcome!