Help with Induction Proofs for Beginners

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

 

[matt grime]

1. Why are you factoring out (n+1)^3? You can't.

The philosophy of induction is to relate one statement to previous ones.

So, given (n+1)^3 + 2(n+1) and n^3+2n, what have you tried to do with both?

 

[gcarson1]

1. Why are you factoring out (n+1)^3? You can't.

The philosophy of induction is to relate one statement to previous ones.

So, given (n+1)^3 + 2(n+1) and n^3+2n, what have you tried to do with both?

Tried to divide both by 3 in order to redue the formula to a positive integer. Yet I still don't understand how to write or show this?

 

[matt grime]

Divide both sides of what by 3?

Do the only possible thing that you can do. Expand (n+1)^3+2(n+1). Then think.

 

[gcarson1]

Ok I think I got it, the expansion is a little messy but here goes :
Prove that 3|n^3+2n whenever n is a positive integer.
Basis Step: 1^3+2(1)/3 = 3/3 = 1 then we know that the first step in the formula is true.
Inductive Step: 3|(n+1)^3+2(n+1) If both terms are multiples of 3 then they are divisible by 3 so:
3|(n+1)^3+2(n+1)- (n^3+2n)

Expand
(n+1)^3
(n+1)^2(n+1)
(n^2+n+1)n+(n^2+n+1)1
n^3+n^2+n+n^2+n+1
n^3+2n^2+2n+1
Insert back into equation
n^3+2n^2+2n+1+2n+2
Subtract Original formula
n^3+2n^2+4n+3 - (n^3+2n)
2n^2+2n+3
(2n)(2n)+2n+3
4n+2n+3
6n+3

Since the values are multiples of 3 the formula is divisible by 3 thus 3|(n+1)^3+2(n+1) is true.

Right?

 

[robert Ihnot]

You made a mistake, by the binominal formula: (K+1)^3 = K^3 +3K^2+3K+1. (It is always true that if the power is a prime, (a+b)^p = a^p+b^p +p(middle terms).

We start with Basis: let n=1, 1^3+2(1) = 3.

If true for K, (K+1)^3 +2(K+1) = [k^3+2K] +3K^2+3K+1 +2 . The first part is divisible by 3 by the induction hypothesis and the second is 3K^2+3K+3, all terms divisible.

 

[matt grime]

As robert says, you don't have the correct binomial expansion. Plus you also write something that implies you think 2n^2=(2n)(2n)=4n which is also not true in two different ways.

 

[HallsofIvy]

I got a bad feeling whn you declared "My prof is really not great at explaining this proof method." Now I see I was right. Your problem is not induction-your prof seems to have taught you that well. Your problem is algebra:

(n+1)^3
(n+1)^2(n+1) yes
(n^2+n+1)n+(n^2+n+1)1

No, (n+1)^2= n^2+ 2n + 1, not n^2+ 1
so

n^3+n^2+n+n^2+n+1

should be n^3+ 2n^2+ n+ n^2+ 2n+1 and you get n^3+ 3n^2+ 3n+ 1.

But far, far worse!

2n^2+2n+3
(2n)(2n)+2n+3
4n+2n+3

A thousand lashes with a wet noodle! 2n^2 is NOT(2n)(2n), that would be 4n^2. But anyway, (2n)(2n) is NOT 4n! You took the square off the n and put it on the 2- that's not cricket.