5
$\begingroup$

I have been having a little trouble with proofs, and would like to ask for a hint for this statement. I've already started it, however I'm unsure what I should be doing next.

Prove that if $n^2 + 10$ is odd then $n$ is odd.

My answer so far: Suppose that $n$ is an odd integer, and we want to prove $n^2 + 10$ is odd. There exists a $k$ that $n=2k+1$. By substituting for $n$, we get...

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

$4k^2 + 4k + 11$ = $n^2 +10$

I am unsure what to do next.

EDIT: Thank you all for your hints and answers! They were all brilliant and my understanding for all kinds of proofs is a heck lot better! So much appreciated!

$\endgroup$
  • 1
    $\begingroup$ $[n^2 + 10]_2 = [n^2]_2 + [10]_2 = [n^2]_2 + 0 = [n^2]_2$. $\endgroup$ – kba Oct 27 '13 at 19:02
  • 1
    $\begingroup$ Hi @kba, what's the name of the notation you are using here? I mean that one with the square brackets. Do you have a link for more information? $\endgroup$ – Mzn Oct 27 '13 at 23:14
  • 1
    $\begingroup$ @Mzn, I don't know what the notation is called, sorry, but it's used in Concrete Abstract Algebra. $[x]_y$ is the remainder of $\frac xy$, so $a \equiv b \pmod c \Leftrightarrow [a]_c = [b]_c$. $\endgroup$ – kba Oct 27 '13 at 23:52
  • $\begingroup$ Related: math.stackexchange.com/questions/528811/… $\endgroup$ – The Chaz 2.0 Oct 28 '13 at 0:12
  • $\begingroup$ @kba, I see, thanks a lot! This book should be on my 'study' list! $\endgroup$ – Mzn Oct 28 '13 at 16:15
7
$\begingroup$

Unfortunately, you're working backward. You've (very nearly) proved that if $n$ is odd, then $n^2+10$ is odd.

Now, if you wanted a proof by contrapositive (the simplest way, really), then suppose that $n$ is even, and prove that $n^2+10$ is also even. For a direct proof, assume that $n^2+10$ is odd, and prove that $n^2$ is then odd, and so $n$ is odd (why?). For a proof by contradiction, assume that $n^2+10$ is odd, but $n$ is even, and derive an absurdity.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Because even and odd are mutually exclusive and collectively exhaustive, is it still flawed to go backwards? $\endgroup$ – Nick T Oct 28 '13 at 5:53
  • 1
    $\begingroup$ When it comes to actually proving the claim, yes it is. It turns out that $n^2+10$ is even (respectively, odd) if and only if $n$ is even (respectively, odd), but there are many implications whose converse does not hold, so the direction is still important, even in cases like the above. For example, if $n$ is a perfect square, then $n^2$ is, but the converse is not generally true, even though "perfect square" and "not a perfect square" are mutually exclusive and collectively exhaustive over integers $n$. $\endgroup$ – Cameron Buie Oct 28 '13 at 6:12
9
$\begingroup$

For a direct proof, you need to assume that $n^2 + 10$ is odd, and show this means $n$ is odd. In your proof, you assume $n$ is odd, which is what is to be proven.

For a proof by contraposition, we assume $n$ is not odd, i.e., that $n$ is even, and show this means $n^2 + 10$ is even. So assuming $n$ is even, there is an integer $k$ such that $n = 2k$. Then substitute $2k$ into n: $$n^2 + 10 = (2k)^2 + 10 = 4k^2 + 10 = 2(2k + 5)$$ which is clearly divisible by $2$ and is therefore even.

Remember, what the contrapositive of a statement is: To prove $p \rightarrow q$, we can prove the equivalent statement $\lnot q \rightarrow \lnot p$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Always teaching -->> =1 $\endgroup$ – Amzoti Oct 28 '13 at 1:38
7
$\begingroup$

Your assumptions are backwards. Given $n^2+10$ is odd, you want to prove that $n$ is odd. Perhaps the easiest way to do this is by proving the contrapositive, which can be stated as

If $n$ is even, then $n^2 + 10$ is even.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

What you want to do is prove the contrapositive in proofs of this sort. The tautology is $$(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P).$$

By proving: "If $n$ is even, then $n^2+10$ is even" you will have proven your original theorem.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

If $n^2+10$ is odd, then $(n^2+10)-11$ is even. Thus, $n^2-1$ is even.

Then $2|(n^2-1)=(n-1)(n+1)$. As $2$ is prime, we get $2|n-1$ OR $2|n+1$. Thus $n-1$ is even or $n+1$ is even, which proves that $n$ is odd.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

First note that $n^2 +10$ is odd if and only if $n^2$ is odd. Then you could note that if $n$ is even, then $n^2$ is even. From this it follows that if $n^2$ is not even, then $n$ is not even.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Below is how I would do it:

If $n^2 + 10$ is odd, then $n^2$ is odd.

This makes sense because an odd integer $+1$ is even, an even integer $+1$ is odd, etc. This is to say that an odd integer plus an even integer will give you an odd integer. So it's reasonable to say that if $n^2 + 10$ is odd, then $n^2$ is odd.

Now we want to prove that if $n^2$ is odd, then $n$ must be odd. We note that there are only two possibilities: either $n$ is even or $n$ is odd. Suppose $n$ is even. Then $n$ is a multiple of two, i.e. $2c = n$ for some $c \in \mathbb{Z}$. So $(2c)^2 = 4c^2$, which is also a multiple of two. So if $n$ is even, then $n^2$ must be even. But $n^2$ isn't even, so $n$ can't be even either. (This step was called proving the contrapositive - explanation below). So $n$ must be odd.

Proving the Contrapositive

This is a useful technique. If we have some statement that says $P$ implies $Q$, i.e. if P, then Q, then the statement if not Q, then not P is logically equivalent to the first one (can you figure out why?). Sometimes it can be easier to prove if not Q, then not P than if P, then Q.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Suppose n=2k is even. Then n^2+10 = 4k^2+10=2(2k^2+5) is also even. Consequently, since all integers > 0 are either even or odd (but not both), when n^2+10 is odd, so is n.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

or even simpler,

if $n^2+10$ is odd, then there exists $k \epsilon \mathbb{N}$ such that

$n^2+10 = 2k+1 \Rightarrow n^2 = 2(k-5)+1$

so, $n^2$ must be odd, which implies $n$ is odd.

| cite | improve this answer | |
$\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.