Proof Techniques

Abigail Huettig

11 Proof Techniques

As we mentioned before, proofs are critical in the realm of mathematics so it is important to know how to properly prove a statement by using the correct method. There are five techniques that we will be discussing.

Direct Proofs: A direct proof is appropriate when we can reach the conclusion directly from the assumption through a series of logical steps. We start with the assumption itself then show through logical steps that the conclusion must be true. Proofs in a high-school geometry course usually follow this format.
Contraposition: This method of proof proves the statement by proving the contrapositive of the statement. This is appropriate when it is easier to prove the contrapositive than it is to prove the original statement.
Indirect Proofs: An indirect proof can also be referred to as a proof of contradiction. With this method, we assume that our statement $A$ is not true then show through a series of logical steps that we reach a contradiction. Because of the contradiction, our assumption has been shown to be false which proves that the original statement is in fact true. This method is appropriate when it is easier to show that $A$ is true through this contradiction method than it is to prove the statement directly.
Mathematical Induction: Mathematical induction is an interesting proof method that consists of two steps, the basis step and the inductive step. This method is useful when proving statements about the integers [22]. Proofs relating to sequences and series usually use this method.
Proof by Cases: Proof by cases is a proof that is broken into smaller pieces that are then proved individually. This is appropriate when it is necessary (or perhaps easier) to prove individual parts rather than the whole at one time.

We will now explore each of these in depth in the following sections.

Direct Proofs

In a direct proof, we start with our assumption and work through a series of logical steps to reach what we are trying to prove, taking a straight path from start to finish. We do not have to go one of the roundabout ways such as proving the contrapositive or proving by contradiction. Whenever we need to prove a statement, we should first look at the direct proof method and see if it will work as this is the most straightforward of the proof techniques. There is no need to make the process more complicated than it needs to be.

Let’s look at an example to have a better idea of what a direct proof actually looks like. This proof is a homework problem I completed for Number Theory and comes from Rosen [22]. Keep in mind that an integer $a$ divides an integer $b$ , denoted as $a|b$ , if and only if there exists an integer $c$ such that $ac=b$ .

Example 22
Show that if $a$ , $b$ , and $c$ are integers not equal to zero and $a\,|\,b$ , then $ac\,|\,bc.$

Proof.
We are given that $a$ is a divisor of $b$ . This means that there is an integer $d$ such that

$\begin{align*} ad&=b &&\text{Definition of divides}\\ adc&=bc &&\text{Multiply both sides by $c\neq 0$}\\ (ac)d&=bc &&\text{Commutative and associative properties}\\ \end{align*}$

Thus, $ac$ is a divisor of $bc$ . Therefore, $ac\,|\,bc$ .

Notice how we started with what we were given and followed clear, logical steps to our conclusion.

Sometimes, a direct proof is not the best method. It may be easier to prove the contrapositive.

Contraposition

For the statement “if $A$ , then $B$ ,” the contrapositive statement is “if not $B$ , then not $A$ .”
In essence, the proof method of contraposition consists of proving the contrapositive of the statement rather than the statement itself. The reason why this method works is that a statement and its contrapositive are equivalent. This is proven by contradiction in the following section.

The proof that we will look at to demonstrate the contrapositive method is one I completed for Introduction to Analysis which is a homework problem from Abbott [1]. To help clarify the logic, the theorem used in the proof is given by Abbott as follows [1].

Theorem II.2

If the series $\sum_{k=1}^{\infty} a_k$ converges, then the sequence $(a_k)$ converges to zero.

Additionally, Definition IV.14 from chapter 20 is also used.

Example 23
Show that if $a_n>0$ for all $n$ and $(na_n)$ converges to $\ell$ with $\ell\neq 0$ , then the series $\sum a_n$ diverges by showing that if the series $\sum a_n$ converges, then either there exists $n$ such that $a_n\leq 0$ or $(na_n)$ converges to 0.

Proof.
By Theorem II.2, $(a_n)$ converges to 0 since $\sum a_n$ converges. By Definition IV.14, for $\epsilon >$ 0, $\exists\,\, N \in \mathbb{N}$ such that when $n\geq N$ ,

$\begin{align*} \frac{\epsilon}{n} &>|a_n|\\ \epsilon &>n|a_n|\\ &=|na_n| \end{align*}$

Thus, $(na_n)$ converges to 0 by Definition IV.14. Therefore, if $a_n>0$ for all $n$ and $(na_n)$ converges to $\ell$ with $\ell\neq 0$ , then the series $\sum a_n$ diverges, using proof by contraposition.

Indirect Proofs (Proofs by Contradiction)

An indirect proof, or proof by contradiction, works well when proving that an implication $A\Rightarrow B$ is true. The method is to assume that the implication is false. Recall from the truth table in chapter 10 that the only possible way for the implication $A\Rightarrow B$ to be false is if there is an instance where $A$ is true but $B$ is false. Thus, we begin the contradiction method by assuming that $A$ is true and $B$ is false. Then, we show (usually directly) that we reach $C\wedge \neg C$ for some other statement $C$ when this assumption is true. Because it is a logical impossibility to have $C\wedge \neg C$ , we know that our assumption cannot possibly be true. Since our assumption is the only possible way that the original implication $A\Rightarrow B$ could be false, we have shown that the implication must be true.

The following homework problem from Abbott, which I completed for Introduction to Analysis, demonstrates this [1].

Example 24
Show that if $a\in\mathbb{Q}$ and $t\in\mathbb{I}$ , then $a+t\in\mathbb{I}$ .

Proof.
Suppose there exists $a\in\mathbb{Q}$ and $t\in\mathbb{I}$ such that $a+t=x$ where $x\notin\mathbb{I}$ . This implies that $x\in\mathbb{Q}$ since a real number must either be rational or irrational. Because $\mathbb{Q}$ is closed under addition, $t=x-a\in\mathbb{Q}$ . This contradicts $t\in\mathbb{I}$ . By this contradiction, $a+t\in\mathbb{I}$ if $a\in\mathbb{Q}$ and $t\in\mathbb{I}$ .

In the last section, we mentioned that a statement and its contrapositive are logically equivalent. This next proof that I wrote will show us the reasoning behind the contrapositve method.

Example 25
Show that $\neg B \Rightarrow \neg A$ if and only if $A \Rightarrow B$ .

Proof.
Because this is an if and only if statement, we must prove it in two parts. The first part is to show that if $\neg B \Rightarrow \neg A$ then $A \Rightarrow B$ . The second part is to show that if $A \Rightarrow B$ then $\neg B \Rightarrow \neg A$ .To prove the first part, suppose that $\neg B \Rightarrow \neg A$ true but $A \Rightarrow B$ is false. The only way that the implication can be false is if $A$ is true and $B$ is not so we have $A\wedge \neg B$ . But, $\neg B \Rightarrow \neg A$ is true. So if we have $\neg B$ , we must have $\neg A$ . Thus, if $\neg B \Rightarrow \neg A$ is true but $A \Rightarrow B$ is false, we have $A\wedge \neg B\wedge \neg A$ , which is a logical impossibility. Thus, if $\neg B \Rightarrow \neg A$ is true, then $A \Rightarrow B$ must be true as well.

To prove the second part, suppose that $A \Rightarrow B$ is true but $\neg B \Rightarrow \neg A$ is false. The only way that the implication can be false is if $\neg B$ is true and $\neg A$ is not so we have $\neg B\wedge A$ . But, $A \Rightarrow B$ is true. So if we have $A$ , we must have $B$ . Thus, if $A \Rightarrow B$ is true but $\neg B \Rightarrow \neg A$ is false, we have $\neg B\wedge A\wedge B$ , which is a logical impossibility. Thus, if $A \Rightarrow B$ is true, then $\neg B \Rightarrow \neg A$ must be true as well.

Therefore, $\neg B \Rightarrow \neg A$ if and only if $A \Rightarrow B$ .

So, we have just proven that a statement and its contrapositive are equivalent. Thus, if the statement is true, the contrapositive is true and vice versa. This is why we can use the proof by contraposition method. Let’s now move on to one of the most interesting proof methods, mathematical induction.

Mathematical Induction

Mathematical induction is useful when proving statements about the natural or whole numbers, especially when related to sequences or series. For example, recall in Part I: Chapter 6, we discussed how to prove sequences converged using the Monotone Convergence Theorem. Induction is a great tool that allows us to prove that a sequence is monotone and bounded so that we may use the Monotone Convergence Theorem.

In general, induction follows a two-step process. We begin with the basis step in which we prove that the base case is true. Then, we have the inductive step that shows every other case is true by using the inductive hypothesis. Probably the best way to understand what all of this means is to look at an example. The following proof is a homework problem that I completed for Introduction to Analysis [6].

Example 26
Prove that the sequence defined by $x_1=\frac{1}{2}$ and

$x_{n+1}=\frac{2}{5-3x_n}$

for $n \in \mathbb{N}$ converges.

Proof.
We will prove this by using induction to show that the sequence is bounded and monotone. Then by the Monotone Convergence Theorem, we will have proven that the sequence converges.So first, we will use induction to show that the sequence is bounded above. We begin with the basis step in which we show that the first term of the sequence is less than or equal to some real number $M$ .

The next step is the inductive step in which we show that every other number in the sequence is also less than or equal to $M$ . We do this by using the inductive hypothesis. The inductive hypothesis assumes that there is some number $x_k$ in the sequence that is less than or equal to $M$ . Then, we show that $x_{k+1}$ must also be less than or equal to $M$ .

Basis Step: $x_1=\frac{1}{2}\leq \frac{2}{3}$ .
Inductive Step: The inductive hypothesis is “assume $x_k \leq \frac{2}{3}$ for some $k \in \mathbb{N}.$ ” Show that $x_{k+1}\leq \frac{2}{3}$ .
$\begin{align*} x_k &\leq \frac{2}{3} &&\text{Inductive hypothesis}\\ -3x_k &\geq -2\\ 5-3x_k &\geq 3 \\ \frac{1}{5-3x_k}&\leq \frac{1}{3}\\ \frac{2}{5-3x_k}&\leq \frac{2}{3}\\ x_{k+1}&\leq \frac{2}{3} \end{align*}$

By mathematical induction, the sequence is bounded above by $\frac{2}{3}$ .

Now, we need to use induction to show that the sequence is nondecreasing. We begin with the basis step in which we show that the first term of the sequence is less than or equal to the second term in the sequence.

In this case, the inductive hypothesis is that there exists some number $x_k$ in the sequence that is less than or equal to $x_{k+1}$ . We then use this in the inductive step to show that if $x_k$ is less than or equal to $x_{k+1}$ then $x_{k+1}$ is less than or equal to $x_{k+2}$ .

Basis Step: $x_1=\frac{1}{2}$ , and $x_2=\frac{4}{7}$ . Therefore, $x_1 \leq x_2$ .
Inductive Step: The inductive hypothesis is “assume $x_k \leq x_{k+1}$ for some $k \in \mathbb{N}.$ ” Show that $x_{k+1}\leq x_{k+2}$ .
$\begin{align*} x_k &\leq x_{k+1} &&\text{Inductive hypothesis}\\ -3x_k &\geq -3x_{k+1}\\ 5-3x_k &\geq 5-3x_{k+1}> 0 &&\text{$\left(x_{k+1}\leq \frac{2}{3} < \frac{5}{3}\right)$}\\ \frac{1}{5-3x_k}&\leq \frac{1}{5-3x_{k+1}}\\ \frac{2}{5-3x_k}&\leq \frac{2}{5-3x_{k+1}}\\ x_{k+1}&\leq x_{k+2} \end{align*}$

Therefore, the sequence is monotone by mathematical induction. Because the sequence is monotone, bounded below by $\frac{1}{2}$ , and bounded above by $\frac{2}{3}$ , the sequence converges by the Monotone Convergence Theorem.

Let’s now try to understand why induction works. Consider the section of the proof where we showed the sequence is bounded above. With the induction step, we showed that if $x_k \leq \frac{2}{3}$ then it must be the case that $x_{k+1}\leq \frac{2}{3}$ as well. The basis step proved that $x_1 \leq \frac{2}{3}$ which implies $x_2 \leq \frac{2}{3}$ which then implies $x_3 \leq \frac{2}{3}$ and so on. Thus, every term in the sequence must be less than or equal to $\frac{2}{3}$ . Similar reasoning can be used to explain why induction works when proving the sequence is monotone. In general, this is why induction proves a statement to be true when the basis step is established and the inductive step can be proven using the inductive hypothesis.

Let’s now move on to our final proof method, proof by cases.

Proof by Cases

A proof by cases is simply a proof that we break into smaller parts, or cases. We use this method when it is easier or even mandatory to prove individual cases rather than everything at once. The best way to understand this method is to see an example. The following proof is a homework problem I completed for Number Theory and comes from Rosen [22]. To help clarify the logic, the theorem used in the proof is given by Rosen as follows [22].

Theorem II.3 (The Fundamental Theorem of Arithmetic)

Every positive integer greater than 1 can be written uniquely as a product of primes, with the prime factors in the product written in nondecreasing order.

Example 27
Show that every positive integer can be written as the product of a square (possibly 1) and a square-free integer. A square-free integer is an integer that is not divisible by any perfect squares other than 1.

Proof.
$1=1\cdot 1.$ Because 1 is a square and a square-free integer, 1 can be written as the product of a square and a square-free integer.Let $n\neq 1$ be a positive integer.

$n=p_1^{q_1}\cdot p_2^{q_2}\cdot...\cdot p_j^{q_j}$

where $p_i$ is prime, $p_1<p_2<...<p_j$ , and $q_i$ is a positive integer by the Fundamental Theorem of Arithmetic.

Case 1: $q_i$ is even for $1\leq i\leq j$ .

This means that

$n=p_1^{2c_1}\cdot p_2^{2c_2}\cdot...\cdot p_j^{2c_j}$

where $q_i=2c_i$ and $c_i$ is a positive integer. So,

$n=\left(p_1^{c_1}\cdot p_2^{c_2}\cdot...\cdot p_j^{c_j}\right)^2\cdot 1.$

Let $a=p_1^{c_1}\cdot p_2^{c_2}\cdot...\cdot p_j^{c_j}.$ Therefore, $n=a^2\cdot 1$ , and $n$ is the product of a square and a square-free integer.

Case 2: $q_i$ is odd for $1\leq i\leq j$ .

This means that

$n=p_1^{2c_1+1}\cdot p_2^{2c_2+1}\cdot...\cdot p_j^{2c_j+1}$

where $q_i=2c_i+1$ and $c_i\geq 0$ is an integer. So,

$\begin{align*} n&=p_1^{2c_1}\cdot p_1\cdot p_2^{2c_2}\cdot p_2\cdot...\cdot p_j^{2c_j}\cdot p_j\\ &=\left(p_1^{c_1}\cdot p_2^{c_2}\cdot...\cdot p_j^{c_j}\right)^2\cdot p_1\cdot p_2\cdot...\cdot p_j \end{align*}$

Let $a=p_1^{c_1}\cdot p_2^{c_2}\cdot...\cdot p_j^{c_j}$ and $b= p_1\cdot p_2\cdot...\cdot p_j.$ Thus, $n=a^2\cdot b$

Because $p_1\neq p_2\neq...\neq p_j$ , $b$ is not divisible by any perfect squares other than 1. Therefore, $n$ is the product of a square and a square-free integer.

Case 3: The prime-power factorization of $n$ contains at least one prime raised to an even power and at least one prime raised to an odd power.

Rewrite the prime-power factorization of $n$ so that all primes to an even power are grouped together and all primes to an odd power are grouped together. That is,

$n=a_1^{2c_1}\cdot a_2^{2c_2}\cdot ...\cdot a_k^{2c_k}\cdot b_1^{2d_1+1}\cdot b_2^{2d_2+1}\cdot ...\cdot b_m^{2d_m+1}$

where $a_i$ and $b_j$ are prime, $a_1<a_2<...<a_k$ and $b_1<b_2<...<b_m$ , and $c_i\geq 1$ and $d_j\geq 0$ are integers. So,

$\begin{align*} n&=a_1^{2c_1}\cdot a_2^{2c_2}\cdot ...\cdot a_k^{2c_k}\cdot b_1^{2d_1}\cdot b_1\cdot b_2^{2d_2}\cdot b_2\cdot ...\cdot b_m^{2d_m}\cdot b_m\\ &=\left(a_1^{c_1}\cdot a_2^{c_2}\cdot ...\cdot a_k^{c_k}\cdot b_1^{d_1}\cdot b_2^{d_2}\cdot ...\cdot b_m^{d_m}\right)^2\cdot b_1\cdot b_2\cdot ...\cdot b_m\\ \end{align*}$

Let $x=a_1^{c_1}\cdot a_2^{c_2}\cdot ...\cdot a_k^{c_k}\cdot b_1^{d_1}\cdot b_2^{d_2}\cdot ...\cdot b_m^{d_m}$ and $y=b_1\cdot b_2\cdot ...\cdot b_m$ . Thus, $n=x^2\cdot y$ .

Because $b_1\neq b_2\neq...\neq b_m$ , $y$ is not divisible by any perfect squares other than 1. Thus, $n$ is the product of a square and a square-free integer.

Therefore, every positive integer can be written as the product of a square and a square-free integer.

Notice that in our proof, the cases covered every single possibility. The prime factorization of a positive integer greater than 1 consists of the product of primes raised to some power. The primes can all be raised to an even power, all raised to an odd power, or some can be raised to an even and some to an odd. These are our only possibilities, and we provided a short proof for each one, referred to as cases. It is critical when using this method that we address every single possibility.