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?
Best Answer
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.
Added:
For a general discussion about how the differences and similarities between the two proof strategies, you might want to read an earlier MSE post: