# Proof Techniques

These lecture notes are mainly based on Rosen's (2011) *Discrete Mathematics and its Applications 7th Edition*.

## Propositions, Theorems, Axioms, Lemmas, Corollaries, and Conjectures

**Theorems** are basically **propositions**. By convention, we usually call important propositions as theorems. Theorems' truthfulness are evaluated using **proofs**. Proofs are valid arguments that can contain previously proven theorems or **axioms** (sometimes called **postulates**). Axioms are self evident statements we assume to be true. Less important theorems that are useful for other theorems are called **lemmas**. To summarize complicated proofs, it is usually proven using multiple lemmas. **Corollaries** are theorems that can be derived from a proven theorem. A **conjecture** is a statement that is proposed to be true due to partial evidence.

## Statements hiding quantifications

Consider the statement:

- "if $x>y$ , (where $x$ and $y$ are positive real numbers ) then $x^2 > y^2$"

Although it is not obvious, this statement asserts that these equalities will hold true for all positive real numbers since the statement uses **arbitrary** positive real numbers ($x$ and $y$). This means that the statement above can be expressed as the quantification (via the rule of universal generalization):
$$
\forall x \forall y (x>y \to x^2>y^2) \tag{where $x$ and $y$ are positive real numbers}
$$

On the other hand the statement:

- $15 = 2k +1$ for some integer $k$.

asserts an existential quantification. This statement asserts that the equality $15 = 2k +1$ is true for some **unknown** integer $k$. The assertion doesn't know the exact value of $u$ based on the statement, the assertion just knows that such a value exists. Therefore you can write the statement above as the existential quantification (via existential generalization):
$$
\exists k (15=2k+1) \tag{where $k$ is an integer}
$$
You will notice that quantified mathematical statements don't always explicitly state quantifiers. Instead, statements are written using arbitrary and unknown variables.

## Direct Proof

Given an implication $p \to q$. It can be directly proven by assuming $p$ and demonstrating that $q$ is also true from the assumption.

### Example

- Prove that if any integer $x$ is even then $x^2$ is also even.

Assuming $x$ indeed even. Based on the axioms of integers
$$
\forall x\exists k (x=2k)
$$
This means that
$$
\begin{align*}
(2k)^2&=x^2 \\
4k^2&=x^2 \\
2(2k^2) &= x^2
\end{align*}
$$
Also based on the axioms of integers if $k$ is an integer then $2k^2$ is also an integer. Which means $x^2$ is also even when $x$ is even.

#### Why this works

Direct proofs work based on the definition of implication propositions. Recall that an implication statement can only false if the hypothesis is true and the conclusion is false. Which means that to demonstrate the truthfulness of an implication statement, you only need to demonstrate that $T \to T$.

To prove a an implication statement $p \to q$, the first step is to assume that $p$ is true. Then, based on the assumption $p$ you need to demonstrate that $q$ is true as well. Thus proving $p$ indeed implies $q$.

## Proof by Contraposition

Given any implication statement $p \to q$, this statement can be proven by proving its contrapositive $\neg q \to \neg p$. This is because any implication is equivalent to its contrapositive. Proving that $p \to q$ is true will prove its corollary $\neg q \to \neg p$.

For example:

> Prove that if $x^2$ is even then $x$ is even (where $x$ is an integer)

This statement is equivalent to its contrapositive:

> If $x$ is not even, then $x^2$ is not even

Any non-even integer is an odd, which means this statement is basically:

> If $x$ is odd then $x^2$ is odd or:

> $x=2k+1 \to x^2=2l+1$ for some integers $k$ and $l$

Which can be directly proven from the assumption $x=2k+1$:
$$
\begin{align*}
x&=2k+1 \\
x^2&=(2k +1)^2 \\
x^2&=4k^2+4k+1 \\
x^2&=2(2k^2+2k)+1 \\
\end{align*}
$$
Thus proving: "if $x$ is odd then $x^2$ is odd" and its contrapositive "if $x^2$ even then $x$".

## Proof by Induction

Let's start with a simple example:

**Prove:**
$$
1 + 2 + 3+ ... + n = \frac{n(n+1)}{2}
$$

One acceptable way to prove this proposition is by showing that this is true for all possible values for $n$.
$$
1=\frac{1(1+1)}{2}=1
$$

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

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

$$
...
$$

Instead of doing this one by one for all natural numbers, you can use a neat trick called proof by induction. You can start by proving a **basis** case and arbitrarily prove the remaining cases by induction.

To start the proof, you need to establish a basis by demonstrating the simplest case to be true:

**BASIS**:

Let $n=1$.
$$
1=\frac{1(1+1)}{2}=1
$$

This proves that $1 + 2 + 3+ ... + n = \frac{n(n+1)}{2}$ for $n=1$.

To move on you need to assume that this is also true for an arbitrary value for $n$, $k$:

**ASSUMING:**

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

From this assumption, you need to prove that this is also true for $n=k+1$.
$$
1+2+3+...+k+(k+1)
$$

Based on the assumption, we can substitute, $1+2+3+...+k$ with $\frac{k(k+1)}{2}$:
$$
1+2+3+...+k+(k+1)=\frac{k(k+1)}{2}+k+1
$$

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

Factoring out $(k+1)$ we get:
$$
\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{(k+1)(k+2)}{2}=\frac{(k+1)(k+1+1)}{2}
$$
Thus proving that $1+2+3+...+k+(k+1)=\frac{(k+1)(k+1+1)}{2}$.

But how does performing a proof based on an assumption prove anything? How does this imply $1 + 2 + 3+ ... + n = \frac{n(n+1)}{2}$? Remember that the only thing we have demonstrated in this step is the implication proposition: **if the equality is true for $n=k$, then it is also true $n=k+1$.**

This is where the basis comes into play. Remember that we have demonstrated that the equality is true when $n=1$. Since we have demonstrated that: if the equality is true for $n=k$ is true, then the equality is true for $n=k+1$, this means that the equality is also true when $n=1+1$. And since the equality is true for $n=2$ then it is also true when $n=2+1$. And since the equality is true when $n=3$ then it is also true for $n=3+1$. And so on. These implications cascades for each case, thus proving that the equality is true for all cases.

### Why this works

So to summarize:

Say you need to prove a proposition for all possible cases. You can break apart this proposition into many propositions, one for each case. Using the example above let $p$ be the proposition, "$\forall n\in \mathbb{N},1 + 2 + 3+ ... + n = \frac{n(n+1)}{2}$".

We can break this proposition apart like this:

- $P(1)$ is the proposition $1=\frac{1(1+1)}{2}$
- $P(2)$ is the proposition $1+2=\frac{2(2+1)}{2}$
- $P(3)$ is the proposition $1+2+3=\frac{3(3+1)}{2}$
- an so on..

Or:
$$
p=P(1) \land P(2) \land P(3) \land ...
$$

Instead of demonstrating that each of these propositions as true, you can prove the whole proposition inductively

First you need to demonstrate a:

#### BASIS

> *prove that the proposition is true for one simple case*

This gives you an established true proposition:
$$
P(1)= T
$$
Then by creating an:

#### ASSUMPTION

> assume that the proposition is true for one arbitrary case

$$
\text{assume }P(k) = T
$$

#### INDUCTION

> assuming the assumption is true, demonstrate that the next case is also true

Because of this you establish that:
$$
P(k)\rightarrow P(k+1)= T
$$

This means that if the assumption is indeed true, then the next case is also true.

This proves that the proposition is true for all cases because the then established true basis proposition, $p_0​$ implies that $p_1​$ is true.
$$
P(1)=T
$$

$$
\text{therefore, } P(2) = T \text{ because } P(1)\rightarrow p(2)
$$

$$
\text{therefore, } P(3) = T \text{ because } P(2)\rightarrow p(3)
$$

$$
\text{therefore, } P(4) = T \text{ because } P(3)\rightarrow p(4)
$$

### More examples

#### Proof that $n^2$ is even, if $n$ is even.

This proposition can be written like this:
$$
n=2m\rightarrow n^2=2l
$$

$$
\text{for some }m,n \in \mathbb{N}
$$

1. **BASIS:**

$$
0^2=0
$$

$$
0=2(0)
$$

Therefore the the proposition is true when $n=0$

2. **ASSUMPTION:**

assuming the proposition is true when $n=k$ for some arbitrary even number $k$:
$$
k=2u
$$

$$
k^2=2v
$$

$$
\text{for some } u,v\in \mathbb{N}
$$

3. **INDUCTION**

$$
(k+2)^2 =(2u+2)^2
$$

> From on the assumption, the above can be achieved by substituting $k$ with $2u$.

$$
= 4u^2+8u+4
$$

$$
=2(2u^2+4u+2)
$$

Since $u$ is a natural number, $(2u^2+4u+2)$ is also a natural number (This is true based on the natural number axioms). This makes the expressions $2(2u^2+4u+2)$ an even number.

Therefore, the assumption that $k^2$ is even when $k$ is even implies that $(k+2)^2$ is even when $k+2$ is even.

And since it has been established that $n^2$ is even when $n=0$, this inductively proves that $n^2$ is even for any even number $n$.

#### Proof that $n^2$ is odd, if $n$ is odd.

This proposition can be written like this:
$$
n=2m+1\rightarrow n^2=2l+1
$$

$$
\text{for some }m,n \in \mathbb{N}
$$

1. **BASIS:**

$$
1^2=1
$$

$$
1=2(0)+1
$$

Therefore the the proposition is true when $n=0$

2. **ASSUMPTION:**

assuming the proposition is true when $n=k$ for some arbitrary even number $k$:
$$
k=2u+1
$$

$$
k^2=2v+1
$$

$$
\text{for some } u,v\in \mathbb{N}
$$

3. **INDUCTION**

$$
(k+2)^2 =((2u+1)+2)^2=(2u+3)^2
$$

> From the assumption the above can be achieved by substituting $k$ with $2u+1$.

$$
= 4u^2+12u+9= (4u^2+12u+8)+1
$$

$$
=2(2u^2+6u+4)+1
$$

Since $u$ is a natural number, $(2u^2+6u+4)$ is also a natural number (This is true based on the natural number axioms). This makes the expressions $2(2u^2+6u+4)+1$ an odd number.

Therefore, the assumption that $k^2$ is odd when $k$ is odd implies that $(k+2)^2$ is odd when $k+2$ is odd.

And since it has been established that $n^2$ is odd when $n=1$, this inductively proves that $n^2$ is odd for any odd number $n$.

#### Proof that $9^n - 2^n$ is divisible by 7

This proposition can be written like this:
$$
9^n-2^n=7m
$$

$$
\text{for some }n,m\in \mathbb{N}
$$

1. **BASIS**:

$$
9^1-2^1=7(1)
$$

Therefore the proposition is true when $n=1$

2. **ASSUMPTION**:

assuming the proposition is true when $n=k$ for some arbitrary natural number $k$:
$$
9^k-2^k=7l
$$

$$
\text{for some }l\in \mathbb{N}
$$

3. **INDUCTION**:

$$
9^{k+1}-2^{k+1}=9(9^k)-2(2^k)
$$

$$
=9(7l+2^k)-2(2^k)=63l+9(2^k)-2(2^k)
$$

> From the assumption, the above can be achieved by substituting $9k$ with $7l+2^k$.

$$
=63l+2^k(9-2)=63l+7(2^k)
$$

$$
=7(9l+2^k)
$$

Since $l$ and $k$ are natural numbers, ($9l+2^k$) is also a natural number. And, since $9^k-2^k=7l \rightarrow 9^{k+1}-2^{k+1}=7u$ is true, $9^n - 2^n$ is divisible by $7$ for all any natural number $n$, through induction.

## Strong Induction

You can also prove things using a stronger kind of induction.

#### Proof that any integer is prime or a product of primes

Prove:
$$
\forall n (\exists p(n=p) \lor \exists p_1,p_2,p_3,...(n=p_1p_2p_3...))
$$
where $n$ is an integer greater than $1$ and $p$,$p_1$,$p_2$,$p_3$,... are prime numbers.

1. **BASIS**:
$$
n=2 \tag{since 2 is prime}
$$

2. **ASSUMPTION**:

assuming any proposition $P(k')$ such that $k' \leq k$ is true

3. **INDUCTION**:

The next number $k+1$ can either be prime or composite. If $k+1$ is prime then $P(k+1)$ is automatically true. If $k+1$ is composite then there exists positive integers $a$ and $b$, such that $k+1=ab$ and $1 < a,b <k+1$. Because of this inequality, the propositions, $P(a)$ and $P(b)$ are both true. And because of that the product $ab$ can be expressed as a product of primes (since both $a$ and $b$ are either prime or products of primes from $P(a) \land P(b)$. This means $P(k+1)$ is true when the assumption above is true. Or, $\forall k' \leq k (P(k')) \to P(k+1)$.

### Why Strong induction is as valid as weak induction

Finishing the 3 steps of strong induction above establishes these statements:

- $P(2)$
- $\forall k' \leq k (P(k')) \to P(k+1)$

Using modus ponens, it can be concluded that $P(3)$ is also true. Since both $P(2)$ and $P(3)$ is true (or $\forall k' \leq 3 (P(k'))$ is true), then via modus ponens, P(4) is also true. This cascades infinitely, proving that the statement is indeed true for any integer.

## Proof by Contradiction

Another proof strategy is the use of contradiction. It is also called an indirect proof:

Let's demonstrate using an example. Here we will try to prove that $\sqrt{2}$ is irrational.

Let's start on the assumption that, the proposition "$\sqrt{2}$ is irrational" is false. This assumption implies that $\sqrt{2}$ is rational. Based on the definition of rational numbers we can say that:
$$
\exists~{a,b} : \sqrt{2} =\frac{a}{b}
$$

Where $a$ and $b$ are natural numbers and are coprimes, or that $\frac{a}{b}$ is an irreducible fraction.

We can then derive:
$$
2=\frac{a^2}{b^2}
$$

$$
2b^2=a^2
$$

This means that $a^2$ is an even number. Which means that $a$ is also even (proved earlier by induction). This means that we can replace $a$ with $2n$ (where $n$ is a natural number).
$$
2b^2=(2n)^2=4n^2
$$

$$
\frac{2b^2}{2}=\frac{4n^2}{2}
$$

$$
b^2=2n^2
$$

This would also make both $b^2$ and $b$ even numbers. This demonstrates that $a$ and $b$ are both even. Which implies that $a$ and $b$ cannot be coprimes, since comprimes cannot share common factors and all even numbers are a factor of 2. This implies that $a$ and $b$ are coprimes and $a$ and $b$ are not coprimes. That argument is contradiction which means that the assumption cannot be true. This means that $\sqrt{2}$ is indeed irrational.

### Why this works

So to summarize a proof by contradiction works like this.

Using the example above let $p$ be the proposition "$\sqrt{2}$ is irrational". To prove the proposition $p$, you start by assuming, $\neg p$ is true. In this case $\neg p$ is the proposition "$\sqrt{2}$ is rational".

Through implication the assumption led us to the proposition "$a$ and $b$ are coprimes". Lets call this proposition $q$.
$$
\neg p\to q
$$
We also demonstrate that "$a$ and $b$ are not coprimes", which is basically the proposition $\neg q$.
$$
\neg p\to \neg q
$$
This means that:
$$
\neg p \to (q \land \neg q)
$$
The proposition $(q \land \neg q)$ is a contradiction. It cannot be true. This means that
$$
\neg p \to F
$$
And via modus tollens, this means that the assumption $\neg p$ is false. Which means that $p$ is in fact true.

### Another Example

Prove that there are infinite primes.

To prove this lets assume that there is a finite amount of primes. This means that there exists a prime number $n_k$ at the end of the series of primes. This means that there exists no prime number greater that $n_k$:
$$
n_1=2,n_2=3,n_3=5,...,n_k: n_i \in \mathbb{P}
$$
$$
\nexists~m:m>n_k,m\in\mathbb{P}
$$

From this, let $z$ be the product of all primes plus $1$:
$$
z=n_1n_2n_3...n_k+1
$$

This means that $z$ is a number that is not divisible by any of the primes in the series of primes, $n_1,n_2,n_3,...n_k$. This is because for any number $au$ where both $a$ and $u$ are integers, the next multiple of $au$ (the smallest multiple of $a$ greater than $au$) is $au+a$. Which also means that $au+b$ for any $0<b<a$ is not divisible by $a$.

This implies one of two things, either $z$ is indeed prime (having more than 2 divisors), or $z$ is composite. And if $z$ is composite there exists a prime number $m>n_k$, where $z=mu$. Both of these situations provide us with a contradiction since, if $z$ is prime then, $z>n_k$ otherwise $z$ is composite, and the series is incomplete. Both of these contradicts the proposition, $\nexists~m:m>n_k,m\in\mathbb{P}$.

Therefore, there are indeed infinite primes.

## Additional Proof Techniques

### Proof by example and counter example

Given an existentially quantified statement
$$
\exists x P(x)
$$
Based on the rule of existential generalization, given $P(c)$ , you can conclude that $\exists x P(x)$. By showing $P(c)$ is true, you will prove that $\exists x P(x)$ is also true.

For example:

> Prove that there exists a solution for the equation $x^2 + y^2 =z^2$.

This can be expressed as the quantified solution:
$$
\exists x \exists y \exists z(x^2+y^2=z^2)
$$
This can be proven by showing the example:
$$
3^2+4^2=9+16=25=5^2
$$
The proof by example technique can also be used to prove universal quantifications which has domains with few enough members. For example
$$
\forall x(x\leq 3 \to (x+1)^3 \geq 3^x) \tag{where $x$ is a positive integer}
$$
This can be expressed as the restricted quantification:
$$
\forall x\leq 3((x+1)^3 \geq 3^x) \tag{where $x$ is a positive integer}
$$
Notice that the only members in this restricted domain are the integers, $1$, $2$, and $3$. This means that this can be proven by showing $P(1) \land P(2) \land P(3)$. This technique is also called an exhaustive proof.
$$
\begin{align*}
(1+1)^3&=8 \\
3^1&=3\\
8&\geq3 \tag{proves $P(1)$}\\
\\
(2+1)^3&=27 \\
3^2&=9\\
27&\geq9 \tag{proves $P(2)$}\\
\\
(3+1)^3&=64 \\
3^3&=27\\
64&\geq27 \tag{proves $P(3)$}
\end{align*}
$$
You can also use the same principle to disprove universal quantifications. This can be done because a universal quantification is false if at least one of the members of its domain makes its predicate false. For example to prove that the statement below is false:
$$
\forall x \exists u \exists v(x=u^2+v^2) \tag{where $x$,$u$, and $v$ are integers}
$$
You need to provide a counterexample. Which means you need to find a value for $x$ such that there is no $u$ and $v$ that makes the equality true. One counterexample for this is $3$. The integer $3$ can be expressed as a sum of 2 integers in exactly $2$ ways: $3=0+3$ and $3=1+2$. None of these sums are sums of 2 perfect squares. Therefore, the integer $3$ cannot be written as a sum of two perfect squares, disproving the assertion: $\forall x \exists u \exists v(x=u^2+v^2)$.

### Uniqueness proof

A uniquely quantified statement:
$$
\exists! xP(x)
$$
Can be expressed as the statement:
$$
\exists x(P(x) \land \forall z \neq x(\neg P(z)))
$$
To prove statements that come in this form you need prove that the exact value for $x$ such that the predicate is false and you need to prove that for all values besides $x$ the predicate is false.

For example:

>There exists exactly one even prime number.

The number $2$ is even and it has exactly two factors (1 and 2), which means 2 is both even and prime. Every other prime number cannot be even. Since even numbers greater than $2$ has at least three factors, (1, 2 and itself). Which means all even numbers greater than two are composite. Thus proving 2 can only be the even prime number.