Direct Proof by Contraposition

Definition

$p\to q\equiv \neg q\to \neg p$ If we can prove that the negation

Example: Prove that for any integer $n$ if $3n+2$ is odd, then $n$ is odd.

This theorem is of the form $p\to q$. What is $p$ and $q$?

$p$: $3n+2$ is odd. $q$: $n$ is odd.

Contrapositive $\neg q\to \neg p$

$\neg q$: $n$ is even. $\neg p$: $3n+2$ is even.

Proof: Assume $n$ is even. Therefore, $n=2k$, where $k$ is an integer. Now,

$$\begin{array}{r}3n+2\\ \equiv <substitution>\\ 3(2k)+2\\ \equiv <algebra>\\ 6k+2\\ \equiv <algebra>\\ 2(3k+1)\\ \equiv <substitution>\\ 2j\end{array}$$

Since $j$ is an integer, $3n+2$ is even. Therefore, $\neg q\to \neg p$. Therefore $p\to q$.