Proof by exhaustion

Proof by exhaustion is a special way to show that a math idea is true. It works by looking at every single case that could happen and showing the idea works for each one. The cases need to be separate from each other and together they must cover everything that could be possible.

Because we now have computers, it has become easier to use this method. For example, in 1976, a computer helped prove a famous math idea called the four color theorem. Some people worry that using computers this way might not be the most elegant way to solve a math problem.

In theory, you can use proof by exhaustion whenever there are only a few cases to check. But because most math ideas deal with endless numbers or situations, this method is not often used for big, general math results.

General structure

A proof by cases is a way to show that something is true by checking every possible situation. First, you list all the different situations that could happen. Then, you show that the statement is true for each situation, one by one. Finally, if the statement is true for every situation, you can say it is true overall. If it is not true for even one situation, then the statement is not true.

Usage

Proof by cases is used when a problem can be split into clear groups, such as:

• Even and odd numbers
• Positive numbers, negative numbers, and zero
• Different parts of a math rule

This way of proving things works well when one simple argument can't cover every situation by itself.

Example

Prove that for any whole number n, the number n² is even if n is even, and n² is odd if n is odd.

We can show this by looking at two different situations:

Case 1

• n is even
• Then n can be written as 2k for some whole number k
• Then n² = (2k)² = 4k² = 2(2k²), which is even

Case 2

• n is odd
• Then n can be written as 2k+1 for some whole number k
• Then n² = (2k+1)² = 4k² + 4k +1 = 2(2k² + 2k) +1, which is odd

Since we have proven both situations, the statement is true for all whole numbers n.

Prove that if a whole number is a perfect cube, then it must be either a multiple of 9, 1 more than a multiple of 9, or 1 less than a multiple of 9.

Each perfect cube comes from a whole number n, where n is either a multiple of 3, 1 more than a multiple of 3, or 1 less than a multiple of 3. So we look at these three situations:

• Case 1: If n = 3p, then n³ = 27p³, which is a multiple of 9.
• Case 2: If n = 3p + 1, then n³ = 27p³ + 27p² + 9p + 1, which is 1 more than a multiple of 9. For example, if n = 4 then n³ = 64 = 9×7 + 1.
• Case 3: If n = 3p − 1, then n³ = 27p³ − 27p² + 9p − 1, which is 1 less than a multiple of 9. For example, if n = 5 then n³ = 125 = 9×14 − 1. Q.E.D.

Elegance

Mathematicians do not like to use proofs by exhaustion when there are many cases, because these proofs are not simple or neat. A proof is considered elegant when it is simple and effective. Proof by exhaustion works best when there are only a few possible outcomes and becomes harder when there are many or infinite outcomes.

For example, we can show that all modern Summer Olympic Games happen in years divisible by 4 in two ways. One way uses a special method called mathematical induction. Another way is to list every year the Olympics were held and check each one — as of 2016, there were 28 Olympics to check. While this works, it needs extra checking each time a new Olympics happens, unlike the induction method which works forever.

Number of cases

In a proof by exhaustion, you can have as many different situations or "cases" as you need. Sometimes there are just a few cases, but other times there can be thousands or even millions of cases to check. For example, solving a difficult chess endgame puzzle might need looking at many possible positions in the game tree.

One famous example is the first proof of the four colour theorem, which needed to check many different cases. Most of these were checked by a computer. Even today, the shortest proof of this theorem still has many cases. While having many cases can make a proof seem less elegant, sometimes it is the only way to prove certain important ideas, like the proof that there is no finite projective plane of order 10, or the classification of finite simple groups. Other big theorems, such as the Kepler conjecture and the Boolean Pythagorean triples problem, also required this method.

Other types of proofs, like proof by induction (mathematical induction), are often thought of as more elegant.