# Help with Induction proof problem [duplicate]

So im working on induction proofs but im having a bit of trouble with them. If you guys could help me that would be greatly appreciated, they're just sort of confusing to me.

Use induction to prove the following theorem:

Theorem: For each integer $$n$$, $$n^3-n\equiv 0\pmod{6}$$

Here is what I have tried on paper

## marked as duplicate by José Carlos Santos, Henning Makholm, Thomas Andrews, Community♦Apr 4 at 18:45

$$(k+1)^3-(k+1)=k^3-k+3k^2+3k=k^3-k+3k(k+1)$$. You know by hypothesis that $$k^3-k$$ is divisible by $$6$$, the other term is divisible by $$6$$ because $$k(k+1)$$ is always even.

In your inductive step you write $$k^3-k=(k+1)^3-(k+1)$$, which I hope was meant to mean equivalence modulo $$6$$ rather than equality, but in any case it's important to prove, not start from, such an equivalence to establish the inductive step. The desired condition is equivalent to $$6$$ dividing $$(k+1)^3-k^3-1=3k(k+1)$$, or to $$k(k+1)$$ being even. This follows from the fact that $$k,\,k+1$$ cannot both be odd.

• Of course, you can again show that $k(k+1)$ is even by induction. $(k+1)(k+2)-k(k+1)=2k+2.$ – Thomas Andrews Apr 4 at 18:35
• @ThomasAndrews Very true. Inductive proofs often make use of results that can, or must, be proved inductively, even if in some cases they're too obvious for us to think to flesh it out. For example, when I say $k$ or $k+1$ is even, that's itself something one could prove inductively; but it would be an uncontroversial observation even to an audience that hasn't "learned" induction explicitly. – J.G. Apr 4 at 18:39

There is mistake in your proof. Note that $$(k+1)^3-(k+1)=k^3+3k^2+3k-k=k^3-k+3k (k+1) .$$ Now $$k^3-k$$ is a multiple of $$6$$ by assumption and $$k (k+1)$$ is a multiple of $$2$$(why?). Can you complete now?

Much easier to prove in steps of $$6$$:

Let the base case be $$-2\le n\le 3$$. This is proved by explicit calculation; there are only 6 cubes to compute, and only one of these gives more than a single-digit result.

For $$n\ge 4$$, the induction hypothesis is $$(n-6)^3-(n-6)\equiv 0\pmod 6$$. If we expand using the binomial theorem, this gives us $$n^3 + (\text{terms that are multiples of 6}) - n + (\text{yet another multiple of 6}) \equiv 0 \pmod 6$$ which is to say $$n^2-n\equiv 0\pmod 6$$ as desired.

Now if $$n$$ is negative, then $$-n$$ is certainly $$\ge -2$$, so we know that $$(-n)^3 - (-n) \equiv 0\pmod 6$$. Negating both sides of this again gives $$n^2-n\equiv 0\pmod 6$$.