Proofs by exhaustion

This article page is a stub, please help by expanding it.

Not to be confused with Archimedes' method of exhaustion (methodus exhaustionibus, or méthode des anciens).

Proof by exhaustion, also known as proof by cases, perfect induction, or the brute force method, is a method of proof in which the statement to be proved is split into a finite number of cases and each case is checked to see if the proposition in question holds. A proof by exhaustion contains three stages:

1. Splitting up the statement into a finite (usually as small as possible) number of cases;
2. A proof that the cases are exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases;
3. A proof of each of the cases.

Proof by exhaustion is considered the least elegant (the more so the more cases there are...) kind of proof, and usually don't give the insight obtained with other kinds of proofs.

Examples

• The first proof of the four colour theorem was a proof by exhaustion with 1,936 cases. The shortest known proof of the four colour theorem today still has over 600 cases.
• One way to prove that every positive integer can be expressed as a sum of five positive squares (with the exception of the twelve numbers listed in A047701) is to exhibit the five-square sum for each of the integers up to 169 (see table of positive integers as sums of five positive squares) and then demonstrate how the infinity of cases $n>169$ reduce to one of 157 cases.

See also

• Computer-assisted proofs

References

• Reid, D. A. & Knipping, C., Proof in Mathematics Education: Research, Learning, and Teaching, Sense Publishers (2010).

External links

• Berwin A. Turlach, Invalid techniques of proof.