Using Cases in Proofs

🔗

Section 3.4 Using Cases in Proofs

🔗

Beginning Activity Beginning Activity 1: Using a Logical Equivalency
A4 US

🔗

1.

Complete a truth table to show that $(P \lor Q) \to R$ is logically equivalent to $(P \to R) \land (Q \to R) .$

🔗

2.

Suppose that you are trying to prove a statement that is written in the form $(P \lor 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 $x y$ 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 $x y$ is an even integer. Also, prove that if $y$ is an even integer, then $x y$ is an even integer.

🔗

5.

Use the results proved in Exercise 4 and the explanation in Exercise 2 to explain why we have proved the contrapositive of the proposition in Exercise 3.

🔗

Beginning Activity Beginning Activity 2: Using Cases in a Proof
A4 US

🔗

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 \lor Q) \to R] \equiv [(P \to R) \land (Q \to R)] .

🔗

See Theorem 2.12 and Exercise 6.

🔗

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 $(n^{2} + n)$ 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 = 2 m .$ Substituting this into the expression $n^{2} + n$ yields ….

🔗

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.

🔗

Subsection 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 irrational.

Case 2: $x$ is irrational.

When the hypothesis is, “ $x$ is a real number.”

Case 1: $a = b .$

Case 2: $a \neq b .$

Case 1: $a > b .$

Case 2: $a = b .$

Case 3: $a < b .$

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

Case 1: $a = b .$

Case 2: $a \neq b .$

Case 1: $a > b .$

Case 2: $a = b .$

Case 3: $a < b .$

🔗

Subsection 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 ….”

🔗

Progress Check 3.26. Using Cases: $n$ Is Even or $n$ Is Odd.

Complete the proof of the following proposition:

Proposition: For each integer $n,$ $n^{2} - 5 n + 7$ is an odd integer.

Proof: Let $n$ be an integer. We will prove that $n^{2} - 5 n + 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 = 2 m .$ Therefore, … .

Solution.

Proposition: For each integer $n,$ $n^{2} - 5 n + 7$ is an odd integer.

🔗

Proof.

Let $n$ be an integer. We will prove that $n^{2} - 5 n + 7$ is an odd integer by examining the case where $n$ is even and the case where $n$ is odd.

In the case where $n$ is even, there exists an integer $m$ such that $n = 2 m .$ So in this case,

\begin{aligned} n^{2} - 5 n + 7 & = {(2 m)}^{2} - 5 (2 m) + 7 \\ = 4 m^{2} - 10 m + 6 + 1 \\ = 2 (2 m^{2} - 5 m + 3) + 1 . \end{aligned}

Since $(2 m^{2} - 5 m + 3)$ is an integer, the last equation shows that if $n$ is even, then $n^{2} - 5 n + 7$ is odd.

In the case where $n$ is odd, there exists an integer $m$ such that $n = 2 m + 1 .$ So in this case,

\begin{aligned} n^{2} - 5 n + 7 & = {(2 m + 1)}^{2} - 5 (2 m + 1) + 7 \\ = 4 m^{2} - 6 m + 3 \\ = 2 (2 m^{2} - 3 m + 1) + 1 . \end{aligned}

Since $(2 m^{2} - 3 m + 1)$ is an integer, the last equation shows that if $n$ is odd, then $n^{2} - 5 n + 7$ is odd. Hence, by using these two cases, we have shown that for each integer $n,$ $n^{2} - 5 n + 7$ is an odd integer.

🔗

As another example of using cases, consider a situation where we know that

a

and

b

are real numbers and

a b = 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 \neq 0 .

So, we consider two cases: one when

a = 0

and the other when

a \neq 0 .

🔗

Proposition 3.27.

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

🔗

Proof.

We let $a$ and $b$ be real numbers and assume that $a b = 0 .$ We will prove that $a = 0$ or $b = 0$ by considering two cases: (1) $a = 0,$ and (2) $a \neq 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 \neq 0,$ we can multiply both sides of the equation $a b = 0$ by $\frac{1}{a}$ and obtain

\begin{aligned} \frac{1}{a} \cdot a b & = \frac{1}{a} \cdot 0 \\ b & = 0 . \end{aligned}

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

🔗

Subsection 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 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 R,$ we define $| x |,$ called the absolute value of x, by

| x | = {\begin{cases} x, & if x \geq 0; \\ - x & if x < 0 . \end{cases}

🔗

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 $- 7 < 0,$ 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 \geq 0

and the other for when

x < 0 .

This means that when attempting to prove something about absolute value, we often uses cases. This will be illustrated in Theorem 3.28.

🔗

Theorem 3.28.

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

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

🔗

Proof.

The proof of Item 2 is part of Exercise 10. We will prove Item 1.

We let $a$ be a positive real number and let $x \in R .$ 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 \geq 0,$ we see that $| x | = x,$ and since $| x | = a,$ we can conclude that $x = a .$

In the case where $x < 0,$ 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 since a > 0 .

When $x = - a,$ we conclude that

| x | = | - a | = - (- a) since - a < 0,

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 .$

🔗

Progress Check 3.29.

🔗

(a)

What is $| 4.3 |$ and what is $| - π | ?$

Solution.

$| 4.3 | = 4.3$ and $| - π | = π$

🔗

(b)

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

🔗

(i)

$| t | = 12 .$

Solution.

$t = 12$ or $t = - 12 .$

🔗

(ii)

$| t + 3 | = 5 .$

Solution.

$t + 3 = 5$ or $t + 3 = - 5 .$ So $t = 2$ or $t = - 8 .$

🔗

(iii)

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

Solution.

$t - 4 = \frac{1}{5}$ or $t - 4 = - \frac{1}{5} .$ So $t = \frac{21}{5}$ or $t = \frac{19}{5} .$

🔗

(iv)

$| 3 t - 4 | = 8 .$

Solution.

$3 t - 4 = 8$ or $3 t - 4 = - 8 .$ So $t = 4$ or $t = - \frac{4}{3} .$

🔗

Although solving equations involving absolute values may not seem to have anything to do with writing proofs, the point of Progress Check 3.29 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.30.

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

$| x | < a$ if and only if $- a < x < a .$
$| x y | = | x | | y | .$
$| x + y | \leq | x | + | y | .$ This is known as the Triangle Inequality.

🔗

Proof.

We will prove Item 1. The proof of Item 2 is included in Exercise 10, and the proof of Item 3 is Activity 16. For Item 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 R$ and first assume that $| x | < a .$ We will use two cases: either $x \geq 0$ or $x < 0 .$

In the case where $x \geq 0,$ we know that $| x | = x$ and so the inequality $| x | < a$ implies that $x < a .$ However, we also know that $- a < 0$ and that $x > 0 .$ Therefore, we conclude that $- a < x$ and, hence, $- a < x < a .$
When $x < 0,$ we see that $| x | = - x .$ Therefore, the inequality $| x | < a$ implies that $- x < a,$ which in turn implies that $- a < x .$ In this case, we also know that $x < a$ since $x$ is negative and $a$ is positive. Hence, $- a < x < a .$

So in both cases, we have proven that $- a < x < a$ and this proves that if $| x | < a,$ then $- a < x < a .$ We now assume that $- a < x < a .$

If $x \geq 0,$ then $| x | = x$ and hence, $| x | < a .$
If $x < 0,$ then $| x | = - x$ and so $x = - | x | .$ Thus, $- a < - | x | .$ By multiplying both sides of the last inequality by $- 1,$ we conclude that $| x | < a .$

These two cases prove that if $- a < x < a,$ then $| x | < a .$ Hence, we have proven that $| x | < a$ if and only if $- a < x < a .$

🔗

Exercises Exercises

🔗

1.

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.

Hint.

Use the fact that $n^{2} + n = n (n + 1) .$

🔗

2.

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

Answer.

Do not use the quadratic formula. Try a proof by contradiction. If there exists a solution of the equation $x^{2} + x - u = 0$ that is an integer, then we can conclude that there exists an integer $n$ such that $n^{2} + n - u = 0 .$ Then,

u = n (n + 1) .

From Exercise 1, we know that $n (n + 1)$ is even and hence, $u$ is even. This contradicts the assumption that $u$ is odd.

🔗

3.

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

Answer.

If $n$ is an odd integer, then there exists an integer $m$ such that $n = 2 m + 1 .$ Use two cases: (1) $m$ is even; (2) $m$ is odd. If $m$ is even, then there exists an integer $k$ such that $m = 2 k$ and this means that $n = 2 (2 k) + 1$ or $n = 4 k + 1 .$ If $m$ is odd, then there exists an integer $k$ such that $m = 2 k + 1 .$ Then $n = 2 (2 k + 1) + 1$ or $n = 4 k + 3 .$

🔗

4.

Prove the following proposition:

For each integer $a,$ if $a^{2} = a,$ then $a = 0$ or $a = 1 .$

Answer.

If $a \in Z$ and $a^{2} = a,$ then $a (a - 1) = 0 .$ Since the product is equal to zero, at least one of the factors must be zero. In the first case, $a = 0 .$ In the second case, $a - 1 = 0$ or $a = 1 .$

🔗

5.

Complete the following.

🔗

(a)

Prove the following proposition:

For all integers $a,$ $b,$ and $d$ with $d \neq 0,$ if $d$ divides $a$ or $d$ divides $b,$ then $d$ divides the product $a b .$

Hint.

Notice that the hypothesis is a disjunction. So use two cases.

🔗

(b)

Write the contrapositive of the proposition in Task 5.a.

🔗

(c)

Write the converse of the proposition in Task 5.a. Is the converse true or false? Justify your conclusion.

Answer.

For all integers $a,$ $b,$ and $d$ with $d \neq 0,$ if $d$ divides the product $a b,$ then $d$ divides $a$ or $d$ divides $b .$

🔗

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.

🔗

(a)

For all integers $m$ and $n,$ $m$ and $n$ are consecutive integers if and only if 4 divides $(m^{2} + n^{2} - 1) .$

Answer.

The statement, for all integers $m$ and $n,$ if 4 divides $(m^{2} + n^{2} - 1),$ then $m$ and $n$ are consecutive integers, is false. A counterexample is $m = 2$ and $n = 5 .$ The statement, for all integers $m$ and $n,$ if $m$ and $n$ are consecutive integers, then 4 divides $(m^{2} + n^{2} - 1),$ is true. To prove this, let $n = m + 1 .$ Then

m^{2} + n^{2} - 1 = 2 m^{2} + 2 m = 2 m (m + 1) .

We have proven the $m (m + 1)$ is even. (Exercise 1) So this can be used to prove that 4 divides $(m^{2} + n^{2} - 1) .$

🔗

(b)

For all integers $m$ and $n,$ 4 divides $(m^{2} - n^{2})$ 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 ∣ (n^{2} - 1) .$

🔗

8.

Prove that there are no natural numbers $a$ and $n$ with $n \geq 2$ and $a^{2} + 1 = 2^{n} .$

Hint.

Try a proof by contradiction with two cases: $a$ is even or $a$ is odd.

🔗

9.

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

🔗

(a)

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

🔗

(b)

For all integers $a,$ $b,$ and $c,$ if $a,$ $b,$ and $c$ are odd, then the equation $a x^{2} + b x + 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.

🔗

(c)

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} + c x + d = 0$ has no solution that is a rational number.

🔗

10.

Prove the following.

🔗

(a)

Item 2 of Theorem 3.28.

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

Answer.

One way is to use three cases: (i) $x > 0;$ (ii) $x = 0;$ and $x < 0 .$ For the first case, $- x < 0$ and $| - x | = - (- x) = x = | x | .$

🔗

(b)

Item 2 of Theorem 3.30.

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

🔗

11.

Let $a$ be a positive real number. In Item 1 of Theorem 3.30, we proved that for each real number $x,$ $| x | < a$ if and only if $- a < x < a .$ It is important to realize that the sentence $- a < x < a$ is actually the conjunction of two inequalities. That is, $- a < x < a$ means that $- a < x$ and $x < a .$

🔗

(a)

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

Answer.

For each real number $x,$ $| x | \geq a$ if and only if $x \geq a$ or $x \leq - a .$

🔗

(b)

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

🔗

(c)

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

🔗

12.

Prove each of the following:

🔗

(a)

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

🔗

(b)

For all real numbers $x$ and $y,$ $| x - y | \geq | 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 | .$

🔗

(c)

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

🔗

13. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

🔗

(a)

Proposition

For all nonzero integers $a$ and $b,$ if $a + 2 b \neq 3$ and $9 a + 2 b \neq 1,$ then the equation $a x^{3} + 2 b x = 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} + 2 b x = 3$ has a solution that is a natural number, then $a + 2 b = 3$ or $9 a + 2 b = 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} + 2 b x = 3 .$ So we have

\begin{aligned} a n^{3} + 2 b n & = 3 or \\ n (a n^{2} + 2 b) & = 3 . \end{aligned}

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

🔗

(b)

Proposition

For all nonzero integers $a$ and $b,$ if $a + 2 b \neq 3$ and $9 a + 2 b \neq 1,$ then the equation $a x^{3} + 2 b x = 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 + 2 b = 3$ and $9 a + 2 b = 1$ and $a n^{3} + 2 b n = 3,$ where $n$ is a natural number. First, we will solve one equation for $2 b;$ doing this, we obtain

\begin{aligned} a + 2 b & = 3 \\ (11) & 2 b & = 3 - a \end{aligned}

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

\begin{aligned} a n^{3} + (3 - a) n & = 3 \\ a n^{3} + 3 n - a n & = 3 \\ (12) & n (a n^{2} + 3 - a) & = 3) \end{aligned}

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

🔗

Activity 16. Proof of the Triangle Inequality.

🔗

(a)

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.

🔗

(b)

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

🔗

(c)

Now let $x$ and $y$ be real numbers. Apply the result in Task 16.b 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 | \leq | x | + | y | .$

Section 3.4 Using Cases in Proofs

Beginning Activity Beginning Activity 1: Using a Logical Equivalency A4US

1.

2.

3.

Proposition.

4.

5.

Beginning Activity Beginning Activity 2: Using Cases in a Proof A4US

Proposition 1.

1.

Proposition 2.

Proof.

2.

Proposition 3.

3.

Subsection Some Common Situations to Use Cases

Subsection Writing Guidelines for a Proof Using Cases

Progress Check 3.26. Using Cases: n Is Even or n Is Odd.

Proof.

Proposition 3.27.

Proof.

Subsection Absolute Value

Definition.

Theorem 3.28.

Proof.

Progress Check 3.29.

(a)

(b)

(i)

(ii)

(iii)

(iv)

Theorem 3.30.

Proof.

Exercises Exercises

1.

2.

3.

4.

5.

(a)

(b)

(c)

6.

(a)

(b)

7.

8.

9.

(a)

(b)

(c)

10.

(a)

(b)

11.

(a)

(b)

(c)

12.

(a)

(b)

(c)

13. Evaluation of Proofs.

(a)

(b)

Activity 16. Proof of the Triangle Inequality.

(a)

(b)

(c)

Beginning Activity Beginning Activity 1: Using a Logical Equivalency
A4 US

Beginning Activity Beginning Activity 2: Using Cases in a Proof
A4 US

Progress Check 3.26. Using Cases: $n$ Is Even or $n$ Is Odd.