Proof Technique: Casework

Previously, we talked about a proof technique where we examine every single element of a finite set. In a sense, we examined multiple cases, and verified some result for each of those cases. An exhaustive proof is a special kind of proof by casework.

Sometimes, we may have trouble demonstrating that some result holds for a set of elements. However, if we partition the set into groups that have their own special traits, and those traits make it easy to show the desired result holds, a proof by casework can be used to establish the desired result for the entire set.

The Underlying Argument

Suppose we were trying to prove a statement of the form

p → c

Suppose that we somehow knew that

p = p₁ ∨ p₂ ∨ p₃ ∨ … ∨ p_n

If we knew how to show that

p₁	→	c
p₂	→	c
p₃	→	c
⋮	⋮	⋮
p_n	→	c

We would then have that

(p₁ ∨ p₂ ∨ p₃ ∨ … ∨ p_n) → c

Thus, because p = p₁ ∨ p₂ ∨ p₃ ∨ … ∨ p_n, we would also have that

p → c

by extension.

	p → r
	q → r
∴	(p ∨ q) → r

Figure 3.8.1: Using casework is just using the proof by cases rule of inference.

This proof technique is simply an extension of the Rule of Proof by Cases as presented in Chapter 2, Section 2. Even though we could have discussed this proof technique in Chapter 2, we decided to hold off until partitions were discussed because a lot of casework is done by considering elements from disjoint sets. However, when doing casework, it’s not important that elements from the universe of discourse are in only one subset of a partition.

Whether we form a partition of the universe, or we split the universe up into overlapping subsets is not important. What’s important is that, once we have our desired subsets, that every element is represented by at least one of those subsets.

Picking Arbitrary Elements from a Partition

When we partition a set, we split it into disjoint subsets where every element is accounted for in one of the subsets. We don’t have to form these subsets arbitrarily. Instead, we could take all elements from the original set that have some common property, and stick those elements into a subset. We can repeat this process until all elements are accounted for.

Then, from each of these subsets, we choose an arbitrary element. Then, whatever is true of that element will be true for all elements within that subset. In essence, we are using the principles of Universal Specification and Universal Generalization along with a partition to prove a theorem.

Our first theorem will be a result about absolute values of real numbers. As a reminder, here’s the definition of absolute value of a real number.

Absolute Value

For any real number x, the absolute value of x, commonly denoted

|x|

is the non-negative real number given by the following:

|x| = x when x ≥ 0

|x| = -x when x < 0

Another way to think of absolute value of a number is as a distance from 0.

Theorem 3.8.1

For any two real numbers x and y, we have that

|xy| = |x||y|

Proof

General Strategy: Because the absolute value changes based on whether the given number is negative, or non-negative, we can consider combinations of negative and non-negative numbers for x and y respectively.

We can start by partitioning the real numbers into two subsets: one subset will be the real numbers greater than or equal to 0, and the other subset will be the real numbers less than 0.

ℝ^*	=	{ x \| x ≥ 0 }
ℝ^–	=	{ x \| x < 0 }

Notice that we have two variables x and y. Because of how we partitioned the real numbers, we can pick values for x and y from either ℝ^* or ℝ^–.

This gives us four cases to check.

Case 1: x ∈ ℝ^, y ∈ ℝ^

Because both x ≥ 0 and y ≥ 0, we have that xy ≥ 0. We also have that |x| = x and |y| = y. This tells us that

\|xy\|	=	xy
	=	\|x\|\|y\|

which is the desired result.

Case 2: x ∈ ℝ^*, y ∈ ℝ^–

Because y < 0, we have that |y| = -y. We still have that |x| = x. Additionally we know that xy < 0, and so |xy| = -xy. This tells us that

\|xy\|	=	-xy
	=	x(-y)
	=	\|x\|\|y\|

We’ve reached the same desired result.

Case 3: x ∈ ℝ^–, y ∈ ℝ^*

This case is just a mirrored version of case 2, and so we will get the same result.

Case 4: x ∈ ℝ^–, y ∈ ℝ^–

Since both x and y are less than 0, we have that |x| = -x and |y| = -y. However, notice that since both x and y are negative, their product xy will be positive, and so |xy| = xy. This gives us the following result:

\|xy\|	=	xy
	=	(1)xy
	=	(-1)(-1)xy
	=	(-1)x(-1)y
	=	(-x)(-y)
	=	\|x\|\|y\|

Here, we used the fact that 1 = -1 * -1. We also used the commutative property of multiplication to move around the numbers.

Conclusion

In all four cases, we achieved the result as desired.

An Example with Lots of Cases

Here, we are going to discuss perfect squares and what kinds of numbers can be the units digits of perfect squares. Before we discuss the next theorem, let’s make some observations about the non-negative integers.

Example 3.8.1

Observe the following:

0	=	0 + 0	=	10(0) + 0
1	=	0 + 1	=	10(0) + 1
5	=	0 + 5	=	10(0) + 5
13	=	10 + 3	=	10(1) + 3
17	=	10 + 7	=	10(1) + 7
453	=	450 + 3	=	10(45) + 3
102706	=	102700 + 6	=	10(10270) + 6

What we see is that any non-negative integer can be written as

10a + b

where a is any non-negative integer and b is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

This will be important to use in our next theorem, but for now we can organize this observation using the following table

n = 10a + b
	a
b	0	1	2	3	4	5	6	7	8	9	…
0	0	10	20	30	40	50	60	70	80	90
1	1	11	21	31	41	51	61	71	81	91
2	2	12	22	32	42	52	62	72	82	92
3	3	13	23	33	43	53	63	73	83	93
4	4	14	24	34	44	54	64	74	84	94
5	5	15	25	35	45	55	65	75	85	95
6	6	16	26	36	46	56	66	76	86	96
7	7	17	27	37	47	57	67	77	87	97
8	8	18	28	38	48	58	68	78	88	98
9	9	19	29	39	49	59	69	79	89	99

From the observations presented in Example 3.8.1, we see that any non-negative integer can be written as

10a + b

This observation will help us in this upcoming theorem.

Theorem 3.8.2

The only numbers that can occur in the units digit of a perfect square are

0, 1, 4, 5, 6, and 9.

Proof

General Strategy: We use the observation in Example 3.8.1 that any non-negative integer can be written as 10a + b. We square that quantity to see what determines the units digit of any perfect square.

Any non-negative integer can be written as

10a + b

where a is any non-negative integer (0, 1, 2, 3, 4, 5, …) and b can only be one of 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

When we square that number, we see that

(10a + b)²	=	(10a + b)(10a + b)
	=	100a² + 10ab + 10ab + b²
	=	100a² + 20ab + b²
	=	10(10a² + 2ab) + b²

Because the quantity 10a² + 2ab is being multiplied by 10, the units digit of the number

(10a + b)²

will be the same units digit as b². Remember that b can only take on one of ten values. Thus we could simply check each of those values and see if some pattern emerges.

Case 1: b = 0

When b = 0, we have that b² = 0. The units digit of 0 is of course 0, so the units digit of

(10a + b)²

will also be 0.

Case 2: b = 1

When b = 1, we have that b² = 1. The units digit of 1 is of course 1, so the units digit of

(10a + b)²

will also be 1.

Case 3: b = 2

When b = 2, we have that b² = 4. The units digit of 4 is of course 4, so the units digit of

(10a + b)²

will also be 4.

Case 4: b = 3

When b = 3, we have that b² = 9. The units digit of 9 is of course 9, so the units digit of

(10a + b)²

will also be 9.

Case 5: b = 4

When b = 4, we have that b² = 16. The units digit of 16 is 6, so the units digit of

(10a + b)²

will also be 6.

Case 6: b = 5

When b = 5, we have that b² = 25. The units digit of 25 is 5, so the units digit of

(10a + b)²

will also be 5.

Case 7: b = 6

When b = 6, we have that b² = 36. The units digit of 36 is 6, so the units digit of

(10a + b)²

will also be 6.

Case 8: b = 7

When b = 7, we have that b² = 49. The units digit of 49 is 9, so the units digit of

(10a + b)²

will also be 9.

Case 9: b = 8

When b = 8, we have that b² = 64. The units digit of 64 is of course 4, so the units digit of

(10a + b)²

will also be 4.

Case 10: b = 9

When b = 9, we have that b² = 81. The units digit of 81 is 1, so the units digit of

(10a + b)²

will also be 1.

Conclusion

After examining all ten cases, we see that the only units digits encountered were

0, 1, 4, 5, 6, and 9.

This establishes the desired result.

A Common Mistake

The most common error that can occur when doing a proof by cases is not accounting for every element in the universe being considered. It is essential that all the cases you consider account for every possible element.

Example 3.8.2

Consider the universe of all integers.

Whether we have a negative or positive integer, squaring that integer yields a number that is either larger, or equal, to the original integer.

For example, when we start with a positive integer n ≥ 1, we have that

n ≥ 1 ⟹ n² ≥ n

Likewise, squaring any negative integer always yields a positive integer like so:

n ≤ -1 ⟹ n² ≥ -n ≥ n

It may seem like Example 3.8.2 demonstrates that

n² ≥ n

for all integers. After all, we showed it was true for positive integers and negative integers. However, there is one integer that is neither positive or negative, namely 0. In this situation, since it’s only one integer left unaccounted for, we could simply compute 0² and compare it to 0 to determine that the above statement is indeed true for all integers. We formalize this proof now.

Theorem 3.8.2

For any integer n, we have that

n ≤ n²

Proof

General Strategy: Here, we’ll partition the integers into three subsets. We’ll consider negative integers, positive integers, and 0.

Case 1: n < 0

All square numbers are greater than or equal to 0, meaning n² ≥ 0.

Since n < 0 and n² ≥ 0, we necessarily have that

n ≤ n²

as desired.

Case 2: n = 0

Here, since 0² = 0, we also have that 0 ≤ 0².

This gives us that

n ≤ n²

as desired.

Case 3: n > 0

Since n is an integer > 0, we have that n ≥ 1. Multiplying both sides by n gives us that

n² ≥ n

as desired.

Conclusion

All integers are accounted for with the three cases presented above. Hence we have the desired result.

The Book ofFoundational Mathematics

Quick Links