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, here are some ways I could take cases:
(a) ,
, or
.
(b) or
.
(c) or
(d) x is rational or x is irrational.
There are an infinite number of ways to divide up the real numbers to take cases; how you do it depends on what you're trying to prove. 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!
I'll begin with a logic proof. In this situation, your cases are
usually P and , where P is a statement.
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:
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.
Prove Rolle's Theorem by taking cases.
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.
Example. Apply the Division Algorithm to:
(a) Divide 31 by 8.
(b) Divide -31 by 8.
(c) Divide an integer m by 2.
(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 an 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 an integer, then
is not divisible by 3.
When n is divided by 3, the possible remainders are 0, 1, or 2. I consider these three cases.
Case 1. When n is divided by 3, the remainder is 0.
Then for some integer q. So
The last expression shows that in this case when is divided by 3, the remainder is 1. Hence,
is not divisible by 3.
Case 2. When n is divided by 3, the remainder is 1.
Then for some integer q. So
The last expression shows that in this case when is divided by 3, the remainder is 1. Hence,
is not divisible by 3.
Case 3. When n is divided by 3, the remainder is 2.
Then for some integer q. So
The last expression shows that in this case when is divided by 3, the remainder is 2. Hence,
is not divisible by 3.
Since in every case is not divisible by 3, it
follows that
is not divisible by 3 for any
integer n.
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 2019 by Bruce Ikenaga