# Thread: prove by induction 6 divides n^3 -n

1. ## 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!!!

2. 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!!!
$\displaystyle (k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)$

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

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

What can you say about the factors of this product?

-Dan

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

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

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

What can you say about the factors of this product?
So here we don't have to assume that $\displaystyle k^3-k = 6r?$

4. Originally Posted by robocop_911
So here we don't have to assume that $\displaystyle k^3-k = 6r?$
Ahhh!!! I got it thanks bud!!!

5. Originally Posted by robocop_911
So here we don't have to assume that $\displaystyle k^3-k = 6r?$
Huh. I didn't see that. Well you could start by writing $\displaystyle 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
$\displaystyle k^3 - k = 6a$

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

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

$\displaystyle = k^3 + 3k^2 + 2k$

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

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

See what you can do with that line.

-Dan

6. Originally Posted by topsquark
Huh. I didn't see that. Well you could start by writing $\displaystyle 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
$\displaystyle k^3 - k = 6a$

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

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

$\displaystyle = k^3 + 3k^2 + 2k$

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

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

See what you can do with that line.

-Dan

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

this is the same line why I posted this question!

7. Originally Posted by topsquark
$\displaystyle (k + 1)^3 - (k + 1) = (k + 1)((k + 1)^2 - 1)$

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

$\displaystyle = 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

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

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

It seems like circumventing the requirements.

8. Originally Posted by robocop_911
What should I do with this line??
$\displaystyle = 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