# prove by induction 6 divides n^3 -n

• May 31st 2008, 05:08 PM
robocop_911
prove by induction 6 divides n^3 -n
Hello there!

I don't get it - what to assume in the following problem for solving by induction

Prove that 6 divides n^3 - n whenever n is a nonnegative integer

I tried following:

assume for "k" --
k^3 - k = 6r for some integer "r"

now to prove "k+1" we get:
(k+1)^3 - (k+1) = k^3 + 3k^2+3k+1 - k - 1
= (k^3-k) +3k^2+3k
= 6r + 3k^2+3k by induction
what should i do after this? I am not getting "6" as a common factor how come 6 divides n^3-n!!!
• May 31st 2008, 05:21 PM
topsquark
Quote:

Originally Posted by robocop_911
Hello there!

I don't get it - what to assume in the following problem for solving by induction

Prove that 6 divides n^3 - n whenever n is a nonnegative integer

I tried following:

assume for "k" --
k^3 - k = 6r for some integer "r"

now to prove "k+1" we get:
(k+1)^3 - (k+1) = k^3 + 3k^2+3k+1 - k - 1
= (k^3-k) +3k^2+3k
= 6r + 3k^2+3k by induction
what should i do after this? I am not getting "6" as a common factor how come 6 divides n^3-n!!!

$(k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)$

$= (k + 1)(k^2 + 2k)$

$= k(k + 1)(k + 2)$

What can you say about the factors of this product?

-Dan
• May 31st 2008, 05:26 PM
robocop_911
Quote:

Originally Posted by topsquark
$(k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)$

$= (k + 1)(k^2 + 2k)$

$= k(k + 1)(k + 2)$

What can you say about the factors of this product?

So here we don't have to assume that $k^3-k = 6r?$
• May 31st 2008, 05:29 PM
robocop_911
Quote:

Originally Posted by robocop_911
So here we don't have to assume that $k^3-k = 6r?$

Ahhh!!! I got it thanks bud!!!
• May 31st 2008, 05:34 PM
topsquark
Quote:

Originally Posted by robocop_911
So here we don't have to assume that $k^3-k = 6r?$

Huh. I didn't see that. Well you could start by writing $k^3 - k = k(k^2 - 1) = (k - 1)k(k + 1)$ which is automatically divisible by 6 and not worry about it. I guess this problem is just lousy for an induction proof.

But we should be able to write it as one.

Assume the argument is true for some n = k. Then we have
$k^3 - k = 6a$

We need to show that $(k + 1)^3 - (k + 1) = 6b$

So
$(k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1$

$= k^3 + 3k^2 + 2k$

$= (k^3 - k) + 3k^2 + 3k$

$= 6a + 3k^2 + 3k = 6a + 3k(k + 1)$

See what you can do with that line.

-Dan
• May 31st 2008, 05:39 PM
robocop_911
Quote:

Originally Posted by topsquark
Huh. I didn't see that. Well you could start by writing $k^3 - k = k(k^2 - 1) = (k - 1)k(k + 1)$ which is automatically divisible by 6 and not worry about it. I guess this problem is just lousy for an induction proof.

But we should be able to write it as one.

Assume the argument is true for some n = k. Then we have
$k^3 - k = 6a$

We need to show that $(k + 1)^3 - (k + 1) = 6b$

So
$(k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1$

$= k^3 + 3k^2 + 2k$

$= (k^3 - k) + 3k^2 + 3k$

$= 6a + 3k^2 + 3k = 6a + 3k(k + 1)$

See what you can do with that line.

-Dan

What should I do with this line??
$= 6a + 3k^2 + 3k = 6a + 3k(k + 1)$

this is the same line why I posted this question!
• May 31st 2008, 05:47 PM
angel.white
Quote:

Originally Posted by topsquark
$(k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)$

$= (k + 1)(k^2 + 2k)$

$= k(k + 1)(k + 2)$

What can you say about the factors of this product?

-Dan

EDIT: NVM, you addressed this while I was writing it.

But is that legitimate? Because we could also say

$k^3-k = (k-1)k(k+1)$

Now, if we are required to use induction to prove $(k-1)k(k+1)$ is divisible by 6, then why are we not required to use induction when we prove it for $k(k+1)(k+2)$?

It seems like circumventing the requirements.
• Jun 1st 2008, 04:08 AM
topsquark
Quote:

Originally Posted by robocop_911
What should I do with this line??
$= 6a + 3k^2 + 3k = 6a + 3k(k + 1)$

this is the same line why I posted this question!

Don't you think that one of k or k + 1 might be an even number? (That's why I put it into that factored form.)

-Dan