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

\$\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
• May 31st 2008, 05:26 PM
robocop_911
Quote:

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?\$
• May 31st 2008, 05:29 PM
robocop_911
Quote:

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!!!
• May 31st 2008, 05:34 PM
topsquark
Quote:

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
• 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 \$\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!
• May 31st 2008, 05:47 PM
angel.white
Quote:

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.
• Jun 1st 2008, 04:08 AM
topsquark
Quote:

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