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 .

Copyright 2009 by Bruce Ikenaga