3 Constructing and Writing Proofs in Mathematics

3.4 Using Cases in Proofs

3.4.1 Beginning Activity 1 (Using a Logical Equivalency)

1. Complete a truth table to show that $(P\vee Q)\to R$ is logically equivalent to $(P\to R)\wedge (Q\to R)$.

2. Suppose that you are trying to prove a statement that is written in the form $(P\vee Q)\to R$. Explain why you can complete this proof by writing separate and independent proofs of $P\to R$ and $Q\to R$.

3. Now consider the following proposition:

   Proposition. For all integers $x$ and $y$, if $xy$ is odd, then $x$ is odd and $y$ is odd.

   Write the contrapositive of this proposition.

4. Now prove that if $x$ is an even integer, then $xy$ is an even integer. Also, prove that if $y$ is an even integer, then $xy$ is an even integer.

5. Use the results proved in part (4) and the explanation in part (2) to explain why we have proved the contrapositive of the proposition in part (3).

3.4.2 Beginning Activity 2 (Using Cases in a Proof)

The work in Beginning Activity 1 was meant to introduce the idea of using cases in a proof. The method of using cases is often used when the hypothesis of the proposition is a disjunction. This is justified by the logical equivalency

$$[(P\vee Q)\to R]\equiv [(P\to R)\wedge (Q\to R)]$$

See Theorem 2.8 and Exercise (6) from Section 2.2.
In some other situations when we are trying to prove a proposition or a theorem about an element $x$ in some set $U$, we often run into the problem that there does not seem to be enough information about $x$ to proceed. For example, consider the following proposition:

Proposition 1. If $n$ is an integer, then $\left(n^2+n\right)$ is an even integer.

If we were trying to write a direct proof of this proposition, the only thing we could assume is that $n$ is an integer. This is not much help. In a situation such as this, we will sometimes use cases to provide additional assumptions for the forward process of the proof. Cases are usually based on some common properties that the element $x$ may or may not possess. The cases must be chosen so that they exhaust all possibilities for the object $x$ in the hypothesis of the original proposition. For Proposition 1, we know that an integer must be even or it must be odd. We can thus use the following two cases for the integer $n$ :

• The integer $n$ is an even integer;

• The integer $n$ is an odd integer.

1. Complete the proof for the following proposition:

   Proposition 2: If $n$ is an even integer, then $n^2+n$ is an even integer.
   Proof. Let $n$ be an even integer. Then there exists an integer $m$ such that $n=2m$. Substituting this into the expression $n^2+n$ yields $\mathrm{\dots }$.

2. Construct a proof for the following proposition:

   Proposition 3: If $n$ is an odd integer, then $n^2+n$ is an even integer.

3. Explain why the proofs of Proposition 2 and Proposition 3 can be used to construct a proof of Proposition 1.

3.4.3 Some Common Situations to Use Cases

When using cases in a proof, the main rule is that the cases must be chosen so that they exhaust all possibilities for an object $x$ in the hypothesis of the original proposition. Following are some common uses of cases in proofs.

When the hypothesis is, "$n$ is an integer."
Case 1: $n$ is an even integer.
Case 2: $n$ is an odd integer.

When the hypothesis is, "$m$ and $n$ are integers."
Case 1: $m$ and $n$ are even.
Case 2: $m$ is even and $n$ is odd.
Case 3: $m$ is odd and $n$ is even.
Case 4: $m$ and $n$ are both odd.

When the hypothesis is, "$x$ is a real number."
Case 1: $x$ is rational.
Case 2: $x$ is irrational.

When the hypothesis is, "$x$ is a real number."
Case 1: $x=0$. OR Case 1: $x>0$.
Case 2: $x\ne 0.$ Case 2: $x=0$.
Case 3: .

When the hypothesis is, "$a$ and $b$ are real numbers."

3.4.4 Writing Guidelines for a Proof Using Cases

When writing a proof that uses cases, we use all the other writing guidelines. In addition, we make sure that it is clear where each case begins. This can be done by using a new paragraph with a label such as "Case 1," or it can be done by starting a paragraph with a phrase such as, "In the case where …."

3.4.5 Progress Check 3.21 (Using Cases: $𝒏$ Is Even or $𝒏$ Is Odd)

Complete the proof of the following proposition:
Proposition. For each integer $n,n^2-5n+7$ is an odd integer.
Proof. Let $n$ be an integer. We will prove that $n^2-5n+7$ is an odd integer by examining the case where $n$ is even and the case where $n$ is odd.

Case 1. The integer $n$ is even. In this case, there exists an integer $m$ such that $n=2m$. Therefore, $\mathrm{\dots }$.

As another example of using cases, consider a situation where we know that $a$ and $b$ are real numbers and $ab=0$. If we want to make a conclusion about $b$, the temptation might be to divide both sides of the equation by $a$. However, we can only do this if $a\ne 0$. So, we consider two cases: one when $a=0$ and the other when $a\ne 0$.

Proposition 3.22. For all real numbers $a$ and $b$, if $ab=0$, then $a=0$ or $b=0$.

Proof. We let $a$ and $b$ be real numbers and assume that $ab=0$. We will prove that $a=0$ or $b=0$ by considering two cases: (1) $a=0$, and (2) $a\ne 0$.

In the case where $a=0$, the conclusion of the proposition is true and so there is nothing to prove.

In the case where $a\ne 0$, we can multiply both sides of the equation $ab=0$
by $\frac{1}{a}$ and obtain

${\displaystyle \frac{1}{a}}\cdot ab$ $={\displaystyle \frac{1}{a}}\cdot 0$

$b$ $=0$

So in both cases, $a=0$ or $b=0$, and this proves that for all real numbers $a$ and $b$, if $ab=0$, then $a=0$ or $b=0$.

3.4.6 Absolute Value

Most students by now have studied the concept of the absolute value of a real number. We use the notation $|x|$ to stand for the absolute value of the real number $x$. One way to think of the absolute value of $x$ is as the "distance" between $x$ and 0 on the number line. For example,

$$|5|=5\text{ and }|-7|=7$$

Although this notion of absolute value is convenient for determining the absolute value of a specific number, if we want to prove properties about absolute value, we need a more careful and precise definition.

Definition. For $x\in ℝ$, we define $|x|$, called the absolute value of $𝒙$, by

Let’s first see if this definition is consistent with our intuitive notion of absolute value by looking at two specific examples.

• Since $5>0$, we see that $|5|=5$, which should be no surprise.

• Since , we see that $|-7|=-(-7)=7$.

Notice that the definition of the absolute value of $x$ is given in two parts, one for when $x\ge 0$ and the other for when . This means that when attempting to prove something about absolute value, we often use cases. This will be illustrated in Theorem 3.23.

Theorem 3.23. Let $a$ be a positive real number. For each real number $x$,

1. $|x|=a$ if and only if $x=a$ or $x=-a$.

2. $|-x|=|x|$.

Proof. The proof of Part (2) is part of Exercise (10). We will prove Part (1).
We let $a$ be a positive real number and let $x\in ℝ$. We will first prove that if $|x|=a$, then $x=a$ or $x=-a$. So we assume that $|x|=a$. In the case where $x\ge 0$, we see that $|x|=x$, and since $|x|=a$, we can conclude that $x=a$.

In the case where , we see that $|x|=-x$. Since $|x|=a$, we can conclude that $-x=a$ and hence that $x=-a$. These two cases prove that if $|x|=a$, then $x=a$ or $x=-a$.

We will now prove that if $x=a$ or $x=-a$, then $|x|=a$. We start by assuming that $x=a$ or $x=-a$. Since the hypothesis of this conditional statement is a disjunction, we use two cases. When $x=a$, we see that

$$|x|=|a|=a\text{ since }a>0$$

When $x=-a$, we conclude that

and hence, $|x|=a$. This proves that if $x=a$ or $x=-a$, then $|x|=a$. Because we have proven both conditional statements, we have proven that $|x|=a$ if and only if $x=a$ or $x=-a$.

3.4.7 Progress Check 3.24 (Equations Involving Absolute Values)

1. What is $|4.3|$ and what is $|-\pi |$ ?

2. Use the properties of absolute value in Theorem 3.23 to help solve the following equations for $t$, where $t$ is a real number.

   1. $|t|=12$.

   2. $|t+3|=5$.

   3. $|t-4|=\frac{1}{5}$.

   4. $|3t-4|=8$.

Although solving equations involving absolute values may not seem to have anything to do with writing proofs, the point of Progress Check 3.24 is to emphasize the importance of using cases when dealing with absolute value. The following theorem provides some important properties of absolute value.

Theorem 3.25. Let a be a positive real number. For all real numbers $x$ and $y$,

1. if and only if .

2. $|xy|=|x||y|$.

3. $|x+y|\le |x|+|y|$. This is known as the Triangle Inequality.

Proof. We will prove Part (1). The proof of Part (2) is included in Exercise (10), and the proof of Part (3) is Exercise (14). For Part (1), we will prove the biconditional proposition by proving the two associated conditional propositions.

So we let $a$ be a positive real number and let $x\in ℝ$ and first assume that . We will use two cases: either $x\ge 0$ or .

• In the case where $x\ge 0$, we know that $|x|=x$ and so the inequality implies that . However, we also know that and that $x>0$. Therefore, we conclude that and, hence, .

• When , we see that $|x|=-x$. Therefore, the inequality implies that , which in turn implies that . In this case, we also know that since $x$ is negative and $a$ is positive. Hence, .

So in both cases, we have proven that and this proves that if , then . We now assume that .

• If $x\ge 0$, then $|x|=x$ and hence, .

• If , then $|x|=-x$ and so $x=-|x|$. Thus, . By multiplying both sides of the last inequality by -1, we conclude that .

These two cases prove that if , then . Hence, we have proven that if and only if .

3.4.8 Exercises for Section 3.4

1. $(\star )$ In Beginning Activity 2, we proved that if $n$ is an integer, then $n^2+n$ is an even integer. We define two integers to be consecutive integers if one of the integers is one more than the other integer. This means that we can represent consecutive integers as $m$ and $m+1$, where $m$ is some integer.

   Explain why the result proven in Beginning Activity 2 can be used to prove that the product of any two consecutive integers is divisible by 2.

2. $(\star )$ Prove that if $u$ is an odd integer, then the equation $x^2+x-u=0$ has no solution that is an integer.

3. $(\star )$ Prove that if $n$ is an odd integer, then $n=4k+1$ for some integer $k$ or $n=4k+3$ for some integer $k$.

4. $(\star )$ Prove the following proposition: For each integer $a$, if $a^2=a$, then $a=0$ or $a=1$.

5. 1. Prove the following proposition:

      For all integers $a,b$, and $d$ with $d\ne 0$, if $d$ divides $a$ or $d$ divides $b$, then $d$ divides the product $ab$. Hint: Notice that the hypothesis is a disjunction. So use two cases.

   2. Write the contrapositive of the proposition in Exercise (5a).

   3. $(\star )$ Write the converse of the proposition in Exercise (5a). Is the converse true or false? Justify your conclusion.

6. Are the following propositions true or false? Justify all your conclusions. If a biconditional statement is found to be false, you should clearly determine if one of the conditional statements within it is true. In that case, you should state an appropriate theorem for this conditional statement and prove it.

   1. $(\star )$ For all integers $m$ and $n,m$ and $n$ are consecutive integers if and only if 4 divides $\left(m^2+n^2-1\right)$.

   2. For all integers $m$ and $n$, 4 divides $\left(m^2-n^2\right)$ if and only if $m$ and $n$ are both even or $m$ and $n$ are both odd.

7. Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.

   For each integer $n$, if $n$ is odd, then $8\mid \left(n^2-1\right)$.

8. $(\star )$ Prove that there are no natural numbers $a$ and $n$ with $n\ge 2$ and $a^2+1=2^n$.

9. Are the following propositions true or false? Justify each conclusion with a counterexample or a proof.

   1. For all integers $a$ and $b$ with $a\ne 0$, the equation $ax+b=0$ has a rational number solution.

   2. For all integers $a,b$, and $c$, if $a,b$, and $c$ are odd, then the equation $a{x}^2+bx+c=0$ has no solution that is a rational number. Hint: Do not use the quadratic formula. Use a proof by contradiction and recall that any rational number can be written in the form $\frac{p}{q}$, where $p$ and $q$ are integers, $q>0$, and $p$ and $q$ have no common factor greater than 1.

   3. For all integers $a,b,c$, and $d$, if $a,b,c$, and $d$ are odd, then the equation $a{x}^3+b{x}^2+cx+d=0$ has no solution that is a rational number.

10. 1. $(\star )$ Prove Part (2) of Theorem 3.23.

       For each $x\in ℝ,|-x|=|x|$.

    2. Prove Part (2) of Theorem 3.25.

       For all real numbers $x$ and $y,|xy|=|x||y|$.

11. Let $a$ be a positive real number. In Part (1) of Theorem 3.25, we proved that for each real number if and only if . It is important to realize that the sentence is actually the conjunction of two inequalities. That is, means that and .

    1. $(\star )$ Complete the following statement: For each real number $x,|x|\ge a$ if and only if ….

    2. Prove that for each real number $x,|x|\le a$ if and only if $-a\le x\le a$.

    3. Complete the following statement: For each real number $x,|x|>a$ if and only if ….

12. Prove each of the following:

    1. For each nonzero real number $x,\left|x^{-1}\right|=\frac{1}{|x|}$.

    2. For all real numbers $x$ and $y,|x-y|\ge |x|-|y|$.

       Hint: An idea that is often used by mathematicians is to add 0 to an expression "intelligently". In this case, we know that $(-y)+y=0$. Start by adding this "version" of 0 inside the absolute value sign of $|x|$.

    3. For all real numbers $x$ and $y,\parallel x|-|y||\le |x-y|$.

13. Evaluation of proofs. See the instructions for Exercise (19) from Section 3.1.

    1. Proposition. For all nonzero integers $a$ and $b$, if $a+2b\ne 3$ and $9a+2b\ne 1$, then the equation $a{x}^3+2bx=3$ does not have a solution that is a natural number.

       Proof. We will prove the contrapositive, which is
       For all nonzero integers $a$ and $b$, if the equation $a{x}^3+2bx=3$ has a solution that is a natural number, then $a+2b=3$ or $9a+2b=1$.
       So we let $a$ and $b$ be nonzero integers and assume that the natural number $n$ is a solution of the equation $a{x}^3+2bx=3$. So we have

       $a{n}^3+2bn$ $=3\text{ or}$

       $n\left(a{n}^2+2b\right)$ $=3.$

       So we can conclude that $n=3$ and $a{n}^2+2b=1$. Since we now have the value of $n$, we can substitute it in the equation $a{n}^3+2bn=3$ and obtain $27a+6b=3$. Dividing both sides of this equation by 3 shows that $9a+2b=1$. So there is no need for us to go any further, and this concludes the proof of the contrapositive of the proposition.

    2. Proposition. For all nonzero integers $a$ and $b$, if $a+2b\ne 3$ and $9a+2b\ne 1$, then the equation $a{x}^3+2bx=3$ does not have a solution that is a natural number.

       Proof. We will use a proof by contradiction. Let us assume that there exist nonzero integers $a$ and $b$ such that $a+2b=3$ and $9a+2b=1$ and $a{n}^3+2bn=3$, where $n$ is a natural number. First, we will solve one equation for $2b$; doing this, we obtain

       $a+2b$ $=3$

       $2b$ $=3-a.$ (1)

       We can now substitute for $2b$ in $a{n}^3+2bn=3$. This gives

       $a{n}^3+(3-a)n$ $=3$

       $a{n}^3+3n-an$ $=3$

       $n\left(a{n}^2+3-a\right)$ $=3$ (2)

       By the closure properties of the integers, $\left(a{n}^2+3-a\right)$ is an integer and, hence, equation (2) implies that $n$ divides 3. So $n=1$ or $n=3$. When we substitute $n=1$ into the equation $a{n}^3+2bn=3$, we obtain $a+2b=3$. This is a contradiction since we are told in the proposition that $a+2b\ne 3$. This proves that the negation of the proposition is false and, hence, the proposition is true.

3.4.9 Explorations and Activities

1. Proof of the Triangle Inequality.

   1. Verify that the triangle inequality is true for several different real numbers $x$ and $y$. Be sure to have some examples where the real numbers are negative.

   2. Explain why the following proposition is true: For each real number $r$, $-|r|\le r\le |r|$.

   3. Now let $x$ and $y$ be real numbers. Apply the result in Part (14b) to both $x$ and $y$. Then add the corresponding parts of the two inequalities to obtain another inequality. Use this to prove that $|x+y|\le |x|+|y|$.