Proof Techniques

Maggie Schildt

11 Proof Techniques

Throughout our educational experiences we have been asked to show our work. In arithmetic we showed how $2+2=4$ , in geometry we found the length of the hypotenuse of a triangle, and in calculus we showed our steps to evaluate an integral or take a derivative. In analysis we are asked to show our work for how we came to a conclusion, using proofs. We begin by being given a statement or claim that we are asked to prove using our statements take on the form $P\rightarrow Q$ . We have seen this notation before, in logic we learned that this denotes an “if, then” statement. In order to prove a statement like this, we are required to provide a proof. As mentioned above, a proof is a structured walk through the steps taken and theorems applied to come to the suggested conclusion or or to disprove the claim entirely. Much like a debate there are several different structure we can apply to create our proof.

There are five proof techniques we will cover: direct proofs, proof by contraposition, indirect proofs, mathematical induction, and proof by cases. We will introduce each technique in detail below.

10.1 Direct Proofs

Direct proofs are just that, direct. Given the claim $P \Rightarrow Q$ , we begin with allowing $P$ to be true, then by utilizing known theorems and logic we work to a conclusion that either concludes $Q$ to be true or disproves $Q$ . The formal steps for direct proof are as follows.

Assume that $P$ is true
Use $P$ to show that $Q$ must be true

From these steps we know that in order to prove a claim directly we must utilize what information we are given from our statement $P$ , knowing that the claim $P\Rightarrow Q$ is structured as “if $P$ , then $Q$ “. From this step we move to prove that $Q$ is true by utilizing theorems and definitions that lead us to the conclusion that $Q$ is true, and thus $P\Rightarrow Q$ . We can see an example of this proof technique in use, below.

Example:

The sum of two odd numbers is even.

Proof: Let $x$ , $y$ be odd, by the definition of odd numbers there exists $m,n\in \mathbb{Z}$ such that $x=2n+1$ and $y=2m+1$ . Then,

$\begin{equation*} \begin{split} x+y&=(2n+1)+(2m+1)\\ &=2n+2m+2\\ &=2(n+m+1) \end{split} \end{equation*}$

Now let $n+m+1=r$ where $r\in \mathbb{Z}$ , since $n,m\in \mathbb{Z}$ which is closed under addition. Thus,

$\begin{equation*} x+y=2{n+m+1}=2r \end{equation*}$

for $r\in \mathbb{Z}$ . Therefor, by the definition of even numbers $x+y$ is even

Let’s now move to the next proof technique which takes the counter approach to a direct proof.

10.2 Contraposition

Previously in the section on direct proofs, we discussed the “if, then” statement. With direct proofs we approach this by claiming $P$ to be true and thus prove $Q$ to be true. We denoted this form of proof by $P\Rightarrow Q$ , with contraposition we denote the proof as $\neg Q\Rightarrow \neg P$ . We prove a claim using the contrapositive proof method by claiming $Q$ to be false firstly and then prove $P$ to be false. In some ways this is the reverse approach to direct proofing. We provide the steps for contraposition below.

Beginning with the implication $P\Rightarrow Q$ , we first deny $P$ and $Q$ are true, denoted by $\neg P$ and $\neg Q$ . We are thus, assuming that $P$ and $Q$ are false.
Next, directly prove that $\neg Q$ implies $\neg P$ .

We are proving a claim, essentially, by proving an alternate position. Consider an example of contrapositive application.

Example:

If $5x+3$ is even, then $x$ is odd.

Proof: Consider that $x$ is even, by the definition of even numbers there is $n\in \mathbb{Z}$ such that $x=2n$ . Thus we can rewrite $5x+3$ as follows:

$\begin{equation*} 5x+3=5(2n)+3=10n+3 \end{equation*}$

If we consider that

$\begin{equation*} 10n+3=10n+2+1=(10n+2)+1 \end{equation*}$

then we can factor out $2$ from $10n+2$ which gives us the following result

$\begin{equation*} (10n+2)+1=2(5n+1)+1 \end{equation*}$

Since $n\in \mathbb{Z}$ which is closed under addition, let $5n+1=r$ where $r\in \mathbb{Z}$ such that

$\begin{equation*} 2(5n+1)+1=2r+1 \end{equation*}$

for $r\in \mathbb{Z}$ . Therefore by the definition of odd numbers $5x+3$ is odd.

We can see here in this example that we began the proof with the claim that “ $x$ is odd” is false and from there we structured a proof that proved the negative of the statement “ $5x+3$ is even” as proposed by proof by contraposition. Now in some courses contraposition proofs fall under the category Indirect proofs because the proof does not follow a direct path from assumption to conclusion. Here we only categorize contrapositive proofs as indirect proofs but it should be noted that both contrapositive and contraposition in most cases are both considered indirect proofs.

10.3 Indirect Proofs

Indirect proofs, like we have seen in contrapositive proofs, find alternative ways to prove a claim. We utilize indirect proofs when proving a claim directly is too challenging. The idea behind indirect proofs is that we want to prove all other possibilities are impossible and thus our claim must be true. Under indirect proofs we will discuss the proof by contradiction. When we start a proof by contradiction we begin by assuming our statement $P$ is not true. We then work through our proof using definitions and theorems to conclude $P\wedge \neg P$ which is a contradiction. Consider the below example.

Example:

Prove that $\sqrt{5}$ is irrational [20].

Proof: Assume $\sqrt{5}$ is a rational number, let $a,b\in \mathbb{Z}$ where $a$ and $b$ share no common factors. If $\left( \frac{a}{b} \right)^{2} = 5$ then $a^{2}=5b^{2}$ which suggests that $a^{2}$ is a multiple of $5$ , a prime number, therefore $a^{2}$ is divisible by the prime number $5$ . Next, we can say that $a^{2}$ contains an even number of prime factors given that $b^{2}$ will contain an even number of prime factors. We can rewrite $a$ then to be $a=5c$ for $c\in \mathbb{Z}$ such that

$\begin{equation*} \begin{split} a^{2}&=(5c)^{2}\\ &=25c^{2}\\ \end{split} \end{equation*}$

Since $a^{2}=5b^{2}$ then we have the equality

$\begin{equation*} 25c^{2}=5b^{2} \end{equation*}$

We can then divide both sides by 5 to get

$\begin{equation*} 5c^{2}=b^{2} \end{equation*}$

We can see here that $b^{2}$ is a multiple of prime $5$ . Since $5c^{2}=b^{2}$ and $c^{2}$ contains an even number of prime factors there is $d\in \mathbb{Z}$ such that $b=5d$ . Thus $a=5c$ and $b=5d$ share the common factor $5$ . But $a$ and $b$ contain no common factors, this is a contradiction. Thus we conclude that $\sqrt{5}$ is an irrational number.

We can see in this example that we solved by first assuming $\sqrt{5}$ was rational and then proving to a conclusion that contradicted a previously stated claim, thus disproving the argument and allowing us to conclude that $\sqrt{5}$ must be irrational.

Concluding this section we can derive the following steps for a proof by contradiction, as seen in the above examples.

We are asked to prove $P\Rightarrow Q$
Assume $P\Rightarrow \neg Q$ , this implication means if $P$ is true then not $Q$ .
we then work through a proof to conclude $Q$ , this is a contradiction.
Finally, conclude that $P\Rightarrow Q$ must be true.

Let us now move on to another method of proofing that does not prove a statement directly but does not qualify as an indirect proof either. As we will see below there is yet another direction for constructing a proof, from the inside out.

10.4 Mathematical Induction

Some proofs can be structured by proving two cases. This means that we can start with one case, called the base case, which we attempt to prove. If we can prove the base case then, through repeated inductive steps, we can prove that the related cases are true. This leads us to finally conclude that the claim we wanted to prove is true. This method is only effective when the statement, or claim, is true for base case $n$ and when the claim is true for some natural number $n=k$ which leads to $n=k+1$ cases to be true. We call mathematical induction and can be seen in the formal steps to solve prove our below [36].

The Base Case: The statement is true for case $n=1$ .
Inductive Step: If the statement is true for case $n=k$ , then the statement is also true for case $n=k+1$ .

First consider an example of a direct proof solved by mathematical induction.

Example:

$4^{n}-1$ is divisible by 3 [20].

Base case: Let $n=1$ , $4^{1}-1=3$ which is divisible by 3 as our claim suggests.
Inductive step: Let $n=k$ for some $k\in \mathbb{N}$ such that $4^{k}-1$ is divisible by $3$ . Then $4^{k}-1=3r$ for some $r\in \mathbb{Z}$ .Consider there is $k+1\in \mathbb{N}$ where

$\begin{equation*} 4^{k+1}-1=4\cdot 4^{k}-1 \end{equation*}$

Since $-1=4-3$ then substitute $-1$ for $-4+3$ in our function

$\begin{equation*} \begin{split} 4\cdot 4^{k}-1&=4\cdot 4^{k}(-4+3)\\ &=(4\cdot 4^{k}-4)+3 \end{split} \end{equation*}$

We can factor out 4 from $4 \cdot 4^{k}-4$ to get the following

$\begin{equation*} (4\cdot 4^{k}-4)+3=4(4^{k}-1)+3 \end{equation*}$

Since $4^{k}-1=3r$ then we can substitute $4^{k}-1$ with $3r$ and then simplify by factoring out the common factor.

$\begin{equation*} \begin{split} 4(4^{k}-1)+3&=4(3r)+3\\ &=12r+3\\ &=3(4r+1) \end{split} \end{equation*}$

Since we have found $4^{k+1}-1=3(4r+1)$ and $3(4r+1)$ is divisible by $3$ then we conclude that the product of $(4^{k+1}-1)$ is divisible by 3 as well. Thus since our claim is true whenever $n=k$ for some $k\in \mathbb{N}$ and if the claim is true for $n=k$ then it is also true for $k+1$ , we can conclude that $4^{n}-1$ is divisible by 3 for all $n\in \mathbb{N}$ .

By starting small and proving a base case we can use that base case to build on our proof until we can come to a sound conclusion. Induction is a key part of mathematics, we are asked to look at numbers, to find patterns or trends. By locating a pattern or trend between a few examples we can develop a method or law that includes every possible case. We can also develop methods for finding the minimum or maximum steps required to obtain a certain result. An incredible example of this is the Tower of Hanoi problem.

Example: The Tower of Hanoi

There are seven disks, of varying sizes, with holes in the center large enough to fit on each of three posts. We start with all seven disks on one post, all seven disks are stacked in order of largest at the bottom to smallest at the top. The objective is to find the least amount of steps required to move all seven disks onto another peg in the same order. There are two rules that must be followed [25]:

The only action that can be taken is to move the top disk from one post to another.
A larger sized disk cannot stack on top of a smaller disk, ever.

In order to solve this problem we need to use induction. We begin with the base step.

Base step: Consider we have one disk, $n=1$ , and let $H_{n}=2^{n}-1$ be defined as the minimal number of steps required to move all disks to another peg. The number of steps required to move the disks from one post to another is then

$\begin{equation*} \begin{split} H_{1}&=2^{1}-1\\ &=2-1\\ &=1 \end{split} \end{equation*}$

Inductive Step: Now consider $n+1$ disks, we start by breaking down the steps. The first step would be to move $n-1$ disks to another post which requires $2^{n-1}-1$ moves. Next we consider moving the last disk from the original post to the only other available post without the other disks on it, this requires $+1$ moves. Finally we need to move that original stack of $n-1$ disks from their second post and onto the post with the largest disk just dropped on it, this will require $2^{n-1}-1$ moves. Now lets add these steps to to find the total amount of moves required.

$\begin{equation*} 2^{n}-1+1-2^{n}-1=2H_{n}+1=H_{n+1} \end{equation*}$

The last step is to show that $H_{n}=2^{n}-1$ for any $n\in \mathbb{N}$ . We already know that $H_{n}$ applies to $n=1$ , now let $k\in \mathbb{N}$ such that $H_{k}=2^{k}-1$ , using the equation we found above for $n+1$ disks substitute $k$ for $n$ giving us $2H_{k}+1$ , we solve for $k+1$ .

$\begin{equation*} \begin{split} 2H_{k}+1&=2^{k}-1+1-2^{k}-1\\ &=2^{k}+2^{k}-1\\ &=2\cdot 2^{k}-1\\ &=2^{k+1}-1 \end{split} \end{equation*}$

Thus we can conclude that the minimum number of moves required to satisfy the problem given $n$ discs is $2^{n}-1$ .

We have seen from this example that by starting with the most basic case we know to be true we are able to derive a conclusion for all cases by using mathematical induction. And as such we can construct a proof that can prove all cases for a claim.

There is another way to prove a claim through cases when there are only a few cases and each can be solved directly. We see this type of proof introduced below.

10.5 Proof by Cases

As noted in the previous section there are some claims that require a proof for each individual case for the claim. We call this technique proof by cases or in some classes it will be described as proof by exhaustion. The second description sums up the fundamental idea behind a proof by cases. We are given a claim with which we must either prove all possible cases in order to draw a conclusion for the claim entirely. By doing this we leave no room for error in our conclusion because we have considered every possibility and proven its truth value.

Unlike the proof by induction technique, proof by cases does not make any assumptions unless a rational connection can be proven for connecting the truth value of one case to another. There may be proof by induction used per claim but unless a connection can be drawn between claims each claim as proven independently.

Consider an example of this type of proof in use.

Example:

$|\frac{a}{b}|=\frac{|a|}{|b|}$ , for $b\neq 0$ .

We will construct our proof using cases.

Case 1) Suppose $a>0$ if $b>0$ , then $a=|a|$ and $b=|b|$ such that

$\begin{equation*} \frac{a}{b}=\frac{|a|}{|b|}=\left|\frac{a}{b} \right| \end{equation*}$

This is because the absolute value of positive values in a fraction taken independently, still results in a positive value for the fraction. This is equal to if we were to take the absolute value of the fraction in it’s entirety. As well, if $b<0$ then $|-b|=|b|=b$ such that

$\begin{equation*} \begin{split} \frac{a}{-b}&=\frac{a}{b}\\ &=\frac{|a|}{|b|}\\ &=\left|\frac{a}{b} \right| \end{split} \end{equation*}$

We see here that the absolute value of a negative variable is equal to the variable if it were simply positive. Thus, we find that the absolute value of the denominator and numerator, found separately, is equal to the absolute value of the fraction if we took the absolute value of the fraction as a whole. Therefore we can conclude that $\left| \frac{a}{b} \right|=\frac{|a|}{|b|}$ for $a> 0$ and $b>0$ or $b<0$ .

Case 2) Suppose $a<0$ and $b>0$ , then $|-a|=|a|=a$ and $b=|b|$ , thus

$\begin{equation*} \begin{split} \frac{-a}{b}&=\frac{a}{b}\\ &=\frac{|a|}{|b|}\\ &=\left| \frac{a}{b} \right| \end{split} \end{equation*}$

If $b<0$ , then $|-a|=|a|=a$ and $|-b|=|b|=b$ , thus

$\begin{equation*} \begin{split} \frac{-a}{-b}&=\frac{a}{b}\\ &=\frac{|a|}{|b|}\\ &=\left| \frac{a}{b} \right| \end{split} \end{equation*}$

Here we see that the absolute value of a negative variable is equal to the variable if it were simply positive. Thus the absolute value of the numerator and denominator, found separately, is equal to the absolute value of the fraction. Therefore we can conclude that $\left| \frac{a}{b} \right|=\frac{|a|}{|b|}$ for $a<0$ and $b>0$ or $b<0$ .

Case 3) Suppose $a=0$ and $b>0$ , then $0=|a|$ and $b=|b|$ , thus

$\begin{equation*} \frac{a}{b}=\frac{0}{|b|}=\left| \frac{0}{b} \right| \end{equation*}$

If $b<0$ , then $|-b|=|b|=b$ , thus

$\begin{equation*} \begin{split} \frac{0}{-b}&=\frac{0}{b}\\ &=\frac{0}{|b|}\\ &=\left| \frac{0}{b} \right| \end{split} \end{equation*}$

Since 0 is never negative and the absolute value of a variable, negative or positive, results in a positive, then we can conclude that absolute value of the denominator and numerator, found individually, is the same as if we were to take the absolute value of the fraction as a whole. Thus we can make the final conclusion that the initial claim is true since every case has been proven to be true.

Proofs by cases are a great way to prove a claim when applicable. Without being able to address each case individually we would not be able to prove without a doubt that our claim was true.

11 Proof Techniques

License

Share This Book