Introduction to Proof Techniques

Mathematical notation

Link to latex symbols

Relations

There are a number of mathematical relations we may deal with in this course

$\equiv$ is equivalent to
$<$ less than
$\leq$ less than or equal to
$\subset$ is a proper subset of
$\subseteq$ is a subset of
$\sim$ is similar to
$\approx$ is approximately
$\propto$ is proportional to
$\neq$ is not equal to

Binary and Logical Operators

These will be used throughout the course.

$\cap$ set intersection
$\cup$ set union
$\wedge$ logical and
$$\lor$ logical or
$\land$ exists
$\nexists$ does not exist
$\forall$ for all
$\neg$ logical not
$\Rightarrow$ right implication
$\Leftarrow$ left implication
$\Leftrightarrow$ equivalence
$\rightarrow$ implies

Numeric sets

When talking about numbers, it can be useful to use set notation

$\mathbb{N}$ Natural numbers or the positive integers
$\mathbb{N}^0$ non negative integers (natural numbers and 0)
$\mathbb{Z}$ Integers
$\mathbb{Q}$ rational numbers
$\mathbb{R}$ Real numbers

Types of Proofs

Direct Proofs

When trying to prove $p\rightarrow q$ assume p and prove that q must be true

Example

Theorem: if x is divisible by 4, it must be divisible by 2.

Since x is divisible by 4, it can be written as 4k for some integer k.

Since 4 is equal to 2 times 2, 4k can be written as $2\times2\times k$ which is clearly divisible by 2.

Proof by Contradiction

When trying to prove $p\rightarrow q$ assume p and $\neg q$ and prove that there is a contradiction

Example

Theorem: $\sqrt{2}$ is irrational

Proof: Assume that $\sqrt{2}$ is rational.

Then it can be written as $\frac{p}{q}$ for coprime integers $p,q\in\mathbb{N}$ by definition of a rational number.

Then by squaring both sides we have $2=\frac{p^2}{q^2}$.

Rearranging, we get that $2q^2=p^2$. Therefore p must be even (see below). Therefore we can write p=2k for some integer k.

Then we have $2q^2=(2k)^2=4k^2$ or $q^2=2k^2$. By similar logic, q must be even. However this means both p and q are divisible by 2, contradicting our assumption that p and q are coprime.

Proof by Contrapositive

When trying to prove $p\rightarrow q$ assume $\not q$ and prove $\not p$

Example

Theorem: $\forall n\in\mathbb{N}$, if $n^2$ is even, $n$ must be even (used above)

Proof: Let $n$ be odd, then $n=2k+1$ for some integer $k$.

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

Since $4k^2+4k=4(k^2+k)$, it is divisible by 2. So $n^2$ must be odd.

Therefore if $n$ is odd, $n^2$ is odd.

Therefore by contrapositive if $n^2$ is even, $n$ is even.

Proof by Induction

To prove the theorem is true for all n.

Prove it is true for a simple value (the base case)
Assume it is true for some case k (the inductive hypothesis)
Prove that it is true for case k+1 (inductive step)

Note. The above is week induction. In strong induction we assume it is true for all values up to and including k.

Example

Theorem: $\forall n\in\mathbb{N}$ $n^3+2n$ is divisible by 3.

Proof:

Base case: $n=1$. $n^3+2n=1^3+2(1)=3$ which is divisible by 3.

Inductive hypothesis: For $n=k$, we have that $k^3+2k$ is divisible by 3. This means that $k^3+2k=3m$ for some integer m.

Inductive step: Now we must prove for $n=k+1$, $n^3+2n$ is divisible by 3.

Substituting k+1 for n we have that $n^3+2n=(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2$.

Rearranging, we have that $k^3+3k^2+3k+1+2k+2=(k^3+2k)+(3k^2+3k+1+2)$.

Combining like terms, we have that $(k^3+2k)+(3k^2+3k+1+2)=(k^3+2k)+(3k^2+3k+3)$.

By the inductive hypothesis, we know that $k^3+2k=3m$.

Therefore we have that $(k^3+2k)+(3k^2+3k+3)=3m+3k^2+3k+3=3(m+k^2+k+1)$ which is divisible by 3.

Proof by Exhaustion

To show the theorem must be true, exhaustively demonstrate it is true in all cases

Example

Theorem: $\forall x\in\mathbb{R}$ if $x\leq-2$ or $x\geq2$ then $\lvert x\rvert\geq 2$

Proof: x must be either less than or equal to -2 (case 1) or greater than or equal to 2 (case 2)

case 1: If x is less than or equal to -2, then by definition of absolute value, $\lvert x\rvert=-x\geq2$

case 2: If x is greater than or equal to 2, then by definition of absolute value, $\lvert x\rvert=x\geq2$

Since these cases are exhaustive, and in all cases $\lvert x\rvert\geq 2$, we have shown that $\forall x\in\mathbb{R}$ if $x\leq-2$ or $x\geq2$ then $\lvert x\rvert\geq 2$.

Proof by Construction

To show the theorem is true, build the structure that proves it true.

Theorem: Given 2 L-shaped pieces ($2\times2$ square with one block removed), one can fill a $2\times3$ board with no overlap.

Proof: Construction left to the reader

Example

Theorem:

Proof by Combinatorics

Prove the number of cases through efficient counting techniques.

Example

Theorem: There are 90 2-digit numbers in base 10

Proof: There are 9 possible numbers for the first digit (1-9) and 10 possible numbers for the second digit (0-9) all of which will lead to unique numbers. Therefore there are $9\times10=90$ 2-digit numbers in base 10.

(dis)Proof by Counterexample

Prove that the theorem is false by providing a counterexample.

Example

Theorem: All numbers that are divisible by 2 are divisible by 4.

Counterexample: 6 is divisible by 2, but not by 4.