prove by induction 6 divides n^3 -n

**robocop_911** · May 31st 2008, 05:08 PM

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!!!

**topsquark** · May 31st 2008, 05:21 PM

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

**robocop_911** · May 31st 2008, 05:26 PM

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?$

**robocop_911** · May 31st 2008, 05:29 PM

Originally Posted by robocop_911

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

Ahhh!!! I got it thanks bud!!!

**topsquark** · May 31st 2008, 05:34 PM

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

**robocop_911** · May 31st 2008, 05:39 PM

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!

**angel.white** · May 31st 2008, 05:47 PM

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.

**topsquark** · June 1st 2008, 04:08 AM

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

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

LinkBack

Thread Tools

Display

prove by induction 6 divides n^3 -n

Similar Math Help Forum Discussions

Prove using induction on n that 3 divides (4^n)+5

Prove 3 divides two integers

Prove that ab divides c.

Prove that p divides infinitely many numbers...

Prove that gcd(a,b) divides lcm[a,b]

Search Tags