Methods of Proof

Methods of Proof in Discrete Mathematics

In discrete mathematics, proofs are essential tools used to demonstrate the validity of mathematical statements or propositions. The methods of proof provide structured approaches to show that a given statement is true. Below are the primary methods of proof commonly used in mathematics:

---

1. Direct Proof

A direct proof is the most straightforward method of proving a statement. In a direct proof, we assume that the premises (or hypotheses) of the statement are true, and then use logical reasoning to arrive at the conclusion.

Steps of a Direct Proof:

1. Assume the hypotheses (the given conditions of the statement) are true.
2. Use logical steps to derive the conclusion directly from these assumptions.
3. Conclude that the statement is true because the conclusion follows logically from the premises.

Example:

Statement: If $n$ is an even integer, then $n^2$ is even.

Proof:
Assume $n$ is an even integer. By definition of an even integer, we can write $n = 2k$, where $k$ is an integer.
Now, calculate $n^2$:

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

Since $n^2$ is of the form $2 \times$ (an integer), it is even. Therefore, $n^2$ is even.

Thus, the statement is proven by direct proof.

---

2. Proof by Contradiction (Reductio ad Absurdum)

Proof by contradiction is a method where we assume that the statement to be proven is false and then show that this assumption leads to a contradiction. Since the assumption of falsity leads to an inconsistency, it must be that the original statement is true.

Steps of Proof by Contradiction:

1. Assume the negation of the statement you want to prove.
2. Show that this assumption leads to a contradiction, an impossible or inconsistent situation.
3. Conclude that the assumption must be false, and therefore the original statement must be true.

Example:

Statement: $\sqrt{2}$ is irrational.

Proof:
Assume, for the sake of contradiction, that $\sqrt{2}$ is rational. That means we can express $\sqrt{2}$ as a fraction $\frac{a}{b}$, where $a$ and $b$ are integers with no common factors (i.e., $\frac{a}{b}$ is in its simplest form).

$$\sqrt{2} = \frac{a}{b} \quad \Rightarrow \quad 2 = \frac{a^2}{b^2} \quad \Rightarrow \quad a^2 = 2b^2$$

This implies that $a^2$ is even (since it is divisible by 2). Therefore, $a$ must also be even (since the square of an odd number is odd). Let $a = 2k$ for some integer $k$. Substituting into the equation $a^2 = 2b^2$, we get:

$$(2k)^2 = 2b^2 \quad \Rightarrow \quad 4k^2 = 2b^2 \quad \Rightarrow \quad 2k^2 = b^2$$

This implies that $b^2$ is even, so $b$ must be even as well. But this contradicts the assumption that $a$ and $b$ have no common factors, because both are divisible by 2.

Therefore, our assumption that $\sqrt{2}$ is rational must be false. Hence, $\sqrt{2}$ is irrational.

---

3. Proof by Contrapositive

A contrapositive proof is a proof that involves proving the contrapositive of an implication. The contrapositive of a statement of the form "If $p$, then $q$" is "If not $q$, then not $p$."

The contrapositive is logically equivalent to the original statement, meaning proving one proves the other.

Steps of Proof by Contrapositive:

1. Reformulate the statement to its contrapositive form.
2. Prove the contrapositive directly.
3. Conclude that since the contrapositive is true, the original statement is true.

Example:

Statement: If $n$ is an odd integer, then $n^2$ is odd.

Proof:
The contrapositive of this statement is: "If $n^2$ is not odd (i.e., $n^2$ is even), then $n$ is not odd (i.e., $n$ is even)."
Now, we prove the contrapositive:

• Assume $n^2$ is even. This means there exists an integer $k$ such that $n^2 = 2k$.
• Since $n^2$ is even, $n$ must also be even (because the square of an odd number is odd).
• Thus, $n$ is even.

Since the contrapositive is true, the original statement is also true. Therefore, if $n$ is odd, then $n^2$ is odd.

---

4. Proof by Induction

Mathematical induction is a powerful proof technique used to prove statements that hold for all natural numbers. The process consists of two main steps:

Steps of Proof by Induction:

1. Base case: Prove that the statement holds for the smallest value of $n$, typically $n = 1$ or $n = 0$.
2. Inductive step: Assume the statement is true for some arbitrary integer $n = k$, and then prove that it must also hold for $n = k + 1$.

If both steps are proven, the statement holds for all natural numbers greater than or equal to the base case.

Example:

Statement: $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$, for all $n \in \mathbb{N}$.

Proof:

• Base case: For $n = 1$, we have:

  $$1 = \frac{1(1+1)}{2} = \frac{1 \times 2}{2} = 1$$

  The base case holds.

• Inductive step: Assume that the formula holds for some arbitrary $k$, i.e.,

  $$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

  We need to prove that the formula holds for $k + 1$, i.e.,

  $$1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$$

  Starting from the inductive hypothesis:

  $$1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

  Factor out $(k+1)$:

  $$= (k+1)\left(\frac{k}{2} + 1\right) = (k+1)\left(\frac{k+2}{2}\right)$$

  Simplifying:

  $$= \frac{(k+1)(k+2)}{2}$$

  Therefore, the formula holds for $k + 1$. By the principle of mathematical induction, the statement is true for all natural numbers $n$.

---

5. Proof by Exhaustion (Case Analysis)

In proof by exhaustion, we break the statement into several cases and prove each case separately. This method is useful when a statement depends on different possibilities, and each possibility needs to be verified.

Steps of Proof by Exhaustion:

1. Identify all possible cases of the statement.
2. Prove the statement for each case.
3. Conclude that the statement is true for all cases.

Example:

Statement: A triangle with side lengths 3, 4, and 5 is a right triangle.

Proof:

• Case 1: If the triangle has side lengths 3, 4, and 5, we check if it satisfies the Pythagorean theorem: $$3^2 + 4^2 = 9 + 16 = 25 = 5^2$$ Since the Pythagorean theorem holds, the triangle is a right triangle.

Thus, the statement is proven.

---

Conclusion

Different methods of proof are essential tools in mathematics to establish the truth of various statements. Each method—direct proof, proof by contradiction, proof by contrapositive, proof by induction, proof by exhaustion—serves a unique purpose and can be applied to different types of mathematical problems. Mastery of these techniques is crucial for solving problems and proving theore