# Proof by Cases

You can sometimes prove a statement by:

1. Dividing the situation into cases which exhaust all the possibilities; and

2. Showing that the statement follows in all cases.

It's important to cover all the possibilities. And don't confuse this with trying examples; an example is not a proof.

Note that there are usually many ways to divide a situation into cases. For example, if I know that x is a real number and I'm proving something about x, I could divide the situation into cases in these ways:

• , , or .
• or .
• or
• x is rational or x is irrational.

The division you choose depends on the situation. In general, you should try to use a small number of cases --- and in particular, you should see if you can give a proof without taking cases at all!

Example. Premises:

Prove: .

I can divide the situation into two cases: Either C is true, or is true. These exhaust the possibilities, by the Law of the Excluded Middle. I'll assume each in turn and show that I can derive .

Since both of my cases led to the conclusion , and since my cases exhausted the possibilities, I've proved .

In logic proofs, cases of the form P and where P is some statement will cover all possibilities, since one of P or must be true. So these are the natural cases to take in logic proofs.

How did I know to use C and rather than (say) B and ? I looked at my premises and noticed that I could do something with each of those assumptions: C could be used for modus ponens, and could be used for disjunctive syllogism. As with many logic proofs, it was a matter of looking ahead or working backward.

Note: You may use the premises for the proof in either case, but you may not use a statement derived for one case in the other case.

For example, in the first case, I derived the statement A at line 5. I may not use A anywhere in the second case.

Example. In calculus, you learned Rolle's theorem. Here's the statement:

\item{} Let f be a function which is continuous on the interval and is differentiable on the interval . Suppose . Then there is a real number c such that and .

In other words (to put it roughly), between two roots there must be a horizontal tangent.

There are three cases: f is never positive or negative on the interval , f is positive somewhere on the interval , or f is negative somewhere on the interval .

Suppose first that f is never positive or negative on the interval . Then , a constant function, and for all x in the interval .

Suppose that f is positive at some point of the interval . A continuous function on a closed interval attains a maximum value on the interval; since I already know f is positive somewhere, the maximum value of f must be positive. Since f is 0 at the endpoints, it must attain the maximum value at some point c in the open interval .

Since , f is differentiable at c. But at a point where a differentiable function attains a maximum, the derivative is 0. Therefore, .

Suppose that f is negative at some point of the interval . A continuous function on a closed interval attains a minimum value on the interval; since I already know f is negative somewhere, the minimum value of f must be negative. Since f is 0 at the endpoints, it must attain the minimum value at some point c in the open interval .

Since , f is differentiable at c. But at a point where a differentiable function attains a minimum, the derivative is 0. Therefore, .

Since the three cases exhaust all the possibilities, this proves that for some c in the interval .

Many problems involving divisibility of integers use the Division Algorithm. It is a consequence of the Well-Ordering Axiom for the positive integers, which is also the basis for mathematical induction.

Theorem. (Division Algorithm) Let m and n be integers, where . Then there are unique integers q and r such that

("q" stands for "quotient" and "r" stands for "remainder".)

I won't give a proof of this, but here are some examples which show how it's used.

Examples. (a) Let and . Then I have

In this case, and . Note that holds --- when you divide, the remainder should be nonnegative, and less than the number you divided by.

(b) (a) Let and . Then I have

In this case, and . Again, holds. Note that if I wrote " ", the equation is true, but the numbers aren't the ones produced by the Division Algorithm --- r is not allowed to be negative.

(c) Take m to be any integer, and let . Then

Now since r is an integer and , I must have or . Thus, if , then

Of course, the first case occurs when m is even, and the second case occurs when m is odd. If a problem involves odd or even integers, you might consider taking cases in this way.

A similar situation occurs when n is any positive integer. For example, if and , then

The condition means , , , , or . So if , the possibilities are

If a problem involves divisibility by 5 you might consider taking cases in this way.

(When I discuss modular arithmetic, there will be an easier way to deal with these cases.)

Example. Prove that if n is an integer, then is even.

Let . I'll consider two cases: n is even and n is odd.

Case 1. n is even.

Since n is even, I can write , where . Then

Since is an integer, is even if n is even.

Case 2. n is odd.

Since n is odd, I can write , where . Then

Since is an integer, is even if n is odd.

Since in both cases is even, it follows that if n is an integer, then is even.

Example. Prove that if n is any integer which is not divisible by 5, then leaves a remainder of 1 or 4 when it is divided by 5.

Let n be an integer which is not divisible by 5. I want to show that leaves a remainder of 1 or 4 when it is divided by 5.

Since n is not divisible by 5, it leaves a remainder of 1, 2, 3, or 4 when it is divided by 5. These four cases exhaust all the possibilities.

If n leaves a remainder of 1 when it's divided by 5, then for some integer k. So

Therefore, leaves a remainder of 1 when it's divided by 5.

If n leaves a remainder of 2 when it's divided by 5, then for some integer k. So

Therefore, leaves a remainder of 4 when it's divided by 5.

If n leaves a remainder of 3 when it's divided by 5, then for some integer k. So

Therefore, leaves a remainder of 4 when it's divided by 5.

If n leaves a remainder of 4 when it's divided by 5, then for some integer k. So

Therefore, leaves a remainder of 1 when it's divided by 5.

I've exhausted all the cases. This proves that if n is any integer which is not divisible by 5, then leaves a remainder of 1 or 4 when it is divided by 5.

This is not the best way to write this kind of proof, since the algebra can be a bit annoying. Proofs like this one can be written more easily using modular arithmetic.

Example. Prove that for all ,

You often think of taking cases in dealing with absolute values. I have

Now means , and means . So

In the same way,

Given the way the functions are broken apart, I'll consider the cases , , and . Notice that all real numbers are in one of the three cases.

Case 1. . In this case,

Therefore, holds in this case.

Case 2. . In this case,

I have to do some additional work to see whether the target inequality holds. I have

Therefore, holds in this case.

Case 3. . In this case,

Therefore, holds in this case.

Since holds all three cases, it is true for all .