Proof by Exhaustion (Maths): Definition, Examples & Methods

Q: What is an exhaustive proof?

An exhaustive proof is where we have exhausted all cases to disprove it, thus it must be true.

Jump to a key chapter

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\).