0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Yes, you should. Or use congruences, which is shorter. $\endgroup$ – Bernard Jul 28 '18 at 22:17
  • 5
    $\begingroup$ 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. $\endgroup$ – md2perpe Jul 28 '18 at 22:18
1
$\begingroup$

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.

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

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

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

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – md2perpe Jul 28 '18 at 22:24
  • $\begingroup$ @md2perpe Ah yeah! Thanks for pointing out $\endgroup$ – Stefan4024 Jul 28 '18 at 22:29
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks. Very clear and concise. $\endgroup$ – Ryan Jul 28 '18 at 23:44
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$\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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.