9
$\begingroup$

I don't think it is but I don't understand why.

Conjecture: $n^2 \text{ is odd} \Rightarrow n \text{ is odd}$ (*)

Proof:

In general, $$ (A \Rightarrow B) \Leftrightarrow (\neg(B) \Rightarrow \neg(A)) $$

Therefore $(n^2 \text{ is odd } \Rightarrow n \text{ is odd } \Leftrightarrow (\neg(n \text{ is odd}) \Rightarrow \neg(n^2 \text{ is odd})) $

This is the same as $n \text{ is even} \Rightarrow n^2 \text{ is even}$ (✝)

Isn't it?

If it is, then

$$\begin{align} n = 2m &\\ &\Leftrightarrow n^2 = 4m^2 \\ &\Leftrightarrow n^2 = 2(2m^2)\\ \end{align}$$

Therefore $n^2$ is even, by definition of even.

And, since we'e proved (✝), surely we have then proved (*).

I'm a novice to proofs and this is one of my first ones, so I can't notice any obvious problems with it, yet it doesn't seem to me to prove anything - it seems to me to be proving something else entirely. Is it correct?

$\endgroup$
  • 1
    $\begingroup$ Yes, the new equivalent statement is called the contrapositive, and the method is called modus tollens. Your proof is correct. $\endgroup$ – Kenny Lau Aug 28 '17 at 12:52
  • 1
    $\begingroup$ Yes, that's called proof by contrapositive. $\endgroup$ – skyking Aug 28 '17 at 13:13
  • 3
    $\begingroup$ The deduction process is correct, well done, although there is a missing hypothesis. $n$ must be natural, and in the proof you must assert that m is natural. $\endgroup$ – Francesco Alem. Aug 28 '17 at 14:25
9
$\begingroup$

Very well done. Yes, indeed, proving $n\text{ is even}\implies n^2\text{ is even}$ is much easier than the original statement.

$\endgroup$
  • 1
    $\begingroup$ Cool. Thanks :) It didn't seem obvious at first. $\endgroup$ – Benjamin Aug 28 '17 at 12:55
  • 3
    $\begingroup$ @HaroldFinchLinus That's the beauty of maths - follow the rules where they take you, and complicated statements may reduce to trivial truths. $\endgroup$ – 5xum Aug 28 '17 at 12:56
  • $\begingroup$ Just to be curious - how do you prove the original statement without resorting to the contrapositive directly or in disguise? $\endgroup$ – skyking Aug 28 '17 at 13:16
  • $\begingroup$ @skyking Well you can't. That was my point (maybe awkwardly phrased...) $\endgroup$ – 5xum Aug 28 '17 at 13:19
4
$\begingroup$

Alternatively, if $n^2$ is odd, then $n^2-1$ is even. It can be expressed as: $$n^2-1=(n-1)(n+1).$$ If $n$ is even, $n-1$ and $n+1$ are both odd, whose product is also odd and it contradicts the given condition ($n^2-1$ is even). Hence, $n$ is odd.

$\endgroup$
  • $\begingroup$ This is very nice. $\endgroup$ – Benjamin Aug 28 '17 at 20:10
  • $\begingroup$ @Benjamin, thank you. But note your method is nicer as it is shorter. Indeed, given $n^2$ is odd, if $n$ is even, then $n^2$ is also even (contradicts the given condition). Hence $n$ is odd. $\endgroup$ – farruhota Aug 28 '17 at 21:03
3
$\begingroup$

Your idea is correct, but it might be better to write the proof this way:

We prove the contrapositive statement, that if $n$ is even then $n^2$ is even. Since $n$ is even, $n=2k$ for some integer $k$. Then $n^2=4k^2=2(2k^2)$ with $2k^2$ an integer, so $n^2$ is even.

Notice that in your proof, you did not mention that $m$ or $2m^2$ are integers, which are important details. The last two biconditional arrows also obscure the picture, especially when the nature of $m$ is not specified. (You only need one direction in the proof, and the other direction might not even hold in some cases.)

$\endgroup$
  • 1
    $\begingroup$ But how is that better? In what way does it differ in an important way? To me it only looks like a show off in technicalities... $\endgroup$ – skyking Aug 28 '17 at 13:18
  • 2
    $\begingroup$ It's the same proof, just written in a more concise way, like mathematicians write proofs. However, it might be better for Benjamin to write the proof in his way; that shows that he has thought himself and not just copied a proof. $\endgroup$ – md2perpe Aug 28 '17 at 15:46
2
$\begingroup$

Alt. hint: $\,n^2+n=n(n+1)$ is always even, since one of two consecutive integers must be even. Therefore $n^2$ and $n$ always have the same parity and, in particular, $n^2$ is odd iff $n$ is odd.

$\endgroup$
  • 2
    $\begingroup$ Nice hint, in other words we can just subtract $(n^2+n)-n^2$ and immediately get $n$, which must be odd (because even minus odd is odd). $\endgroup$ – Sil Aug 30 '17 at 7:13
1
$\begingroup$

Your proof is correct as has been pointed by others and perhaps it is the most simple way to go about this, but just for fun, here is somewhat more direct proof (trying to avoid proof by contrapositive or contradiction):

If $n^2$ is odd, then $n^2+2n+1$ is even (odd + odd is even). Notice that this is just $(n+1)^2$. This means that $2$ divides $(n+1)^2$ and since $2$ is a prime, it follows $2$ divides $(n+1)$ and so $n$ is odd.

Another way to go about this is noticing that if $n^2$ is odd, then it can be written as $n^2=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ where $p_i$ are odd primes. Now $n$ is divisor of $n^2$ and so it must also consist only of odd primes, hence $n$ is odd.

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