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?

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

Derive a contradiction.

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:

  • $\begingroup$ 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? $\endgroup$ – Whitecat Mar 5 '13 at 18:42
  • 1
    $\begingroup$ $\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. $\endgroup$ – Namaste Mar 5 '13 at 18:49
  • $\begingroup$ Nice Amy :^D.... $\endgroup$ – mrs Mar 5 '13 at 18:50
  • $\begingroup$ I just followed your hint and substitution and showed $3(2m) + 2 = 2(3m+1) = 2j$ is even, and derived the contradiction. $\endgroup$ – Whitecat Mar 5 '13 at 18:59
  • 1
    $\begingroup$ 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? $\endgroup$ – 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?

  • $\begingroup$ I think this is a perfect answer on how to set up the problem. $\endgroup$ – Whitecat Mar 5 '13 at 18:20
  • $\begingroup$ 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$ $\endgroup$ – Whitecat Mar 5 '13 at 18:25
  • $\begingroup$ 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. $\endgroup$ – Namaste Mar 5 '13 at 18:35
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Mar 5 '13 at 18:36
  • 1
    $\begingroup$ @Whitecat: no problem. amWhy's answer is a good one. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Namaste Mar 6 '13 at 4:18

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.