1.7 Simple Deductive Proof
1. The Difference Between Symbols = and $\equiv$
Consider the relation $3x = 6$. It holds only for a particular value $x=2$. This is an Equation.
Consider the relation $2(x+3) \equiv 2x+6$. It holds for any value of x. This is an Identity.
The symbol $\equiv$ emphasizes this "stronger" relation.
Example: It is easy to check that $\frac{1}{4} + \frac{1}{12} = \frac{1}{3}$. This is a specific instance of the general identity:
2. Proof of an Equality (or Identity)
To prove $A = B$, three techniques are commonly used:
- Method A: Start from LHS $\rightarrow$ ... $\rightarrow$ RHS.
- Method B: Work independently: LHS $\rightarrow$ ... $\rightarrow$ C and RHS $\rightarrow$ ... $\rightarrow$ C.
- Method C: Use equivalence: $A=B \Leftrightarrow \dots \Leftrightarrow \text{True Statement}$.
Method A Example
Prove $(a+b)^3 \equiv a^3 + 3a^2b + 3ab^2 + b^3$.
Proof: Start from LHS:
$= (a^2+2ab+b^2)(a+b)$
$= a^3 + a^2b + 2a^2b + 2ab^2 + ab^2 + b^3$
$= a^3 + 3a^2b + 3ab^2 + b^3$ (= RHS).
Method B Example
Prove $(2a+b)^2 - 4a^2 - b^2 \equiv (a+b)^2 - (a-b)^2$.
Proof:
RHS $= (a^2 + 2ab + b^2) - (a^2 - 2ab + b^2) = 4ab$
Therefore, LHS = RHS.
Method C Example
Given $a \ne \pm b$, show that $\frac{a-2b}{a-b} \equiv \frac{a^2-ab-2b^2}{a^2-b^2}$.
Proof:
$\Leftrightarrow (a-2b)(a^2-b^2) = (a-b)(a^2-ab-2b^2)$
$\Leftrightarrow a^3 - ab^2 - 2a^2b + 2b^3 = a^3 - a^2b - 2ab^2 - a^2b + ab^2 + 2b^3$
$\Leftrightarrow 0 = 0$ (True).
EXAMPLE 1
Prove $\frac{1}{m+1} + \frac{1}{m^2+m} \equiv \frac{1}{m}$.
Solution: From LHS to RHS.
$= \frac{m}{m(m+1)} + \frac{1}{m(m+1)}$
$= \frac{m+1}{m(m+1)}$
$= \frac{1}{m}$ (= RHS).
EXAMPLE 2 & 3
Work from RHS: $2(x^2 - 6x + 9) + 1 = 2x^2 - 12x + 18 + 1 = 2x^2 - 12x + 19$.
Expand RHS: $a(x^2 - 2bx + b^2) + c = ax^2 - 2abx + (ab^2 + c)$.
Compare coefficients:
1. $a = 2$
2. $-2ab = -12 \Rightarrow -4b = -12 \Rightarrow b = 3$
3. $ab^2 + c = 19 \Rightarrow 2(9) + c = 19 \Rightarrow c = 1$.
1.8 Methods of Proof (HL)
1. Converse and Contrapositive
For a statement of the form "If A then B":
- Converse: If B then A (Not necessarily true)
- Contrapositive: If not B then not A (Always equivalent to the original statement)
Examples
| Original | If $x=1$ then $x^2=1$ | [True] |
| Converse | If $x^2=1$ then $x=1$ | [False] |
| Contrapositive | If $x^2 \ne 1$ then $x \ne 1$ | [True] |
2. Three Methods of Proof
We use a simple example: Let X be the name of a city.
1. Deductive Proof
Start from the hypothesis and use logical steps to reach the result.
Statement: If X is a Greek city, then X is a European city.
Proof: Assume X is a Greek city. Greece is part of Europe. Therefore, X is a European city.
2. Proof by Counterexample
Used to establish that a statement is not true.
Statement: If X is a European city, then X is a Greek city.
Proof: Select Rome. It is a European city but not in Greece. Hence the statement is false.
3. Proof by Contradiction
Assume the result is false, and deduce a contradiction.
Statement: If X is a non-European city, then it is not a Greek city.
Proof: Let X be a non-European city. Assume the result is false (i.e., X is a Greek city). But then X would be a European city! Contradiction. Thus, X is not a Greek city.
3. Mathematical Examples
Deduction: Even Numbers
Show: If $a$ is even then $a^2$ is even.
Proof: $a$ is even $\Rightarrow a=2n$.
$a^2 = (2n)^2 = 4n^2 = 2(2n^2)$.
Therefore $a^2$ is a multiple of 2 (even).
Counterexample: Multiples of 4
Statement: If $a^2$ is a multiple of 4, then $a$ is a multiple of 4.
Proof: Choose $a=6$. Then $a^2 = 36$, which is a multiple of 4. However, 6 is not a multiple of 4. The statement is false.
Contradiction: Irrationality of $\sqrt{2}$
Show: $\sqrt{2}$ is irrational.
Proof: Assume $\sqrt{2}$ is rational, i.e., $\sqrt{2} = \frac{a}{b}$ where $a, b$ are coprime integers.
- $a = \sqrt{2}b \Rightarrow a^2 = 2b^2$. Thus $a^2$ is even, so $a$ is even ($a=2c$).
- Substitute back: $(2c)^2 = 2b^2 \Rightarrow 4c^2 = 2b^2 \Rightarrow b^2 = 2c^2$.
- Thus $b^2$ is even, so $b$ is even.
- If $a$ and $b$ are both even, they are not coprime. Contradiction.
Contradiction: Integer Solutions
Show: The equation $6x + 15y = 100$ has no integer solutions.
Proof: Assume it has an integer solution $(x,y)$.
LHS $= 3(2x + 5y)$ is a multiple of 3.
RHS $= 100$ is not a multiple of 3.
Contradiction. No integer solutions exist.
The Pigeonhole Principle (Contradiction)
Suppose $n+1$ pigeons are placed in $n$ pigeonholes. There exists a pigeonhole with at least 2 pigeons.
Proof: Assume all pigeonholes have at most 1 pigeon. Total pigeons $\le n$. Contradiction (since we have $n+1$).
Example: Suppose 64 pigeons are placed in 7 pigeonholes. Show some pigeonhole contains at least 10 pigeons.
Proof: Assume all pigeonholes have at most 9 pigeons. Total pigeons $\le 7 \times 9 = 63$. Contradiction (since we have 64).