A conjecture is a mathematical statement that has not yet been rigorously proven. When we have a finite number of cases for which a conjecture can hold, we can use proof by exhaustion. In this method, we check each case to see if the statement holds.
What is the proof by exhaustion method?
Proof by exhaustion is a direct method of proof. It can take a lot of time to complete, as there can be a lot of cases to check. It’s possible to split up the cases, for example, odd and even numbers.
Proof by exhaustion is different from other direct methods of proof, as we need not draw logical arguments. It is sufficient to show that ‘none of the cases disproves the conjecture; thus the conjecture is true’. The only time we use proof by exhaustion is when there are a finite number of cases.
How do you prove by exhaustion?
We can generalise the method of proof by exhaustion using two steps.
Step 1: Establish the cases that apply to the statement.
Step 2: Prove that the statement is true for each case.
Each case of the statement needs to be proved separately, one by one. We need to exhaust all of the cases to verify the statement.
If any identified cases can be disproven, the entire conjecture can be considered disproven. You can check out Disproof by Counterexample to dive deeper into this concept.
Let’s look at an example to understand how to apply the above steps.
Show that \(n^2-1\) is a multiple of 3 if n is not a multiple of 3.
Solution:
Step 1: If n isn’t a multiple of 3, it is either one or two more than a multiple of 3. Thus we can write \(n = 3k + 1\) or \(n = 3k + 2\), with k being any integer.
Step 2: Now prove that the statement is true for each case.
Case 1: Show that if \(n = 3k + 1\), then \(n^2-1\) is a multiple of 3.
\(\begin{align} n^2-1 &= (3k + 1)^2 -1 \\ &= (3k)^2 + 6k +1-1 \\&=9k^2 +6k \\ &=3(3k^2 + 2k) \end{align}\)
As \(3 (3k^2 + 2k)\) is 3 times \((3k² + 2k)\), we can conclude that \(3 (3k^2 + 2k)\) is a multiple of 3.
So, \(n^2 -1\) is a multiple of 3 for \(n = 3k + 1\).
Now, let’s check the second case.
Case 2: To check if \(n = 3k + 2\), then \(n^2 -1\) is a multiple of 3.
\(\begin{align} n^2-1 &= (3k+2)^2 -1 \\ &= (3k)^2 + 2(3k)(2) + 2^2-1 \\ &= 9k^2 +12k + 3 \\ &= 3(3k^2 + 4k + 1) \end{align}\)
The resulting expression \(3 (3k^2 + 4k + 1)\) is also a multiple of 3 for any value of k. So, \(n^2 -1\) is a multiple of 3 for \(n = 3k + 2\).
As both cases satisfy the statement, we have proved that the given statement is correct.
When you should use proof by exhaustion
Proof by exhaustion is only possible when we can reduce the conjecture to a finite number of cases. For example, we reduced the conjecture to two possible cases in the above example. Suppose we tried to solve by proof by exhaustion for all possible values of n instead. That would be a never-ending process since the domain of n is unbounded, i.e. n can take an infinite number of values.
If we can reduce the given conjecture to a small number of possible cases, each of which can be proven (or disproven), then it could be good to use proof by exhaustion. For a very large number of cases, proof by exhaustion is usually not going to be a very efficient approach.
Examples of proofs by exhaustion
Example 1: Show that \(p = n^2 + 2\) is not a multiple of 4, where n is an integer, \(2 \leq n \leq 7\).
Solution:
Step 1: Split the statement into a finite number of cases.
It is given that \(2 \leq n \leq 7\) and for each value of n, we need to check if \(p = n^2 +2\) is a multiple of 4 or not.
We will have six cases, as shown.
Case 1: n = 2
Case 2: n = 3
Case 3: n = 4
Case 4: n = 5
Case 5: n = 6
Case 6: n = 7
Step 2: Prove that the statement is true for each case.
Let us prove each case one by one.
Case 1: n = 2
Substitute n = 2 in \(p = n^2 +2\) and check if the value obtained is a multiple of 4 or not.
\(p = (2)^2 + 2 = 6\)
As 6 is not divisible by 4, we can conclude that p is not a multiple of 4.
Case 2: n = 3
Substitute n = 3 in \(p = n^2 +2\) and check if the value obtained is a multiple of 4 or not.
\(p = (3)^2 + 2 =11\)
As 11 is not divisible by 4, we can conclude that p is not a multiple of 4.
Case 3: n = 4
Substitute n = 4 in \(p = n^2 +2\) and check if the value obtained is a multiple of 4 or not.
\(p = (4)^2 + 2 = 18\)
As 18 is not divisible by 4, we can conclude that p is not a multiple of 4.
Case 4: n = 5
Substitute n = 5 in \(p = n^2 +2\) and check if the value obtained is a multiple of 4 or not.
\(p = (5)^2 + 2 = 27\)
As 27 is not divisible by 4, we can conclude that p is not a multiple of 4.
Case 5: n = 6
Substitute n = 6 in \(p = n^2+2\) and check if the value obtained is a multiple of 4 or not.
\(p = (6)^2 + 2 = 38\)
As 38 is not divisible by 4, we can conclude that p is not a multiple of 4.
Case 6: n = 7
Substitute n = 7 in \(p = n^2 +2\) and check if the value obtained is a multiple of 4 or not.
\(p = (7)^2 + 2 = 51\)
As 51 is not divisible by 4, we can conclude that p is not a multiple of 4.
As all the cases satisfy the statement. The statement, \(p = n + 2\) is not a multiple of 4 when n is an integer, and \(2 \leq n \leq 7\) is correct.
Example 2: If p is a prime number such that \(3 <p <25\), then prove by exhaustion that \((p - 1) (p + 1)\) is a multiple of 12.
Solution:
Step 1: Split the statement into a finite number of cases.
It is given that p is a prime number such that \(3 <p <25\), and for each p, we need to check if \((p - 1) (p + 1)\) is a multiple of 12 or not.
The prime numbers between 3 and 25 are 5, 7, 11, 13, 17, 19, 23.
We will have seven cases, as shown.
Case 1: p = 5
Case 2: p = 7
Case 3: p = 11
Case 4: p = 13
Case 5: p = 17
Case 6: p = 19
Case 7: p = 23
Step 2: Prove that the statement is true for each case.
Let us prove each case one by one.
Case 1: To check if \((p - 1) (p + 1)\) is a multiple of 12 when p = 5.
\(\begin{align} (p - 1) (p + 1) &= (5-1) (5 + 1) \\&= (4) (6) \\ &= 24 \\ &= 2(12) \end{align}\)
\((p-1) (p + 1)\) is a multiple of 12 when p = 5.
Case 2: To check if \((p - 1) (p + 1)\) is a multiple of 12 when p = 7.
\(\begin{align} (p - 1) (p + 1) &= (7-1) (7 + 1) \\ &= (6) (8) \\ &= 48 \\ &= 4 (12) \end{align}\)
\((p-1) (p + 1)\) is a multiple of 12 when p = 7.
Case 3: To check if \((p - 1) (p + 1)\) is a multiple of 12 when p = 11.
\( \begin{align} (p-1) (p + 1) &= (11-1) (11 + 1) \\ &=(10)(12) \\ &= 120 \\ & = 10 (12) \end{align}\)
\((p-1) (p + 1)\) is a multiple of 12 when p = 11.
Case 4: To check if (p - 1) (p + 1) is a multiple of 12 when p = 13.
\(\begin{align} (p - 1) (p + 1) &= (13-1) (13 + 1) \\ &= (12) (14) \\ &= 168 \\ &= 14 (12) \end{align}\)
\((p-1) (p + 1)\) is a multiple of 12 when p = 13.
Case 5: To check if (p - 1) (p + 1) is a multiple of 12 when p = 17.
\(\begin{align} (p - 1) (p + 1) &= (17-1) (17 + 1) \\ &= (16) (18) \\ &= 288 \\ &= 24 (12) \end{align}\)
\((p-1) (p + 1)\) is a multiple of 12 when p = 17.
Case 6: To check if \((p - 1) (p + 1)\) is a multiple of 12 when p = 19.
\( \begin{align} (p - 1) (p + 1) &= (19-1) (19 + 1) \\ &= (18) (20) \\&= 360 \\&= 30 (12) \end{align} \)
\((p-1) (p + 1)\) is a multiple of 12 when p = 19.
Case 7: To check if \((p - 1) (p + 1)\) is a multiple of 12 when p = 23.
\( \begin{align} (p - 1) (p + 1) &= (19-1) (19 + 1) \\ &= (18) (20) \\&= 360 \\&= 30 (12) \end{align} \)
\((p-1) (p + 1)\) is a multiple of 12 when p = 23.
So, all the cases satisfy the statement. Therefore, the statement, if p is a prime number such that \(3 <p <25\), then \((p - 1) (p + 1)\) is a multiple of 12, is correct.
Example 3: If n is a positive integer, then \(n^7-n\) is divisible by 7.
Solution:
Step 1: Split the statement into a finite number of cases.
It is given that n is an integer, and for each n, we need to check if \(n^7-n\) is divisible by 7 or not.
We will have seven cases, as shown.
Case 1: n multiple of 7. So, \(n = 7q\), where q is an integer.
Case 2: n one more than the multiple of 7. So, \(n = 7q + 1\), where q is an integer.
Case 3: n two more than the multiple of 7. So, \(n = 7q + 2\), where q is an integer.
Case 4: n three more than the multiple of 7. So, \(n = 7q + 3\), where q is an integer.
Case 5: n four more than the multiple of 7. So, \(n = 7q + 4\), where q is an integer.
Case 6: n five more than the multiple of 7. So, \(n = 7q + 5\), where q is an integer.
Case 7: n six more than the multiple of 7. So, \(n = 7q + 6\), where q is an integer.
Step 2: Prove that the statement is true for each case.
Let us first factorise the expression \(n^7 -n\) and prove each case one by one.
\(n^7-n = n(n^6-1) = n((n^3)^2-1) = n(n^3+1)(n^3-1)\)
Since \(x^2 -y^(x+y)(x-y)\):
\(n(n+1)(n^2-n+1)(n-1)(n^2+n+1)\)
Since \(x^3 + y^3 = (x+y)(x^2-xy+y^2)\) and \(x^3-y^3 = (x-y)(x^2+xy+y^2)\)
So, \(n^7-n = n(n-1)(n+1)(n^2-n+1)(n^2+n+1)\)
Now, let us check each case one by one.
Case 1: To check \(n^7-n\) is divisible by 7 for, \(n = 7q\), where q is an integer.
\(n^7-n\) has a factor \(n = 7q\).
So, the expression is divisible by 7.
Case 2: To check \(n^7-n\)is divisible by 7 for, \(n = 7q + 1\), where q is an integer.
\(n^7-n\) has a factor \(n-1 = 7q + 1-1 = 7q\).
So, the expression is divisible by 7.
Case 3: To check \(n^7-n\) is divisible by 7 for, \(n = 7q + 2\), where q is an integer.
\(n^7-n\) has a factor
\(\begin{align} n^2+n+1 &= (7q+2)^2 + 7q +2 +1 \\ &=49q^2 +28q + 4+ 7q+2+1 \\ &=49q^2 +35 q+ 7 \\ &=7(7q^2 + 5q +1) \end{align}\)
So, the expression is divisible by 7.
Case 4: To check \(n^7-n\) is divisible by 7 for, \(n = 7q + 3\), where q is an integer.
\(n^7-n\) has a factor
\(\begin{align} n^2-n + 1 &= (7q+3)^2 -(7q+3) +1 \\ &= 49q^2 + 42q + 9-7q-3 + 1 \\ &= 49q^2 + 35q + 7 \\ &= 7 (7q^2 + 5q + 1) \end{align}\)
So, the expression is divisible by 7.
Case 5: To check \(n^7-n\) is divisible by 7 for, \(n = 7q + 4\), where q is an integer.
\(n^7-n\) has a factor
\(\begin{align} n^2 + n + 1 &= (7q+5)^2 - (7q+5)+1 \\ &= 49q^2 + 56q +16 +7q+4 +1 \\ &= 49q^2 + 63q+21 \\ &=7(7q^2 +9q+3) \end{align}\)
So, the expression is divisible by 7.
Case 6: To check \(n^7-n\) is divisible by 7 for, \(n = 7q + 5\) where q is an integer.
\(n^7-n\) has a factor
\(\begin{align} n^2-n+1 &= (7q +5)^2 -(7q+5) +1 \\ &= 49q^2 + 70q+25 -7q-5 +1 \\ &= 49q² + 63q + 21 \\ &= 7(7q^2 + 9q+3) \end{align}\)
So, the expression is divisible by 7.
Case 7: To check \(n^7-n\) is divisible by 7 for \(n = 7q + 6\), where q is an integer.
\(n^7-n\) has a factor \(n + 1 = 7q + 6 + 1 = 7q + 7 = 7 (q + 1)\).
So, the expression is divisible by 7.
So, all the cases satisfy the statement. Therefore if n is a positive integer, then \(n^7-n\) is divisible by 7.
Proof by Exhaustion - Key takeaways
Proof by exhaustion is used when there are a finite number of cases.
We must first find the cases and then try each of the cases out to show it holds.
The proof is completed if all values hold true.
Explanations 
Exams 
Magazine 
