Using the Well Ordering Principle to Show that n^3 - n is divisible by 6. A Guide On Well-Ordering Principle
MIT OCW Guide on WOP
I read the following two sources and I think I understand the structure of proofs involving WOP, but I am stuck on the open-ended part where you prove P(n-1) for the  following problem: 


*

*Use the well-ordering principle to show that n^3 - n is divisible by 6. 


Any help would be greatly appreciated! 
Note: After factoring out (n-1)^3 - (n-1) it took the form of n^3 - 3n^2 + 2n and the only difference between that and n^3 - n is "3n^2 - 3n" which I proved was divisible by 6 via induction. Is there a better way to solve this problem?
Edit: Show that $n^3-n$ is divisible by $6$ using induction, post is useful however I not supposed to use induction for the main part of the proof.
 A: The basic proof strategy using the WOP is that you need to show that there are no exceptions to the claim that:
$P(n): n^3-n$ is divisible by $6$
and you do this by a proof by contradiction:
Assume there are exceptions. Then let $k$ be the smallest number for which the claim does not hold, i.e. assume that $\neg P(k)$.  Now, if we can now show that $\neg P(k-1)$, then we have our contradiction, because $k$ was supposed to be the smallest number for which the claim did not hold.  That is, you need to show that:
$\neg P(k) \Rightarrow \neg P(k-1)$
(Note: this assumes $k>0$, or, if you start with $1$, that $k>1$. ... if $k=0$ (or $k=1$), you show there is a contradiction by showing that in fact we do have $P(0)$.  So note how WOP is really equivalent to induction, where you show $P(0)$, as well as $P(k-1)\Rightarrow P(k)$, which of course is just the contrapositive of $\neg P(k) \Rightarrow \neg P(k-1)$)
Well, you can show that $(k-1)^3-(k-1)=(k^3-k)-(3k^2-3k)$
So, given the assumption that $\neg P(k)$, i.e. that $(k^3-k)$ is not divisible by $6$, then (start of inside proof by contraposition) if $(k-1)^3-(k-1)$ were to be divisible by $6$, then $(3k^2-3k)$ cannot be divisible by $6$. OK, but obviously $(3k^2-3k)=3(k^2-k)$ is divisible by $3$. And for the remaining term $(k^2-k)$ we have that $(k^2-k)=k(k-1)$, and obviously either $k$ or $k-1$ is even, and so that term is divisible by $2$, and so $(3k^2-3k)$ is divisible by $6$ after all: Contradiction! So, $(k-1)^3-(k-1)$ is not divisible by $6$, under the assumption that $(k^3-k)$ is not divisible by $6$
A: Hint $\ 6\mid f(n)\!=\!n^3\!-\!n\,$ checks true for  $\,-2\le n \le 3.\, $  If it $\,\rm\color{#c00}{fails\ for \,n}\ge -2\,$ then $\,n\ge 4\,$ so $\,n\!-\!6\ge -2\,$ thus $\,f(n\!-\!6)$ is a smaller counterexample by $\!\bmod 6\!:\ f(n\!-\!6)\equiv \color{#c00}{f(n)\not\equiv 0},\,$ by the Polynomial Congruence Rule.
A: Define $f(n) = n^3-n$.
Since $f(-n) = -f(n)$, we only have to prove that $f(n)$ is divisible by $6$ for $n \ge 0$. So our domain is the well-ordered set of natural numbers and we always have $f(n) \ge 0$.
We note that both $f(0)$ and $f(1)$ are divisible by $6$.
Let $k \gt 1$ be the least number such that $f(k)$ is not divisible by $6$, so we employ Euclidean division and write
$\tag 1 f(k) = k^3 - k = 6q + r \quad \text{ with } q \ge 0 \text{ and } 1 \le r \le 5$
Plugging $k-1$ into $f$ we get
$\tag 2 f(k-1) = (k-1)[(k-1)^2-1]$
$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = (k-1) \,(k^2 -2k)$
$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = k^3 -3k^2 + 2k$
$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = (k^3 - k) + k + 2k - 3k^2$
$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = 6q + r + 3k\,(1+k)$
Now both $2$ and $3$ must divide $3k\,(1+k)$, so we write that
$\tag 3 f(k-1) =  6q + r + 6q^{'} = 6(q+q^{'}) + r$
So $f(k-1)$ is also not divisible by $6$, a contradiction.
A: $n^3-n=n(n-1)(n+1)$ which is product of three consecutive numbers. 
Well if you have three consecutive numbers one of them is a multiple of two and one is a multiple of three so the product is a multiple of six. 
