# simple induction ($n^3-n$ is divisible by 6) - Am I doing it right?

as a homework I have to proof that:

$\forall n \in \mathbb{N}: n³-n$ is dividable by 6

Now I did that with a induction

1) basis: $A(0): 0³-0 = 6x$ , $x \in \mathbb{N}_0$// the 6x states that the result is a multiple of 6, right?

2) requirement: $A(n):n³-n=6x$

3) statement: $A(n+1): (n+1)³-(n+1)=6x$

4) step: $n³-n+(n+1)³-n=6x+(n+1)³-n$

So when I resolve that I do get the equation: $n³-n=6x$ so the statement is true for $\forall n \in \mathbb{N}$

Did I do something wrong or is it that simple?

-
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$. – Rick Decker Oct 11 '12 at 15:40

No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then $$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$ is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.

-
Thanks, I got it now :) – Marco Rauscher Oct 11 '12 at 15:01

No need for induction. $$n^3-n=n(n^2-1)=n(n-1)(n+1)$$ which are three consecutive integers. So one must be divisible by 3.

Check for $n=1$: $1^3-1=0=3\cdot 0$

Assume it's true for $n=k$. If you let $n=k+1$ you get \begin{align*} (k+1)^3-(k+1)&=k^3+3k^2+2 \\ &=k^3+3k^2+2k\\ &=3\cdot (k^2+k)+(k^3-k)\end{align*} which is divisible by 3

-
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way. – Marco Rauscher Oct 11 '12 at 14:54
Thanks, I got it now :) – Marco Rauscher Oct 11 '12 at 15:03
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test). – yroc Nov 23 at 19:59