prove by induction that 6 divides n^3 - n

[maggiemagnet]

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]

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 k³ - k, so let's see if we can break that out somehow:

. . . . .

. . . . .

. . . . .

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

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

Have fun!

[maggiemagnet]

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!