New to induction, stuck on a proof and i need some help

[johnnyICON]

I am trying to prove that 3 divides n^3~-7n+3 for all integers n greater than or equal to 0.

I have gotten to this point:
3|(k~+~1)^3~-~7(k~+~1)~+~3
Where I try to show that is true for k+1. I have been scribbling on scrap paper trying to figure it out. I've expanded the expression countless times no avail.
Could someone give me a hint?

 

[HallsofIvy]

How about multiplying out (k+1)³- 7(k+1)+ 3?
Part of it, of course, will be k³-7k+ 3 which you know, by the "induction hypothesis", is divisible by 3: k³- 7k+ 3= 3n for some integer n. What is the rest? Can you factor a "3" out of it?

 

[LittleWolf]

Consider n^3-7n+3= n^3-n-6n+3=n(n^2-1)-3(2n-1)=(n-1)n(n+1)-3(2n-1). You just need to prove (by induction) that the product of three consecutive integers ((n-1)n(n+1)) is always divisible by 3 since 3(2n-1) is divisible by 3.

 

[johnnyICON]

How about multiplying out (k+1)³- 7(k+1)+ 3?
Part of it, of course, will be k³-7k+ 3 which you know, by the "induction hypothesis", is divisible by 3: k³- 7k+ 3= 3n for some integer n. What is the rest? Can you factor a "3" out of it?

Ahhh, I didn't notice that when I was expanding out. The k's threw me off :(
Question: You expanded -7(k+1). Where is the -7?

[(k+1)^3-7k+3]-7
The equation within the brackets is divisible by 3, but -7 is not. I really like this approach because this is more of how I would try to solve the problem. The -7 doesn't make sense though. Maybe I missed something in your explanation.

Thanks for the help.

Consider n^3-7n+3= n^3-n-6n+3=n(n^2-1)-3(2n-1)=(n-1)n(n+1)-3(2n-1). You just need to prove (by induction) that the product of three consecutive integers ((n-1)n(n+1)) is always divisible by 3 since 3(2n-1) is divisible by 3.

Awesome. This makes sense. I wonder how you are able to see these things right away. Must take a lot of practice to be able to play around with terms that easily. I'll probably give this one a shot, I just feel like I didn't do any work :( Thanks for the help though. :D

 

[Gokul43201]

[(k+1)^3-7k+3]-7
The equation within the brackets is divisible by 3, but -7 is not.

Recheck that. The part within brackets is not divisible by 3. You must multiply out the cubic term and keep only the k^3 part within the brackets. The rest go outside, by the "-7".

 

[johnnyICON]

Recheck that. The part within brackets is not divisible by 3. You must multiply out the cubic term and keep only the k^3 part within the brackets. The rest go outside, by the "-7".

Isn't it though? By the induction hypothesis I am assuming that P(n) is true, that is 3 divides n³-7k+3 where n is just k+1.

 

[johnnyICON]

Whoops, ignore my previous post. :D

 

[HAP]

I have an easy prove for you, but is not quite sure if I'm making an illegal conclusion (I have not learned about induction yet). Take a look:

First I asume that 3|(n^3 - 7n + 3) is true. Then I try to prove that 3|((n+1)^3 - 7(n+1) + 3) is also true...

I do this by expanding the expresion to:
n^3 + 3n^2 + 3n + 1 - 7n - 7 + 3

And move the terms around:
(n^3 - 7n + 3) + (3n^2 + 3n + 1 - 7)

And at last simplify it:
(n^3 - 7n + 3) + (3n^2 + 3n - 6)
(n^3 - 7n + 3) + 3*(n^2 + n - 2)

Since 3*(n^2 + n - 2) is divisible with 3, I have proven that if 3|(n^3 - 7n + 3) is true, then 3|((n+1)^3 - 7(n+1) + 3) is also true! I guess that is what induction is all about?

 

[tongos]

if n^3-7n+3 is divisible by 3 then isn't
n^3-7n is divisible by 3?

n^3-7n= n(n^2-7)
if n is not divisible by 3, then n^2-7 must. when 3 is in, n^2-7 is never divisible by 3, always a remainder of 2. n^2-7= n^2-4-3

(n-2)(n+2)-3 must be divisible by 3 when n is not divisible by 3.
the three at the end cancels because we know that if k is divisible by 3, then so is k-3.
(n-2)(n+2) must be divisible by 3.
If n has a remainder of 1, like 4, then n+2 must be divisible by 3. If n has a remainder of 2, then (n-2) must be divisible by 3. And the maximum remainder you could possibly have is 2.