# How do I setup a proof using contradiction.

In specific how can I setup a contradiction proof if $3n+2$ is odd then $n$ is odd? I don't want the answer. I just want to know how to set up the proof by contradiction.

I think that I should assume if $3n+2$ is not odd, then $n$ is even then prove that $n$ is in fact odd.

I am unsure of what to assume and what do I prove. I am trying to teach a class you can do the same proof in many different ways.

I know how to prove with a direct proof. Assume $3n+2=2k+1$ and prove $n=2J+1$

I know how to prove with a contrapositive proof. Assume $n=2J$ and prove $3n+2=2k$

How would I do the same setup for a contradiction proof?

• Step 1: If $3n+2$ is not odd (=even), then $3n$ is? – Julien Mar 5 '13 at 18:02
• Assume 3n+2 is even, and then prove 3n is odd. – Whitecat Mar 5 '13 at 18:03
• If $x$ is even, then $x-2$ is? – Julien Mar 5 '13 at 18:04
• If $x$ is even then $x-2$ must be even also. – Whitecat Mar 5 '13 at 18:07
• But how do I set it up? Assume $3n+2$ is not odd and then contradict that it is odd? – Whitecat Mar 5 '13 at 18:09

For a proof by contradiction, you assume the truth of the premise and the negation of the desired conclusion to obtain a contradiction:

"$3n+2$ is odd then $n$ is odd"

Assume both

(1) $3n + 2$ IS odd, and hence, there $3n + 2 = 2k+1$ for some integer $k$.
(2) $n$ is even, that is, there is some integer $m$ such that $n = 2m$.

From these assumptions, you obtain a contradiction, from which you conclude that the negation of both $(1)$ and $(2)$ entails the affirmation of the statement to be proved:

That it must follow that if $3n+2$ is odd, then $n$ is odd.

In general, a proof by contradiction proceeds as follows:

Prove: $\;p\rightarrow q$.

Assume $\;\lnot (p \rightarrow q) \equiv \lnot(\lnot p \lor q) \equiv (p \land \lnot q)$.

Conclude $\;\lnot \lnot (p \rightarrow q) \equiv (p\rightarrow q)$, as desired.

For a general discussion about how the differences and similarities between the two proof strategies, you might want to read an earlier MSE post:

• This makes much more sense with my knowledge of logic. I am a little confused as to Deriving the contradiction. Can I say with the assumption if we have $n = 1$ Then $1$ is true and $2$ is false $\therefore$ we have a contradiction and we can conclude what you wrote at the end? – Whitecat Mar 5 '13 at 18:42
• $\quad$ You can work it out algebraically. You want a "general" contradiction, not a specific counterexample. Work at is a little: remember each term has $n$ in common. If n = 2m, then 3n + 2 = 3(2m) + 2 = 2k+1 for some integers m, k $\implies$ ? See how it goes, and if you get stuck, post a comment and I'll work with you. – Namaste Mar 5 '13 at 18:49
• Nice Amy :^D.... – mrs Mar 5 '13 at 18:50
• I just followed your hint and substitution and showed $3(2m) + 2 = 2(3m+1) = 2j$ is even, and derived the contradiction. – Whitecat Mar 5 '13 at 18:59
• Exactly! Good for you! Since, by assumption, we have $3(2m) + 2 = 2k + 1 \implies 2(3m+1) = 2k + 1 \implies 2j = 2k + 1,$ for integers k, j, we have a contradiction, since there's no way that $2j = 2k+1,$ because 2 divides the left hand side, but not the right hand side (or there's no way an even number can equal an odd number.) Feels good, doesn't it, to "crack" a proof? – Namaste Mar 5 '13 at 19:04

Hint: You are trying to prove $3n+2$ odd $\implies\ \ n$ odd. So assume the falsity of this statement, which means $3n+2=2k+1$ for some integer $k$ and $n=2m$ for some integer $m$. Now how can you manipulate $n=2m$ to make it look like the other and find a contradiction?

• I think this is a perfect answer on how to set up the problem. – Whitecat Mar 5 '13 at 18:20
• The proof is $p \rightarrow q$ so I want to do contradiction $p \rightarrow \sim q$ But is that wrong? It seems like this contradiction setup is $\sim p \rightarrow q$ – Whitecat Mar 5 '13 at 18:25
• You need to assume the truth of the premise AND the negation of the conclusion: Assume $p \land \lnot q$. Whitecat: see my answer for clarification of what I mean. – Namaste Mar 5 '13 at 18:35
• @Whitecat: the negation of $p \rightarrow q$ is $p \wedge \sim q$, not $p \rightarrow \sim q$. If $p$ is false, then both $p \rightarrow q$ and $p \rightarrow \sim q$ are true. – Ross Millikan Mar 5 '13 at 18:36
• @Whitecat: no problem. amWhy's answer is a good one. – Ross Millikan Mar 5 '13 at 19:17

With contradiction, I think you should assume $n$ is even, i.e., $n = 2k$, then prove that $3n + 2 = 6k + 2$ is even, which contradicts the fact that $3n + 2$ is odd.

To prove $p\rightarrow q$, you prove that $\;\lnot q \rightarrow\lnot p$. And you say since we have already assumed $p$, we can't have $\lnot q$, because $\;\lnot q \rightarrow\lnot p$. Therefore, you have $q$. That is to say, $p\rightarrow q$.

• That is proving the contrapositive, which is a bit different than proof by contradiction. They are similar, but distinct. See the link in my answer for a more elaborate discussion of the distinction. – Namaste Mar 6 '13 at 4:18