# Thread: Proof by induction

1. ## 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!

2. 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 $\displaystyle n^3-7n+3$ is divisible by 3, $\displaystyle n^3-7n+3=3k~where~k\in Z$. Hence $\displaystyle (n^3 - 7n + 3) + 3n^2 + 3n + 6=3k+3n^2 + 3n + 6=3(k+n^2+n+2)$

Since n and k are integers, $\displaystyle k+n^2+n+2$ is also an integer. Therfore, $\displaystyle 3(k+n^2+n+2)$ is divisible by 3.

3. Double check your work...

Should you have a +6 or a -6 ?

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

4. 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.