The Student Room Group

Proof by induction

Prove n^3-n is divisible by 6 for all integers n greater than or equal to 2
Reply 1
Original post by underwood432
Prove n^3-n is divisible by 6 for all integers n greater than or equal to 2


What have you tried so far?
Original post by math42
What have you tried so far?
the normal method for proof by induction, just I end up with the answer f(k) + 3(k^2+k)=6n
where f(k) is a multiple of 6 and 6n is a multiple of 6. But i don't know if this is right or not
Original post by underwood432
the normal method for proof by induction, just I end up with the answer f(k) + 3(k^2+k)=6n
where f(k) is a multiple of 6 and 6n is a multiple of 6. But i don't know if this is right or not


Post your proof so far, step by step, and then the study helpers can see where you may have made an error, if at all.
Reply 4
Original post by underwood432
the normal method for proof by induction, just I end up with the answer f(k) + 3(k^2+k)=6n
where f(k) is a multiple of 6 and 6n is a multiple of 6. But i don't know if this is right or not


So you mean f(k) = k^3 - k right? Well it's correct that f(k + 1) = f(k) + 3(k^2 + k). So if you've shown that this is a multiple of 6 then you're done.
Original post by underwood432
the normal method for proof by induction, just I end up with the answer f(k) + 3(k^2+k)=6n
where f(k) is a multiple of 6 and 6n is a multiple of 6. But i don't know if this is right or not


You need to show that 3(k2+k)3(k^ 2 +k) is a multiple of 6.

You have a factor of 3 already, so just show that k2+kk^2 + k always has a factor of 2, and you're done.
1) let n=2 to prove it. (this was true).

2) let n=k --> k^3-k= f(k), f(k) being a multiple of 6 3) let n=k+1 --> (k+1)^3-k+1

4)when expanded and subtracting k+1 --> k^3+3k^2+2k= 6n where n is a multiple of 6

5)substitute f(k) into equation (f(k)+k)+3k^2+2k=f(k)+3k^2+3k=6n

6)simplify -->f(k)+3(k^2+k)=6n
Original post by RDKGames
You need to show that 3(k2+k)3(k^ 2 +k) is a multiple of 6.

You have a factor of 3 already, so just show that k2+kk^2 + k always has a factor of 2, and you're done.


Awesome! How would I do that?
Original post by underwood432
Awesome! How would I do that?


Well factoring it gives us k(k+1)k(k+1), and since k2k \geq 2 is an integer, what does this tell you about the product??
Original post by RDKGames
Well factoring it gives us k(k+1)k(k+1), and since k2k \geq 2 is an integer, what does this tell you about the product??


the product is an integer? so, for all integers greater than 2 for k, it's always a multiple of 2?
Original post by underwood432
the product is an integer? so, for all integers greater than 2 for k, it's always a multiple of 2?


Yeah the product is an integer but the point is that either kk or k+1k+1 must be an even number for whichever kk you pick. So their product is an even number, hence factor of 2.

Anyway, to finish it up, state that f(k)f(k) and 3(k2+k)3(k^2+k) are both multiples of 6 hence f(k+1)f(k+1) is a multiple of 6.
Original post by RDKGames
Yeah the product is an integer but the point is that either kk or k+1k+1 must be an even number for whichever kk you pick. So their product is an even number, hence factor of 2.

Anyway, to finish it up, state that f(k)f(k) and 3(k2+k)3(k^2+k) are both multiples of 6 hence f(k+1)f(k+1) is a multiple of 6.


ah ok! i get it! thank you very much

Quick Reply