# Thread: Just about done with this problem, but I am stuck on this last part!!

1. ## Just about done with this problem, but I am stuck on this last part!!

Q: Prove that 6 divides n^(3) - n whenever n is a nonnegative integer?
__________________________________________________ _______________
What I have is this:

Basis Step:
If n = 0, then f(n)= n^3 - n = 0^(3) - 0 = 0 - 0 = 0.

So the basis step is true since its divisible by 6.
Inductive Hypothesis:
We assume true, if n = k, then f(k) = k^(3) - k.

We must prove that if n = k + 1, then f(k+1) = (k+1)^(3) – (k+1)
Inductive Step:
f(k+1) = (k+1)^(3) – (k+1)
= (k + 1)(k + 2)^(2) - (k + 1)
= (k+1)(k^(2) + 2k + 1) – (k+1)
= k^(3) + 2k^(2) + k + k^(2) + 2k + 1 – k – 1
= k^(3) + 3k^(2) + 3k + 1 – k – 1
= k^(3) + 3k^(2) + 3k – k
= (k^(3) - k) + (3k^(2) + 3k)
= (k^(3) - k) + 3(k^(2) + k)
= f(k) + 3(k^(2) + k)

Where I am stuck at is I know f(k) is divisible by 6 but the 3(k^(2) + k) is divisible by 3?

2. Hello, Grillakis!

Your work is excellent!

Prove that 6 divides $\displaystyle n^3 - n$ for a nonnegative integer $\displaystyle n.$

What I have is this:

Basis Step:
If $\displaystyle n = 1$, then $\displaystyle f(1)\:=\:1^3 - 1 = 0$
. .
So the basis step is true since its divisible by 6.

Inductive Hypothesis:
We assume true: if $\displaystyle n = k$, then: $\displaystyle f(k) \:=\:k^3 - k$ is divisible by 6.

We must prove that if $\displaystyle n \,=\, k + 1$,
. . then: .$\displaystyle f(k+1) \:=\:(k+1)^3 – (k+1)$ is divisible by 6.

Inductive Step:
$\displaystyle f(k+1) \:=\:(k+1)^3 – (k+1)$
. . . . . .$\displaystyle = \;k^3 + 3k^2 + 2k$
. . . . . .$\displaystyle = \;(k^3 - k) + (3k^2 + 3k)$
. . . . . .$\displaystyle = \;f(k) + 3(k^2 + k)$

Where I am stuck: is $\displaystyle 3(k^2 + k)$ divisible by 6? . . . . Yes!

We know that $\displaystyle f(k)$ is divisible by 6: .$\displaystyle f(k) = 6a,\:\text{ for some integer }a.$

$\displaystyle \text{So we have: }\;f(k+1)\:=\:6a + 3\underbrace{k(k+1)}$

Note that $\displaystyle k(k+1)$ is the product of two consecutive integers.
Hence, one of them is even and the other is odd.
And their product is even, say, $\displaystyle 2b,\:\text{ for some integer }b.$

So we have: .$\displaystyle f(k+1)\:=\:6a + 3(2b) \:=\:6(a + b)\;\hdots\;\text{ which is divisible by 6.}$

3. Originally Posted by Soroban
Hello, Grillakis!

Your work is excellent!

We know that $\displaystyle f(k)$ is divisible by 6: .$\displaystyle f(k) = 6a,\:\text{ for some integer }a.$

$\displaystyle \text{So we have: }\;f(k+1)\:=\:6a + 3\underbrace{k(k+1)}$

Note that $\displaystyle k(k+1)$ is the product of two consecutive integers.
Hence, one of them is even and the other is odd.
And their product is even, say, $\displaystyle 2b,\:\text{ for some integer }b.$

So we have: .$\displaystyle f(k+1)\:=\:6a + 3(2b) \:=\:6(a + b)\;\hdots\;\text{ which is divisible by 6.}$

Thanks Soroban....I understand that now.