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

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

prove by induction that 6 divides n^3 - n

Postby maggiemagnet on Thu Feb 05, 2009 2:08 pm

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?
User avatar
maggiemagnet
 
Posts: 297
Joined: Mon Dec 08, 2008 12:32 am

Sponsor

Sponsor
 

  TOPIC_SOLVED

Postby stapel_eliz on Fri Feb 06, 2009 12:52 am

maggiemagnet wrote: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:

. . . . .

. . . . .

. . . . .

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. :wink:

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! :D
User avatar
stapel_eliz
 
Posts: 1803
Joined: Mon Dec 08, 2008 4:22 pm

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

Postby maggiemagnet on Mon Feb 09, 2009 5:23 pm

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! :clap:
User avatar
maggiemagnet
 
Posts: 297
Joined: Mon Dec 08, 2008 12:32 am


Return to Discrete Math