I want to prove that a² -a is divisible by 2 for all a that is natural. Here is what I know:
- If a is even a² is even, if a is odd a² is odd.
- a² − a is a substraction if and only if a is natural.
- Any even number substracted by an even number is even. Any odd number substracted by an odd number is even.
- Since a²-a is always even and even numbers are divisible by 2, a²-a is divisible by 2.
Not the most elegant proof but I think it works. How do I prove this by well order principle?
Well-ordering principle: any non-empty set of natural numbers has a smallest element.
Natural numbers: I shall assume you mean $\{0,1,2,3,\ldots\}$ but if you mean $\{1,2,3,\ldots\}$ then you will find it is easy to modify the proof.
Let $S$ be the set of natural numbers $a$ for which $a^2-a$ is not even. Suppose that $S$ is not empty. Then $S$ has a smallest element, call it $b$. Now $b\ne0$ since $0^2-0$ is even. So $b-1$ is a natural number. Also, $$(b-1)^2-(b-1)=(b^2-b)-2b+2\ ,$$ and this is odd because $b^2-b$ is odd and the other terms are even. Therefore $b-1$ is in $S$. But this is impossible because $b$ was the smallest element of $S$.
Our assumption that $S$ is not empty has led to a contradiction and is therefore false: that is, $S$ is the empty set. Hence $a^2-a$ can never be odd and is always even. This completes the proof.