Using the Well Ordering Principle to Show that n^3 - n is divisible by 6.

Question

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:

1. 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.

Answer 1

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$

Answer 2

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

Answer 3

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.

Answer 4

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.