3 Constructing and Writing Proofs in Mathematics

3.2 More Methods of Proof

3.2.1 Beginning Activity 1 (Using the Contrapositive)

The following statement was proven in Exercise (3c) in Section 1.2.
If $n$ is an odd integer, then $n^2$ is an odd integer.

Now consider the following proposition:
For each integer $n$, if $n^2$ is an odd integer, then $n$ is an odd integer.

1. After examining several examples, decide whether you think this proposition is true or false.

2. Try completing the following know-show table for a direct proof of this proposition. The question is, "Can we perform algebraic manipulations to get from the ’know’ portion of the table to the ’show’ portion of the table?" Be careful with this! Remember that we are working with integers and we want to make sure that we can end up with an integer $q$ as stated in Step $Q1$.

   Step	Know	Reason
   $P$	$n^2$ is an odd integer.	Hypothesis
   $P1$	$(\exists k\in \mathbb{Z})\left(n^2=2k+1\right)$	Definition of "odd integer"
   $\mathrm{⋮}$	$\mathrm{⋮}$	$\mathrm{⋮}$
   $Q1$	$(\exists q\in \mathbb{Z})(n=2q+1)$
   $Q$	$n$ is an odd integer.	Definition of "odd integer"
   Step	Show	Reason

Recall that the contrapositive of the conditional statement $P\to Q$ is the conditional statement $\neg Q\to \neg P$, which is logically equivalent to the original conditional statement. (It might be a good idea to review Beginning Activity 2 from Section 2.2.) Consider the following proposition once again:

For each integer $n$, if $n^2$ is an odd integer, then $n$ is an odd integer.

1. Write the contrapositive of this conditional statement. Please note that "not odd" means "even." (We have not proved this, but it can be proved using the Division Algorithm in Section 3.5.)

2. Complete a know-show table for the contrapositive statement from Part (3).

3. By completing the proof in Part (4), have you proven the given proposition? That is, have you proven that if $n^2$ is an odd integer, then $n$ is an odd integer? Explain.

3.2.2 Beginning Activity 2 (A Biconditional Statement)

1. In Exercise (4a) from Section 2.2, we constructed a truth table to prove that the biconditional statement, $P\leftrightarrow Q$, is logically equivalent to $(P\to Q)\wedge$ ($Q\to P$). Complete this exercise if you have not already done so.

2. Suppose that we want to prove a biconditional statement of the form $P\leftrightarrow Q$. Explain a method for completing this proof based on the logical equivalency in part (1).

3. Let $n$ be an integer. Assume that we have completed the proofs of the following two statements:

• If $n$ is an odd integer, then $n^2$ is an odd integer.

• If $n^2$ is an odd integer, then $n$ is an odd integer.
  (See Exercise (3c) from Section 1.2 and Beginning Activity 1.) Have we completed the proof of the following proposition?

For each integer $n,n$ is an odd integer if and only if $n^2$ is an odd integer.
Explain.

3.2.3 Review of Direct Proofs

In Sections 1.2 and 3.1, we studied direct proofs of mathematical statements. Most of the statements we prove in mathematics are conditional statements that can be written in the form $P\to Q$. A direct proof of a statement of the form $P\to Q$ is based on the definition that a conditional statement can only be false when the hypothesis, $P$, is true and the conclusion, $Q$, is false. Thus, if the conclusion is true whenever the hypothesis is true, then the conditional statement must be true. So, in a direct proof,

• We start by assuming that $P$ is true.

• From this assumption, we logically deduce that $Q$ is true.

We have used the so-called forward and backward method to discover how to logically deduce $Q$ from the assumption that $P$ is true.

3.2.4 Proof Using the Contrapositive

As we saw in Beginning Activity 1, it is sometimes difficult to construct a direct proof of a conditional statement. This is one reason we studied logical equivalencies in Section 2.2. Knowing that two expressions are logically equivalent tells us that if we prove one, then we have also proven the other. In fact, once we know the truth value of a statement, then we know the truth value of any other statement that is logically equivalent to it.

One of the most useful logical equivalencies in this regard is that a conditional statement $P\to Q$ is logically equivalent to its contrapositive, $\neg Q\to \neg P$. This
means that if we prove the contrapositive of the conditional statement, then we have proven the conditional statement. The following are some important points to remember.

• A conditional statement is logically equivalent to its contrapositive.

• Use a direct proof to prove that $\neg Q\to \neg P$ is true.

• Caution: One difficulty with this type of proof is in the formation of correct negations. (We need to be very careful doing this.)

• We might consider using a proof by contrapositive when the statements $P$ and $Q$ are stated as negations.

3.2.5 Writing Guidelines

One of the basic rules of writing mathematical proofs is to keep the reader informed. So when we prove a result using the contrapositive, we indicate this within the first few lines of the proof. For example,

• We will prove this theorem by proving its contrapositive.

• We will prove the contrapositive of this statement.

In addition, make sure the reader knows the status of every assertion that you make. That is, make sure you state whether an assertion is an assumption of the theorem, a previously proven result, a well-known result, or something from the reader’s mathematical background. Following is a completed proof of a statement from Beginning Activity 1.

Theorem 3.7. For each integer $n$, if $n^2$ is an even integer, then $n$ is an even integer.

Proof. We will prove this result by proving the contrapositive of the statement, which is

For each integer $n$, if $n$ is an odd integer, then $n^2$ is an odd integer.

However, in Theorem 1.8, we have already proven that if $x$ and $y$ are odd integers, then $x\cdot y$ is an odd integer. So using $x=y=n$, we can conclude that if $n$ is an odd integer, then $n\cdot n$, or $n^2$, is an odd integer. We have thus proved the contrapositive of the theorem, and consequently, we have proved that if $n^2$ is an even integer, then $n$ is an even integer.

3.2.6 Using Other Logical Equivalencies

As was noted in Section 2.2, there are several different logical equivalencies. Fortunately, there are only a small number that we often use when trying to write proofs, and many of these are listed in Theorem 2.8 at the end of Section 2.2. We will illustrate the use of one of these logical equivalencies with the following proposition:

For all real numbers $a$ and $b$, if $a\ne 0$ and $b\ne 0$, then $ab\ne 0$.
First, notice that the hypothesis and the conclusion of the conditional statement are stated in the form of negations. This suggests that we consider the contrapositive. Care must be taken when we negate the hypothesis since it is a conjunction. We use one of De Morgan’s Laws as follows:

$$\neg (a\ne 0\wedge b\ne 0)\equiv (a=0)\vee (b=0)$$

3.2.7 Progress Check 3.8 (Using Another Logical Equivalency)

1. In English, write the contrapositive of, "For all real numbers $a$ and $b$, if $a\ne 0$ and $b\ne 0$, then $ab\ne 0$."

The contrapositive is a conditional statement in the form $X\to (Y\vee Z)$. The difficulty is that there is not much we can do with the hypothesis $(ab=0)$ since we know nothing else about the real numbers $a$ and $b$. However, if we knew that $a$ was not equal to zero, then we could multiply both sides of the equation $ab=0$ by $\frac{1}{a}$. This suggests that we consider using the following logical equivalency based on a result in Theorem 2.8:

$$X\to (Y\vee Z)\equiv (X\wedge \neg Y)\to Z$$

1. In English, use this logical equivalency to write a statement that is logically equivalent to the contrapositive from Part (1).

The logical equivalency in Part (2) makes sense because if we are trying to prove $Y\vee Z$, we only need to prove that at least one of $Y$ or $Z$ is true. So the idea is to prove that if $Y$ is false, then $Z$ must be true.

1. Use the ideas presented in the progress check to complete the proof of the following proposition.

   Proposition 3.9. For all real numbers $a$ and $b$, if $a\ne 0$ and $b\ne 0$, then $ab\ne 0$.

   Proof. We will prove the contrapositive of this proposition, which is
   For all real numbers $a$ and $b$, if $ab=0$, then $a=0$ or $b=0$.

   This contrapositive, however, is logically equivalent to the following:
   For all real numbers $a$ and $b$, if $ab=0$ and $a\ne 0$, then $b=0$.
   To prove this, we let $a$ and $b$ be real numbers and assume that $ab=0$ and $a\ne 0$. We can then multiply both sides of the equation $ab=0$ by $\frac{1}{a}$. This gives

   Now complete the proof.
   $\mathrm{⋮}$

   Therefore, $b=0$. This completes the proof of a statement that is logically equivalent to the contrapositive, and hence, we have proven the proposition.

3.2.8 Proofs of Biconditional Statements

In Beginning Activity 2, we used the following logical equivalency:

$$(P\leftrightarrow Q)\equiv (P\to Q)\wedge (Q\to P).$$

This logical equivalency suggests one method for proving a biconditional statement written in the form "$P$ if and only if $Q$." This method is to construct separate proofs of the two conditional statements $P\to Q$ and $Q\to P$. For example, since we have now proven each of the following:

• For each integer $n$, if $n$ is an even integer, then $n^2$ is an even integer. (Exercise (3c) on page 28 in Section 1.2)

• For each integer $n$, if $n^2$ is an even integer, then $n$ is an even integer. (Theorem 3.7)
  we can state the following theorem.

Theorem 3.10. For each integer $n,n$ is an even integer if and only if $n^2$ is an even integer.

3.2.9 Writing Guidelines

When proving a biconditional statement using the logical equivalency $(P\leftrightarrow Q)\equiv (P\to Q)\wedge (Q\to P)$, we actually need to prove two conditional statements. The proof of each conditional statement can be considered as one of two parts of the proof of the biconditional statement. Make sure that the start and end of each of these parts is indicated clearly. This is illustrated in the proof of the following proposition.

Proposition 3.11. Let $x\in ℝ$. The real number $x$ equals 2 if and only if $x^3-2x^2+x=2$.

Proof. We will prove this biconditional statement by proving the following two conditional statements:

• For each real number $x$, if $x$ equals 2, then $x^3-2x^2+x=2$.

• For each real number $x$, if $x^3-2x^2+x=2$, then $x$ equals 2 .

For the first part, we assume $x=2$ and prove that $x^3-2x^2+x=2$. We can do this by substituting $x=2$ into the expression $x^3-2x^2+x$. This gives

$x^3-2x^2+x$ $=2^3-2\left(2^2\right)+2$

$=8-8+2$

$=2$

This completes the first part of the proof.

For the second part, we assume that $x^3-2x^2+x=2$ and from this assumption, we will prove that $x=2$. We will do this by solving this equation for $x$. To do so, we first rewrite the equation $x^3-2x^2+x=2$ by subtracting 2 from both sides:

$$x^3-2x^2+x-2=0.$$

We can now factor the left side of this equation by factoring an $x^2$ from the first two terms and then factoring $(x-2)$ from the resulting two terms. This is shown
below.

$x^3-2x^2+x-2$ $=0$

$x^2(x-2)+(x-2)$ $=0$

$(x-2)\left(x^2+1\right)$ $=0$

Now, in the real numbers, if a product of two factors is equal to zero, then one of the factors must be zero. So this last equation implies that

$$x-2=0\text{ or }{x}^2+1=0.$$

The equation $x^2+1=0$ has no real number solution. So since $x$ is a real number, the only possibility is that $x-2=0$. From this we can conclude that $x$ must be equal to 2 .

Since we have now proven both conditional statements, we have proven that $x=2$ if and only if $x^3-2x^2+x=2$.

3.2.10 Constructive Proofs

We all know how to solve an equation such as $3x+8=23$, where $x$ is a real number. To do so, we first add -8 to both sides of the equation and then divide both sides of the resulting equation by 3. Doing so, we obtain the following result:

$$\text{ If }x\text{ is a real number and }3x+8=23\text{, then }x=5\text{. }$$

Notice that the process of solving the equation actually does not prove that $x=5$ is a solution of the equation $3x+8=23$. This process really shows that if there is a solution, then that solution must be $x=5$. To show that this is a solution, we use the process of substituting 5 for $x$ in the left side of the equation as follows: If $x=5$, then

$$3x+8=3(5)+8=15+8=23.$$

This proves that $x=5$ is a solution of the equation $3x+8=23$. Hence, we have proven that $x=5$ is the only real number solution of $3x+8=23$.

We can use this same process to show that any linear equation has a real number solution. An equation of the form

$$ax+b=c,$$

where $a,b$, and $c$ are real numbers with $a\ne 0$, is called a linear equation in one variable.

Proposition 3.12. If $a,b$, and $c$ are real numbers with $a\ne 0$, then the linear equation $ax+b=c$ has exactly one real number solution, which is $x=\frac{c-b}{a}$.

Proof. Assume that $a,b$, and $c$ are real numbers with $a\ne 0$. We can solve the linear equation $ax+b=c$ by adding $-b$ to both sides of the equation and then dividing both sides of the resulting equation by $a$ (since $a\ne 0$), to obtain

$$x=\frac{c-b}{a}.$$

This shows that if there is a solution, then it must be $x=\frac{c-b}{a}$. We also see that if $x=\frac{c-b}{a}$, then

$ax+b$ $=a\left({\displaystyle \frac{c-b}{a}}\right)+b$

$=(c-b)+b$

$=c$

Therefore, the linear equation $ax+b=c$ has exactly one real number solution and the solution is $x=\frac{c-b}{a}$.

The proof given for Proposition 3.12 is called a constructive proof. This is a technique that is often used to prove a so-called existence theorem. The objective of an existence theorem is to prove that a certain mathematical object exists. That is, the goal is usually to prove a statement of the form

3.2.11 There exists an $x$ such that $P(x)$.

For a constructive proof of such a proposition, we actually name, describe, or explain how to construct some object in the universe that makes $P(x)$ true. This is what we did in Proposition 3.12 since in the proof, we actually proved that $\frac{c-b}{a}$ is a solution of the equation $ax+b=c$. In fact, we proved that this is the only solution of this equation.

3.2.12 Nonconstructive Proofs

Another type of proof that is often used to prove an existence theorem is the socalled nonconstructive proof. For this type of proof, we make an argument that an object in the universal set that makes $P(x)$ true must exist but we never construct or name the object that makes $P(x)$ true. The advantage of a constructive proof over a nonconstructive proof is that the constructive proof will yield a procedure or algorithm for obtaining the desired object.

The proof of the Intermediate Value Theorem from calculus is an example of a nonconstructive proof. The Intermediate Value Theorem can be stated as follows:

If $f$ is a continuous function on the closed interval $[a,b]$ and if $q$ is any real number strictly between $f(a)$ and $f(b)$, then there exists a number $c$ in the interval $(a,b)$ such that $f(c)=q$.

The Intermediate Value Theorem can be used to prove that a solution to some equations must exist. This is shown in the next example.

3.2.13 Example 3.13 (Using the Intermediate Value Theorem)

Let $x$ represent a real number. We will use the Intermediate Value Theorem to prove that the equation $x^3-x+1=0$ has a real number solution.

To investigate solutions of the equation $x^3-x+1=0$, we will use the function

$$f(x)=x^3-x+1.$$

Notice that $f(-2)=-5$ and that $f(0)=1$. Since and $f(0)>0$, the Intermediate Value Theorem tells us that there is a real number $c$ between -2 and 0 such that $f(c)=0$. This means that there exists a real number $c$ between -2 and 0 such that

$$c^3-c+1=0,$$

and hence $c$ is a real number solution of the equation $x^3-x+1=0$. This proves that the equation $x^3-x+1=0$ has at least one real number solution.

Notice that this proof does not tell us how to find the exact value of $c$. It does, however, suggest a method for approximating the value of $c$. This can be done by finding smaller and smaller intervals $[a,b]$ such that $f(a)$ and $f(b)$ have opposite signs.

3.2.14 Exercises for Section 3.2

1. $(\star )$ Let $n$ be an integer. Prove each of the following:

   1. If $n$ is even, then $n^3$ is even.

   2. If $n^3$ is even, then $n$ is even.

   3. The integer $n$ is even if and only if $n^3$ is an even integer.

   4. The integer $n$ is odd if and only if $n^3$ is an odd integer.

2. $(\star )$ In Section 3.1, we defined congruence modulo $n$ where $n$ is a natural number. If $a$ and $b$ are integers, we will use the notation $a\not\equiv b(modn)$ to mean that $a$ is not congruent to $b$ modulo $n$.

   1. $(\star )$ Write the contrapositive of the following conditional statement: For all integers $a$ and $b$, if $a\not\equiv 0(mod6)$ and $b\not\equiv 0(mod6)$, then $ab\not\equiv 0(mod6)$.

   2. Is this statement true or false? Explain.

3. 1. $(\star )$ Write the contrapositive of the following statement: For all positive real numbers $a$ and $b$, if $\sqrt{ab}\ne \frac{a+b}{2}$, then $a\ne b$.

   2. Is this statement true or false? Prove the statement if it is true or provide a counterexample if it is false.

4. $(\star )$ Are the following statements true or false? Justify your conclusions.

   1. For each $a\in \mathbb{Z}$, if $a\equiv 2(mod5)$, then $a^2\equiv 4(mod5)$.

   2. For each $a\in \mathbb{Z}$, if $a^2\equiv 4(mod5)$, then $a\equiv 2(mod5)$.

   3. For each $a\in \mathbb{Z},a\equiv 2(mod5)$ if and only if $a^2\equiv 4(mod5)$.

5. Is the following proposition true or false?

   For all integers $a$ and $b$, if $ab$ is even, then $a$ is even or $b$ is even. Justify your conclusion by writing a proof if the proposition is true or by providing a counterexample if it is false.

6. $(\star )$ Consider the following proposition: For each integer $a,a\equiv 3(mod7)$ if and only if $\left(a^2+5a\right)\equiv 3(mod7)$.

   1. Write the proposition as the conjunction of two conditional statements.

   2. Determine if the two conditional statements in Part (a) are true or false. If a conditional statement is true, write a proof, and if it is false, provide a counterexample.

   3. Is the given proposition true or false? Explain.

7. Consider the following proposition: For each integer $a,a\equiv 2(mod8)$ if and only if $\left(a^2+4a\right)\equiv 4(mod8)$.

   1. Write the proposition as the conjunction of two conditional statements.

   2. Determine if the two conditional statements in Part (a) are true or false. If a conditional statement is true, write a proof, and if it is false, provide a counterexample.

   3. Is the given proposition true or false? Explain.

8. For a right triangle, suppose that the hypotenuse has length $c$ feet and the lengths of the sides are $a$ feet and $b$ feet.

   1. What is a formula for the area of this right triangle? What is an isosceles triangle?

   2. State the Pythagorean Theorem for right triangles.

   3. $(\star )$ Prove that the right triangle described above is an isosceles triangle if and only if the area of the right triangle is $\frac{1}{4}{c}^2$.

9. $(\star )$ A real number $x$ is defined to be a rational number provided there exist integers $m$ and $n$ with $n\ne 0$ such that $x=\frac{m}{n}$.

   A real number that is not a rational number is called an irrational number. It is known that if $x$ is a positive rational number, then there exist positive integers $m$ and $n$ with $n\ne 0$ such that $x=\frac{m}{n}$. Is the following proposition true or false? Explain. For each positive real number $x$, if $x$ is irrational, then $\sqrt{x}$ is irrational.

10. $(\star )$ Is the following proposition true or false? Justify your conclusion. For each integer $n,n$ is even if and only if 4 divides $n^2$.

11. Prove that for each integer $a$, if $a^2-1$ is even, then 4 divides $a^2-1$.

12. Prove that for all integers $a$ and $m$, if $a$ and $m$ are the lengths of the sides of a right triangle and $m+1$ is the length of the hypotenuse, then $a$ is an odd integer.

13. Prove the following proposition:

    If $p,q\in \mathbb{Q}$ with , then there exists an $x\in \mathbb{Q}$ with .

14. Are the following propositions true or false? Justify your conclusion.

    1. There exist integers $x$ and $y$ such that $4x+6y=2$.

    2. There exist integers $x$ and $y$ such that $6x+15y=2$.

    3. There exist integers $x$ and $y$ such that $6x+15y=9$.

15. $(\star )$ Prove that there exists a real number $x$ such that $x^3-4x^2=7$.

16. Let $y_1,y_2,y_3,y_4$ be real numbers. The mean, $\overline{y}$, of these four numbers is defined to be the sum of the four numbers divided by 4. That is,

    $$\overline{y}=\frac{y_1+y_2+y_3+y_4}{4}.$$

    Prove that there exists a $y_i$ with $1\le i\le 4$ such that $y_i\ge \overline{y}$. Hint: One way is to let $y_{\text{max }}$ be the largest of $y_1,y_2,y_3,y_4$.

17. Let $a$ and $b$ be natural numbers such that $a^2=b^3$. Prove each of the propositions in Parts (a) through (d). (The results of Exercise (1) and Theorem 3.10 may be helpful.)

    1. If $a$ is even, then 4 divides $a$.

    2. If 4 divides $a$, then 4 divides $b$.

    3. If 4 divides $b$, then 8 divides $a$.

    4. If $a$ is even, then 8 divides $a$.

    5. Give an example of natural numbers $a$ and $b$ such that $a$ is even and $a^2=b^3$, but $b$ is not divisible by 8.

18. $(\star )$ Prove the following proposition: Let $a$ and $b$ be integers with $a\ne 0$. If $a$ does not divide $b$, then the equation $a{x}^3+bx+(b+a)=0$ does not have a solution that is a natural number.
    Hint: It may be necessary to factor a sum of cubes. Recall that

    $$u^3+v^3=(u+v)\left(u^2-uv+v^2\right)$$

19. Evaluation of Proofs. See the instructions for Exercise (19) on page 100 from Section 3.1.

    1. Proposition. If $m$ is an odd integer, then ($m+6$) is an odd integer.

       Proof. For $m+6$ to be an odd integer, there must exist an integer $n$ such that

       $$m+6=2n+1.$$

       By subtracting 6 from both sides of this equation, we obtain

       $m$ $=2n-6+1$

       $=2(n-3)+1.$

       By the closure properties of the integers, $(n-3)$ is an integer, and hence, the last equation implies that $m$ is an odd integer. This proves that if $m$ is an odd integer, then $m+6$ is an odd integer.

    2. Proposition. For all integers $m$ and $n$, if $mn$ is an even integer, then $m$ is even or $n$ is even.

       Proof. For either $m$ or $n$ to be even, there exists an integer $k$ such that $m=2k$ or $n=2k$. So if we multiply $m$ and $n$, the product will contain a factor of 2 and, hence, $mn$ will be even.

3.2.15 Explorations and Activities

1. Using a Logical Equivalency. Consider the following proposition:

   Proposition. For all integers $a$ and $b$, if 3 does not divide $a$ and 3 does not divide $b$, then 3 does not divide the product $a\cdot b$.

   1. Notice that the hypothesis of the proposition is stated as a conjunction of two negations (" 3 does not divide $a$ and 3 does not divide $b$ "). Also, the conclusion is stated as the negation of a sentence (" 3 does not divide the product $a\cdot b$. "). This often indicates that we should consider using a proof of the contrapositive. If we use the symbolic form $(\neg Q\wedge \neg R)\to \neg P$ as a model for this proposition, what is $P$, what is $Q$, and what is $R$?

   2. Write a symbolic form for the contrapositive of $(\neg Q\wedge \neg R)\to \neg P$.

   3. Write the contrapositive of the proposition as a conditional statement in English.

      We do not yet have all the tools needed to prove the proposition or its contrapositive. However, later in the text, we will learn that the following proposition is true.

      Proposition X. Let $a$ be an integer. If 3 does not divide $a$, then there exist integers $x$ and $y$ such that $3x+ay=1$.

      1. Find integers $x$ and $y$ guaranteed by Proposition X when $a=5$.

      2. Find integers $x$ and $y$ guaranteed by Proposition X when $a=2$.

      3. Find integers $x$ and $y$ guaranteed by Proposition X when $a=-2$.

   4. Assume that Proposition X is true and use it to help construct a proof of the contrapositive of the given proposition. In doing so, you will most likely have to use the logical equivalency $P\to (Q\vee R)\equiv (P\wedge \neg Q)\to R$.