Induction Formulation

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

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?

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)

gcarson1

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?


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

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

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

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

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!