# Need some help with an even/odd proof by contraposition.

Let me preface this by saying I am horrible at math, and I apologize for the dumb question.

So, I'm trying to prove that "for all integers 𝑛, if (𝑛^2) + 2 is even, then 𝑛 is even.", and it has to be by contraposition. This is what I have so far:

By contrapositive, this statement is the same as: for all integers n, if n is odd, then (n^2) + 2 is odd

By definition of odd, n = 2k+1 for any integer k

Thus by substitution, ((2k+1)^2) + 2

= 4k^2 + 4k + 3

=4(k^2 + k) + 3 by basic algebra

Obviously I'm trying to get it to take the 2n+1 form for an odd integer, but right now it's stuck at 4n+3. How do I get it into the proper form to complete the proof? Am I missing something obvious?

• Factor out a 2. 4n+3=2(2n+1)+1 – Sean English Nov 21 '16 at 22:51
• So the next step in the proof should look like "= 2(2k^2 + 2k + 1) + 1" ? – davidib17 Nov 21 '16 at 23:09
• Yeah. Usually it is fine to just state that 4(k^2+k)+3 is odd, but if you really want to make sure it is clear, that would be the next step. – Sean English Nov 21 '16 at 23:11

I'll continue from the asker's post, which was a good start. We recognize $2n$ is even for any integer n, and $2n+1$ is odd for any integer $n$.

Then we want to prove the contrapositive of

$(A):$ "For all integers $n$, if $(n^2) + 2$ is even, then $n$ is even."

The contrapositive of $(A)$ is given by

$(B)$: "For all integers $n$, if $n$ is odd, then $(n^2)+2$ is odd." The two statements are logically equivalent.

"Thus by substitution, assume $n$ is an odd integer. Then $n=2k+1,$ where $k$ is some integer. Then:

$$n^2 + 2 =((2k+1)^2) + 2 = 4k^2 + 4k + 3 = 4k(k + 1) + 3..."$$

From there:

$$4k^2 + 4k + 3 = 4k^2 + 4k + 2 + 1 = 2\cdot\underbrace{\left(2k^2+ 2k + 1\right)}_{\large j} + 1= 2j+1$$

(where $j$ is the integer given by $j=2k^2+2k+1, \quad k\in \mathbb Z$).

So we summarize:

For all $n\in \mathbb Z$, if $n$ is odd, then $n^2 + 2$ must be odd.

Since we have proved the equivalent contraposive, $(B)$, of the original statement we want to prove, we can indeed assert:

For all $n \in \mathbb Z,\; \text{ if }\,\;n^2+2$ is even, then $n$ must be even."

Side note

Given two statements $p,q$, $\quad (p\to q) \equiv (\lnot q \to \lnot p)$.

We use $p:= "n^2 + 2$ is even", and $q:= "n$ is even." So, $\lnot p$ is "$n^2 +2$ is odd" and $\lnot q$ is "$n$ is odd$. We first proved$\lnot q \to \lnot p$, to prove its equivalent,$\,p\to q\$

• An explanation of what this means would be helpful – Sam Redway Jul 2 '17 at 23:02
• Apologies if this came off sarcastic or rude - was not meant that way. This is the first time I have looked at this subject matter and found your answer initially confusing due to lack of explanation. After some thought it did click, and it is kind of obvious once you know, so can see why you thought no explanation was required ... it may be helpful for others that are like myself quite novice in maths and look at this in the future though. Just a thought ... – Sam Redway Jul 3 '17 at 15:11
• @SamRedway I will delete my comment. Thanks for your comment. Note that you prompted me to explain the answer a bit more. (I had originally continued in my original answer, where the asker left off in the questions, because the asker had a very good start. – Namaste Jul 3 '17 at 15:40
• I've done more editing, @Sam. Let me know what you think? – Namaste Jul 3 '17 at 15:55
• Great answer, thanks – Sam Redway Jul 3 '17 at 18:09