# For all natural numbers $n,\; n^2-n$ is even.

I am still new to proofs and just getting some practice in so please be kind. I must use the direct method to prove this claim, as stated in the instructions. Any feedback would be much appreciated. Thanks in advance.

Claim: Prove that for all natural numbers $n, n^2-n$ is even.

Proof attempt: If $n^2-n$ is even, then $n^2-n=2k \Rightarrow n^2=2k+n$, for some $k \in \mathbb{Z}$. Multiplying both sides by $2$ we obtain $2n^2=4k+2n \Rightarrow 2n^2=2(2k+n)$. Since $k$ is some integer, $2k+n$ is also some integer. Let $2k+n=m$. Therefore, $2n^2=2m$, which is even.

I know there is something wrong with my proof, but I just can't pinpoint it. Please help!

Should I approach it this way?

If $n^2-n$ is even, then $n(n-1)=2k$, for some $k \in \mathbb{Z}$.

• Yes, you should. Or use congruences, which is shorter. – Bernard Jul 28 '18 at 22:17
• You are assuming what you are going to prove: "If $n^2-n$ is even" and from that proving that something else is even. That is a huge error. – md2perpe Jul 28 '18 at 22:18

Here's a proof using case analysis on whether $n$ is even or odd:

Either $n$ is even or $n$ is odd. (This I assume that we already know.)

If $n$ is even, then $n = 2k$ for some integer $k$. Therefore $n(n+1) = 2k(2k+1)$ which contains a factor $2$ and is therefore even.

If $n$ is odd, then $n = 2k+1$ for some integer $k$. Therefore $n(n+1) = (2k+1)(2k+2) = 2(2k+1)(k+1)$ which contains a factor $2$ and is therefore even.

Thus, $n(n+1)$ is even.

• Thank you! That was easy to follow and made perfect sense. Thanks again for your help. – Ryan Jul 28 '18 at 22:31

# Inductive Proof

Let $$n=1$$. Then $$n^2-n=0$$,which is even. This shows the statement holds for $$n=1.$$ Assume that the statement holds for $$n=k$$, namely, $$k^2-k$$ is even. Then $$(k+1)^2-(k+1)=(k^2-k)+2k,$$which is a sum of two even numbers. Hence, this is also even, which shows that the statement holds for $$n=k+1$$ as well. Consequently, by inductive principle, we may claim the statement holds for all $$n=1,2,\cdots.$$

• Your proof by induction is quite elegant. I really like it! – user573497 Jul 28 '18 at 22:56
• @user573497 thanks! – mengdie1982 Jul 28 '18 at 22:57
• I never thought that it can be proved in that way. – user573497 Jul 28 '18 at 22:58
• Nice! That was the next attempt - to prove by induction on $n$. Thanks! – Ryan Jul 28 '18 at 23:43

The easiest way would be to notice that $n^2 -n = n(n-1)$, which is a product of two consecutive integers. Hence one of the factors has to be even, therefore the product is even.

• The second way, "If $n^2-n$ is even, then $n(n-1)=2k$, for some $k \in \mathbb{Z}$" also assumes what should be proved. – md2perpe Jul 28 '18 at 22:24
• @md2perpe Ah yeah! Thanks for pointing out – Stefan4024 Jul 28 '18 at 22:29

I would start from the other side.

$Theorem: ∀n∈N,n^2-n=2k,k∈N$

Proof:

If n is odd, then $n=2m-1,m∈N$ $n^2-n=(2m-1)^2-(2m-1)=(4m^2-4m+1)-(2m-1)=4m^2-2m+2=2(2m^2-m+1)$

If n is even, then $n^2 -n=(2k)^2-2k,k∈N=4k^2-2k=2(2k^2-k)$

∴$n^2-n$ is even

• Thanks. Very clear and concise. – Ryan Jul 28 '18 at 23:44

Another way, if we subtract $n-1$ we obtain

$$n^2-n-(n-1)=n^2-2n+1=(n-1)^2$$

then if

• $n-1$ is odd, since the difference is odd, $n^2-n$ is even

• $n-1$ is even, since the difference is even, $n^2-n$ is even

therefore in any case $n^2-n$ is even.

$\forall n \in \mathbb{N}$, $\overline{n}\in \mathbb{Z}_2$ where $\mathbb{Z}_2=\{0,1\}$. Then

If $\overline{n}\equiv 0 \mod 2$ then $\overline{n-1}\equiv \overline{n}-1\equiv 1 \mod 2$.

Therefore

$$\overline{n^2-n}=\overline{n(n-1)}\equiv \overline{n}( \overline{n-1})\equiv 0\cdot1\equiv 0 \mod 2$$

Then $n^2-n$ is even.

If $\overline{n}\equiv 1 \mod 2$ then $\overline{n-1}\equiv \overline{n}-1\equiv 0 \mod 2$.

Therefore

$$\overline{n^2-n}=\overline{n(n-1)}\equiv \overline{n}( \overline{n-1})\equiv 1\cdot 0\equiv 0 \mod 2$$

Then $n^2-n$ is even.

Conclution $n^2-n$ is even $\forall n\in \mathbb{N}$