## prove by induction that 6 divides n^3 - n

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
maggiemagnet
Posts: 358
Joined: Mon Dec 08, 2008 12:32 am
Contact:

### prove by induction that 6 divides n^3 - n

Prove by induction that, for any natural umber n, 6 divides n^3 - n.

Let n = 1. Then n^3 - n = 1 - 1 = 0, and 6(0) = 0, so 6 divides n^3 - n.

Let n = k, and assume 6 divides k^3 - k, so 6m = k^3 - k for some natural number m.

Let n = k + 1. Then (k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1 = k^3 + 3k^2 + 2k.

What then?

stapel_eliz
Posts: 1628
Joined: Mon Dec 08, 2008 4:22 pm
Contact:
Let n = k + 1. Then (k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1 = k^3 + 3k^2 + 2k.

What then?
You've got the assumption about k3 - k, so let's see if we can break that out somehow:

. . . . .$k^3\, +\, 3k^2\, +\, 2k$

. . . . .$k^3\, -\, k\, + \, 3k^2\, +\, 3k$

. . . . .$\left(k^3\, -\, k\right)\, +\, 3\left(k^2\, +\, k\right)$

By assumption, you have k3 - k = 6m for some natural number m. For the whole thing to be divisible by 6, you need 3(k2 + k) to be divisible by 6. Obviously it's divisible by 3.

So all that remains is to show that k2 + k is divisible by 2. Consider cases. If k is even, then k = 2p for some natural p, and k2 + k = (2p)2 + (2p) = 4p2 + 2p = 2(2p2 + p). Now what if k is odd, so k = 2p + 1 for some natural p?

Have fun!

maggiemagnet
Posts: 358
Joined: Mon Dec 08, 2008 12:32 am
Contact:

### Re: prove by induction that 6 divides n^3 - n

If k is odd, so k = 2p + 1 for some natural p, then k^2 = (2p + 1)^2 = 4p^2 + 4p + 1 and k^2 + k = (4p^2 + 4p + 1) + (2p + 1) = 4p^2 + 6p + 2 = 2(2p^2 + 3p + 1). This means k^2 + k is still divisible by 2, so 3(k^2 + k) is divisible by 6, so the whole thing is divisible by 6.

Thank you!