Chapter 11 ▶ Proof by exhaustion
Note: You should be familiar with the flowchart of proof in Chapter 10 before reading this chapter.
Welcome to our first method of proving conjectures! The method is called Proof by Exhaustion.
This doesn’t mean you do it until you are exhausted. Rather, you do it until all possibilities are exhausted. It is closely related to the method presented in Chapter 14 called Proof by Cases.
Part of the skill of mathematical proof is identifying the most appropriate method for any specific conjecture. Considering this, let’s look at some conjectures for which proof by exhaustion is appropriate, and some for which it is not.
| Conjecture | If true, how to prove by exhaustion? | Practical? |
|---|---|---|
| No Chinese citizen has green eyes | Check eye colour of every Chinese citizen | No, as there’s too many |
| All Irish citizens have a vowel in their surname | Check a database of Irish citizens | Possibly |
| There is no integer \(a\) such that \(a^2 + a^3 = 100\) | Check possible integers | Yes, as there are only so many integers which could work here. |
| The sum of the digits of a multiple of \(9\) is itself a multiple of \(9\) | Check all multiples of \(9\) | No, as there’s infinite number of them |
| For any right-angle triangle with hypotenuse \(a\) and legs \(b\) and \(c\), \(a^2 = b^2 + c^2\) | Check every possible right-angle triangle | No, as there’s infinite number of them |
Using this method when there are too many cases, as in (1) and (4), will take far too long, unless you’ve got a quick or systematic way to carry out the check, as in (2). This method works best for conjectures where the number of possibilities is low, as in (3).36
11.1 Steps
- Identify and list all possibilities.
- Prove that your list definitely contains all possibilities (i.e. you haven’t forgotten any).
- Show that the conjecture is true for each of the possibilities on your list.
11.2 Formal definition
To prove “If \(P\) then \(Q\)” by exhaustion, show that
If \(P_1\) then \(Q\).
If \(P_2\) then \(Q\).
\(\vdots\)
If \(P_n\) then \(Q\).
where \(P_1\), \(P_2\), …, \(P_n\) are all possible (finitely many) values of \(P\).
11.3 Conjectures
Exercise 11.1 Use the following examples to practise.
In our next class, you’ll be given a new set of conjectures to prove using this method.
Follow the flowchart in Chapter 10 (for example, if the conjecture is not in the form If … then …, make sure you rewrite it before starting the proof).
Solutions are included underneath the exercise. Attempt the proof before checking the solutions.
Conjecture 11.1 : If \(2 \leq a \leq 7\) and \(a \in{\mathbb Z}^+\), then \(4 \nmid a^2 + 2\).
Conjecture 11.2 : There is a prime number between \(8\) and \(12\).
Conjecture 11.3 : No square number ends in \(8\).
Conjecture 11.4 : \(97\) is a prime number.
Solutions:
Conjecture 11.1: See https://www.youtube.com/watch?v=ifMZt4l5JIM. Alternatively https://www.youtube.com/watch?v=YmbTI91TUp4.
Conjecture 11.2: See https://www.youtube.com/watch?v=eQM778zoB14.
Conjecture 11.3: Watch 0:00-4:20 of https://www.youtube.com/watch?v=k0f7w4xTp1I.
Conjecture 11.4: See https://www.youtube.com/watch?v=1amtOenZEwU.
Exercise 11.2 Some of these conjectures below are false; disprove them by finding a counterexample. Some of them are true; prove them by exhaustion. Follow the flowchart in Chapter 10 to help you.
Conjecture 11.5 : There is no two-digit number which is both a perfect square and a perfect cube.
Conjecture 11.6 : If \(p\) is a prime number and \(p > 5\), then \(p^4\) ends in 1. (Hint here: https://www.youtube.com/watch?v=Q_UdUwm3Biw.)
Conjecture 11.7 : There is no three-digit number which is a perfect square.
Conjecture 11.8 : There is no perfect square between 4100 and 4200.
Conjecture 11.9 : \((a + 1)^3\geq 3^a\) for \(a\in{\mathbb Z^+}\), \(a\leq 4\).
Conjecture 11.10 : The product of two non-integers is never an integer.
Conjecture 11.11 : No integer greater than 2, when written in English with the Latin alphabet, has more letters than the number itself. (Think carefully about which numbers need to be included on your list of possibilities here.)
Conjecture 11.12 : No integer greater than 2, when written in Russian using the Cyrillic alphabet, has more letters than the number itself. (Again, think carefully about which numbers need to be included on your list of possibilities here.)
Conjecture 11.13 : If \(p\) is a prime number such that \(3 \leq p \leq 23\), then \(8 \mid (p+1)(p-1)\).
Conjecture 11.14 : Every positive integer up to and including 28 is at least one of the following: prime, perfect, triangular, or can be written as \(b^c\), where \(b\in{\mathbb Z}\) and \(c\in{\mathbb Z^+}\), \(c > 1\).
Conjecture 11.15 : Every integer between 20 and 30 (inclusive) can be written as the sum of exactly five non-zero square numbers.
Conjecture 11.16 : If \(x\) is a positive integer less than 5, the last digit of \(x^5\) is \(x\).
Conjecture 11.17 : There are fewer square numbers below 50 than prime numbers.
Conjecture 11.18 : Every even integer between (and including) 4 and 30 can be written as a sum of two primes.
Conjecture 11.19 : Every odd integer between 4 and 30 can be written as a sum of two primes.
Conjecture 11.20 : Every composite integer between (and including) 4 and 30 can be written as a sum of two primes.
Conjecture 11.21 : The sum of two distinct square numbers is a square number. (Distinct means the two square numbers can’t be the same.)
Conjecture 11.22 : For \(x, y, a \in \mathbb R\), if \(x > y\) then \(ax > ay\).
Conjecture 11.23 : It’s impossible to move a knight from one corner of a chess board to the corner diagonally opposite in 4 moves. (You don’t play chess? Look up online how a knight moves.)
Conjecture 11.24 : Each integer in the set 2, 4, 6, 8, …, 24, 26 can be written the sum of at most three perfect squares.
Conjecture 11.25 : There are no integers \(a\), \(b\) and \(c\) such that \((1+\frac{1}{a})(1+\frac{1}{b})(1+\frac{1}{c}) = 2\).
Conjecture 11.26 : If the sum of two integers is even, then at least one of the summands is even. (Don’t know what a summand is? Have a search online…)
Conjecture 11.27 : The sum of two consecutive perfect squares between 100 and 200 is an odd number.
Conjecture 11.28 : The sum of any two distinct perfect squares between 100 and 200 is an odd number.
Unless we could prove that there exist only a limited (and small) number of “families” of right-angled triangles. We’ll return to this example later, but for now it seems unlikely to be suitable for a proof by exhaustion.↩︎