Thread: Proof by induction

Hello again,
I was helped nicely on the other question that I posted that I thought I'd post another--but this one is more to be checked over rather than one that needs complete guidance on...

The question is: Prove: for all integers n >= 0, 3|(n^3-7n+3) by induction.

Obviously, the base step I have is that with n=0, 0^3 - 7(0) + 3 = 3 and 3|3 since 3 mod 3=0 and thus 3 divides 3. Therefore the base step is proven.

For the inductive step, I am substituting P(n) with P(n+1) and therefore I have (n+1)^3 - 7(n+1) + 3 and, through some algebraic manipulation, I can get (n^3 - 7n + 3) + 3n^2 + 3n + 6. Now my question is: can I finish this proof off by saying that if (n^3 - 7n + 3) (the base step) is obviously divisible by three, the total in the inductive step (that is when you add 3n^2 + 3n + 6 to (n^3 - 7n + 3)) is also divisible by 3 since (3n^2 + 3n + 6) is just a bunch of additions of multiples of 3? Or is there a better way to end this? Thanks in advance!

Originally Posted by JTL4869

Hello again,
I was helped nicely on the other question that I posted that I thought I'd post another--but this one is more to be checked over rather than one that needs complete guidance on...

The question is: Prove: for all integers n >= 0, 3|(n^3-7n+3) by induction.

Obviously, the base step I have is that with n=0, 0^3 - 7(0) + 3 = 3 and 3|3 since 3 mod 3=0 and thus 3 divides 3. Therefore the base step is proven.

For the inductive step, I am substituting P(n) with P(n+1) and therefore I have (n+1)^3 - 7(n+1) + 3 and, through some algebraic manipulation, I can get (n^3 - 7n + 3) + 3n^2 + 3n + 6. Now my question is: can I finish this proof off by saying that if (n^3 - 7n + 3) (the base step) is obviously divisible by three, the total in the inductive step (that is when you add 3n^2 + 3n + 6 to (n^3 - 7n + 3)) is also divisible by 3 since (3n^2 + 3n + 6) is just a bunch of additions of multiples of 3? Or is there a better way to end this? Thanks in advance!

Dear JTL4869,

Yes your reasoning is correct.

If is divisible by 3, . Hence

Since n and k are integers, is also an integer. Therfore, is divisible by 3.

Double check your work...

Should you have a +6 or a -6 ?

Doesn't make any difference to the proof ... but

Originally Posted by Archie Meade

Double check your work...

Should you have a +6 or a -6 ?

Doesn't make any difference to the proof ... but

Woops! You're right.