70
$\begingroup$

I am just learning maths, and would like someone to verify my proof.

Suppose $n$ is an integer, and that $n^2$ is even. If we add $n$ to $n^2$, we have $n^2 + n = n(n+1)$, and it follows that $n(n+1)$ is even. Since $n^2$ is even, $n$ is even.

Is this valid?

$\endgroup$
4
  • 20
    $\begingroup$ This is quite a nice proof, although the first thing that came to my mind was "If $n$ is odd, then $n^2$ is odd". $\endgroup$
    – Tunococ
    May 26 '13 at 23:46
  • 4
    $\begingroup$ Contrapositive FTW $\endgroup$ May 27 '13 at 16:10
  • 26
    $\begingroup$ While everyone else seems to agree the proof is flawless, I am put off by the phrase "and it follows that $n(n+1)$ is even". Follows from what? From the fact that you have obtained $n(n+1)$ by adding $n$ (of unknown parity) to $n^2$ (supposed even)? I cannot follow the reasoning. It happens to be that $n(n+1)$ is always even (for $n$ integer), which you can check by considering both cases $n$ even or odd (or by saying one of $n,n+1$ must be even, but that is really doing the same thing). If you use this, you should say so. Note you can also prove your main statement by doing those two cases. $\endgroup$ May 27 '13 at 16:28
  • $\begingroup$ If you define an even number as an integer that is not odd, then this amounts to showing that "if n$^2$ is not odd, then n is not odd." $\endgroup$ May 29 '13 at 1:12

15 Answers 15

37
$\begingroup$

It could use a little more explanation, but yes, it works. I’d expand it to point out explicitly why $n(n+1)$ is even and that $n=(n^2+n)-n^2$ is then the difference of two even numbers and as such is even (assuming that you already have this fact available to use).

An alternative approach is to show that if $n$ is odd, then $n^2$ is odd; the desired result is the contrapositive and therefore follows at once.

$\endgroup$
0
16
$\begingroup$

This proof is valid.

I suggest you add the small detail that the difference of even integers is even.

$\endgroup$
1
  • 7
    $\begingroup$ Can the downvoter please give the reason for downvoting ? maybe I can improve my answer $\endgroup$
    – Belgi
    May 27 '13 at 17:15
12
$\begingroup$

If $n$ is odd say $n=2k+1$ then $$n^2=(2k+1)^2=(2k+1)\times (2k+1)=2\times(k(2k+2))+1\quad\text{is odd}$$ hence necessary $n$ is even

$\endgroup$
1
  • 1
    $\begingroup$ This is the same example used by my trainer when I was in 8th Grade $\endgroup$ May 27 '13 at 11:55
10
$\begingroup$

Another simple proof:

$2|n^2$, but $2$ is prime then $2|n$.

$\endgroup$
7
$\begingroup$

Of course, you can always use the fact that if $p$ is a prime which divides a product $ab$ ,then $p | a$ or $p |b$. But, I'm not sure if you have this result, and the question suggests that you don't. If you want to prove it, you can argue along the following lines--if you know Bezout's identity.

Suppose that $p$ divides $ab$ ,but not $a$. Then, it folows that $gcd(a,p)=1$. Hence, we may express $1=np+ma$. Or $b=nbp+mba$. Now, since we know that $p|ab$, we have that $ab=\alpha p$, and so $a=\frac{\alpha p}{b}$. Hence, by substitution, we have that $b=nbp+m\alpha p=p(nb+\alpha m)$. Hence, b is divisible by p.

For this particular problem, a=b=n.

Note, that if you do not know Bezout's identity, then you will have no idea how I was able to write 1 as a linear combo of p and a. First note that 1 is the gcd of $p$ and $a$. Hence, we can obtain one by iterating the Euclidian algorithm again and again. Then, we just backwards substitute from the last equation upwards to get the gcd as a linear combo of the two numbers involved. Try it with 5 and 17, for instance. This is Bezout's idenitity.

$\endgroup$
5
$\begingroup$

We know that,

  1. $n^2=n\times n $, We also know that

  2. even $\times$ even = even

  3. odd $\times$ odd = odd
  4. odd $\times$ even = even

Observation $1$: As $n^2$ is even, we also get an even result in the 2nd and 4th case .

Observation $2$: In the expression "$n \times n$" both operands are same i.e. '$n$', hence we get the result even in the $2$nd and $3$rd case

Since the $2$nd case is common in both the operations we take the first case.Hence comparing even $\times$ even = even and $n^2=n\times n $, Hence proved if $n^2$ is even, then $n$ is even.

$\endgroup$
4
$\begingroup$

That's right. Here is another proof: $\forall n\in\mathbb{Z}$ if $n$ is odd, then $n^2$ is odd . Let $m$ be an integer such that $m^2$ is even. Then $m$ must be even, because if $m$ is odd then $m^2$ must be odd, contrary to the hypothesis.

$\endgroup$
3
$\begingroup$

From: http://mathforum.org/library/drmath/view/56084.html

Try a proof by contraposition (are you familiar with this method of proof? A statement and its contrapositive are logically equivalent so proving the contrapositive of the original statement actually proves the original statement).

So what you want to do is assume that $n$ is not even (i.e., it is odd) and show that $n^2$ is not even (i.e., it is odd).

$n$ is odd means that you can write $n = 2k + 1$ for some integer $k$. Then

$$n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$

which is clearly odd. This completes the proof.

I hope this helps. Please write back if you'd like to talk about this more.

$\endgroup$
2
$\begingroup$

Yes; $ $ simpler: $\,n\ {\rm odd}\,\Rightarrow\, 1\!+\!n\,\ {\rm even}\,\Rightarrow\, n = (1\!+\!n)n-n^2 =\rm even-even = even\,\Rightarrow\Leftarrow$

$\endgroup$
5
  • 1
    $\begingroup$ Haha, I have only ever seen one other person use that symbol for contridiction. $\endgroup$ May 27 '13 at 0:26
  • 1
    $\begingroup$ @Chris The opposing-arrow (or Hand of Eris) notation for "contradiction" is so common that it is mentioned in Wikipedia. $\endgroup$
    – Key Ideas
    May 27 '13 at 1:13
  • $\begingroup$ I had no idea... I am from a small city :( $\endgroup$ May 27 '13 at 5:24
  • 2
    $\begingroup$ I am not convinced that this is simpler. It seems to be the same argument wrapped up in a contradiction, and therefore could be claimed to be more complicated... $\endgroup$
    – user1729
    May 27 '13 at 16:27
  • $\begingroup$ @user1729 It's simpler than the OP's method because that method apparently invokes the lemma that $\,n(n\!+\!1)\,$ is even. The above method does not need that lemma. $\endgroup$
    – Key Ideas
    May 27 '13 at 16:43
0
$\begingroup$

Yes, it's valid. That said I wouldn't say "it follows that n(n+1) is even", because n(n+1) is just even.

So, you have n$^2$+n=n(n+1) and n(n+1) as even. So, we have that n$^2$+n equals the sum of an even integer n$^2$, and some integer n. So, n is either odd or even.

If n were odd, then we would have n$^2$+n would equal the sum of the even number n$^2$ and the odd number n. The sum of an odd number and an even number is always an odd number. So, then n(n+1) would equal an odd number. But, n(n+1) is not an odd number. Since we have a contradiction, by the rule of negation introduction, we have that n is not odd. Since every integer is either even or odd, it follows by the (often derived) rule of disjunctive syllogism, that n is even.

$\endgroup$
0
$\begingroup$

If $n^2$ is even, then it can be factorized as

$$ n^2 = 2^{2k}C^2, $$

where $k$ and $C$ are a positive integers, and $C$ is odd. $k$ cannot be non-positive, because if it is zero or negative, n cannot be integer.

Given $n^2$, $n$ can be written as

$$ n = \mp 2^k C. $$

Which implies that $n$ must also be even.

$\endgroup$
0
$\begingroup$

For natural numbers: If $n$ is even: $n=2k$ for $k =...,-2,-1,0, 1, 2,...$. $n^2=n\cdot n = 2k2k = 4k^2 = 2\cdot 2k^2$. This number is an even number.
If $n$ is odd: $n=2k + 1$ for $k =...,-2,-1,0, 1, 2,...$. $n^2=n\cdot n = (2k+1)(2k+1) = 4k^2+4k+1 = 2\cdot \left(2k\left(k+1\right)\right)+1$. This number is an odd number.
Square preserves the even or odd character of the number.
By simply using the above rules, you can easily make sure that this is true for any number raised to any power. For even $n$ the $n^a$ is even and for odd $n$ the $n^a$ is odd for $a = 2,3,4,...$.

$\endgroup$
0
$\begingroup$

It is valid for sure. You can simplify it just by noting that for every odd $n$ $n^2$ is odd. So the square can be even just with even $n$. But this is the proof just for the implication.

$\endgroup$
0
$\begingroup$

I agree, I think the contra-positive is the way to go. That just means reverse the if-then statement and make it If n is even, then n^2 is even. But, you gotta be careful because it's possible for a statement to be true in one direction and not the other. But, here it seems pretty helpful to us. Also, since you said you were earlier in your math development you are probably pretty familiar with algebra at least... So, If n is even then there is an integer, say k, such that 2n = k. So, if we square both sides we get 4n = k^2. Now, divide by 4 and take the root of the denominator and numerator and n^2 = k / 2. So, you can see that your "claim" is valid. As to the logic itself, it seems good to me but I am pretty early on too so one of the other guys would be a better judge of that than I.

$\endgroup$
0
$\begingroup$

Here is another proof, of the kind "cannon killing a fly".

Suppose $n^2$ even. Then $n^2 = 2k, k \in \mathbb{Z}$.

By Fermat's Little Theorem, $n^2 \equiv n \mod 2$. Then $n^2 - n = 2m, m \in \mathbb{Z}$.

$2k -n = 2m$

$n = 2(k-m), k-m \in \mathbb{Z}$

Hence $n$ is even.

$\endgroup$

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