Proof Techniques

A mathematical proof is an Inferential argument for a mathematical statement. It uses previously established statements, such as theorems, and follows logically sound rules. In mathematics, we are not looking for “evidence” (as in science), but for absolute certainty.

Direct Proof

In a direct proof, we assume $P$ is true and use logic to show that $Q$ must follow.

Example: Prove that if $n$ is an even integer, then $n^2$ is even.

1. Assume $n$ is even. By definition, $n = 2k$ for some integer $k$.
2. Square both sides: $n^2 = (2k)^2 = 4k^2$.
3. Rewrite the result: $n^2 = 2(2k^2)$.
4. Since $2k^2$ is an integer, $n^2$ is in the form $2m$, and thus $n^2$ is even.

Proof by Contradiction

To prove $P$, we assume $P$ is false and show that this leads to an impossible logical contradiction ($0 = 1$ or $x \neq x$).

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

1. Assume $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{a}{b}$ in lowest terms.
2. $2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$.
3. This means $a^2$ is even, so $a$ must be even ($a = 2k$).
4. $(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies 2k^2 = b^2$.
5. This means $b^2$ is even, so $b$ must be even.
6. Contradiction: If both $a$ and $b$ are even, the fraction was not in lowest terms. Thus, the original assumption must be false.

Mathematical Induction

Induction is like a row of falling dominoes. To prove a statement $P(n)$ is true for all $n \geq 1$:

1. Base Case: Prove $P(1)$ is true.
2. Inductive Step: Assume $P(k)$ is true (the “Inductive Hypothesis”) and show that $P(k+1)$ must be true.

Let’s test the formula for the sum of the first $n$ integers: $\sum_{i=1}^n i = \frac{n(n+1)}{2}$.

# Testing the Sum Formula: n(n+1)/2
def sum_formula(n):
  return n * (n + 1) // 2

def sum_manual(n):
  return sum(range(1, n + 1))

# Let's check if they match for various n
n_values = [1, 10, 100, 1000]
results = {n: (sum_manual(n) == sum_formula(n)) for n in n_values}

print("Results for various n:")
for n, correct in results.items():
  print(f"n={n}: Match? {correct}")

By proving the inductive step, we show that if it works for $k$, it guarantees work for $k+1$, creating an infinite chain of truth.

Exercises