Appendix 1 — Proofs in Mathematics

The Purpose of Proofs

A proof transforms a guess or a pattern into an unshakable truth. It is a logical chain of reasoning that starts from accepted statements (axioms, definitions, or previously proven theorems) and, through valid steps, arrives at a new statement (the theorem).

---

Key Types of Proofs Covered

Three fundamental proof techniques, each a different tool for establishing truth.

1. Direct Proof

Assume the hypothesis (the "if" part) is true, then use logical deductions to show the conclusion (the "then" part) must also be true.

Structure: If $P$ is true, then $Q$ is true.

Example: Prove that the product of two even integers is even.

• Let $a$ and $b$ be even integers, so $a = 2m$ and $b = 2n$ for some integers $m, n$.
• Their product is $a \times b = (2m)(2n) = 4mn = 2(2mn)$.
• Since $2mn$ is an integer, $a \times b$ is of the form $2 \times (\text{integer})$, hence even.

2. Proof by Contradiction

Assume the opposite of what you want to prove (the conclusion is false) and show this leads to a contradiction. Since the assumption is impossible, the original statement must be true.

Structure: To prove $P \Rightarrow Q$, assume $P$ true and $Q$ false, derive a contradiction; therefore $Q$ must be true.

Example: Prove that $\sqrt{2}$ is irrational.

• Assume $\sqrt{2}$ is rational: $\sqrt{2} = \frac{p}{q}$ in lowest terms ($p, q$ integers with no common factor, $q \neq 0$).
• Squaring: $2 = \frac{p^2}{q^2}$, so $p^2 = 2q^2$. Then $p^2$ is even, so $p$ is even; let $p = 2r$.
• Substitute: $4r^2 = 2q^2 \Rightarrow q^2 = 2r^2$, so $q^2$ is even, hence $q$ is even.
• But then $p$ and $q$ share the factor $2$, contradicting "lowest terms."
• Therefore the assumption is false, and $\sqrt{2}$ is irrational.

3. Proof by Induction

Used to prove a statement claimed true for all natural numbers $n$. It works like a row of dominoes: knock over the first, and let each one knock over the next.

Structure: To prove $P(n)$ for all $n \in \mathbb{N}$:

1. Base Case: Show $P(1)$ is true.
2. Inductive Step: Assume $P(k)$ is true (the induction hypothesis), and use it to prove $P(k+1)$.

Example: Prove that $P(n): 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$. …