Proof Methods: Direct Proof, Indirect Proof, and Proof by Contradiction

A. Definitions of Proof Methods

i. Direct Proof

Direct Proof is a method where we assume the hypothesis $p$ is true and use logical steps, definitions, and theorems to directly show that the conclusion $q$ is true.

• Structure: Assume $p$ → use logical reasoning → conclude $q$
• We move forward from hypothesis to conclusion in a straight path

ii. Indirect Proof (Proof by Contrapositive)

Indirect Proof is a method where instead of proving $p \rightarrow q$, we prove its contrapositive $\neg q \rightarrow \neg p$, which is logically equivalent.

• Structure: Assume $\neg q$ → use logical reasoning → conclude $\neg p$
• Since $p \rightarrow q \equiv \neg q \rightarrow \neg p$, proving the contrapositive proves the original statement

iii. Proof by Contradiction

Proof by Contradiction is a method where we assume the negation of what we want to prove, and then show that this assumption leads to a logical contradiction.

• Structure: Assume $\neg(p \rightarrow q)$, i.e., assume $p \land \neg q$ → derive a contradiction → conclude $p \rightarrow q$ must be true
• Also called Reductio ad Absurdum

---

B. Direct Proof: "If $n$ is an odd integer, then $n^2$ is an odd integer"

Proof:

• Assume $n$ is an odd integer
• By definition of odd, $n = 2k + 1$ for some integer $k$
• Now compute $n^2$:

$$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$$

$$n^2 = 2(2k^2 + 2k) + 1$$

• Let $m = 2k^2 + 2k$, which is an integer
• So $n^2 = 2m + 1$, which is of the form of an odd integer

Conclusion: Therefore, $n^2$ is odd. $\blacksquare$

---

C. Indirect Proof: "If $n$ is an integer and $n^2$ is odd, then $n$ is odd"

Proof (by Contrapositive):

• The contrapositive of the statement is: "If $n$ is not odd (i.e., $n$ is even), then $n^2$ is not odd (i.e., $n^2$ is even)"
• Assume $n$ is even
• By definition of even, $n = 2k$ for some integer $k$
• Now compute $n^2$:

$$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$

• Let $m = 2k^2$, which is an integer
• So $n^2 = 2m$, which is of the form of an even integer
• Therefore, $n^2$ is even (not odd)

Conclusion: Since the contrapositive is true, the original statement "If $n^2$ is odd, then $n$ is odd" is also true. $\blacksquare$

---

Summary Table

Method	What we assume	What we show
Direct Proof	$p$ is true	$q$ is true
Indirect Proof	$\neg q$ is true	$\neg p$ is true
Contradiction	$p \land \neg q$	A contradiction arises