Proof by Exhaustion

In this section, we will learn about “Proof by Exhaustion”. After reading this article we will be able to prove any statement by exhaustion.

Introduction

As we have studied before, that “proving a mathematical statement is an art”. There are many techniques to prove the mathematical statement. In this section, we are going to discuss proof by exhaustion.

Proof by exhaustion is a technique through which we can show that, the given statement is true for every case.

Proof by Exhaustion is a lengthy process. Proof by exhaustion is quit different from proof by deduction. In proof by deduction, we generally construct the logic to prove the statement. After proving a statement by deduction, it is considered as true for all values. But in the technique of proof by exhaustion, firstly we have to draw the possible cases and then we have to check that, the given statement is true for each case or not.

As we discussed above that, in proof by exhaustion, we have to do many calculation, so this technique has much more work than other techniques. Some time during the procedure of proof by exhaustion, numbers breaks into different types, then we have to show that, the statement is true for each type of number.

Proof by exhaustion requires conclusion for every case. In many situations, proofs by exhaustion are not possible. For example, “show that every multiple of 3 is odd”. In this case, it is not possible to check each case at any stage, because there are huge numbers that are multiples of 3, but it can be shown false by counterexample. Everything has its pros and cons.

There is another example, “show that 2n=n^{2} for first even integer” here, first we split the statement in cases. As first positive integer is 2.

Now check the statment for n = 2. After putting the value of n we get, 2(2)=2^{2}. Since both sides are equal. Because 2(2) is 4 and 2^{2} is also 4. As in this situation, we make a case according to the given statement. Proof by exhaustion worked on cases.

Whenever we are helpless to prove by deduction, we take help from proof by exhaustion. But this type of technique is not very useful as there are many options, because it can take much time to try every option. But, when mathematicians have to prove a difficult theorem, they may sometimes break it down into a limited number of various cases and show them separately using another type of proof.

Definition

Proof by exhaustion is a technique to prove any statement true by developing the number of limited cases.

As we have discussed above, proof by exhaustion is a lengthy process but are helpful when other techniques don’t work.

Methodology

In other techniques, we develop the logic and use proper axioms to check that the statement is true or not. But sometimes it is very difficult to make logic to check statement whether it is true or not. At that moment we make the number of cases whether to check the statement is true or not.

In this technique of proof, we first make the suitable cases, then stat checking each case one by one.

For example, “if n is not the multiple of three then its square will also be not a multiple of three”, in this case proving by deduction is not possible.

Here first we construct the cases to prove the statement.

If n is not a multiple of three then n should be 1 or 2 greater than multiple of 3. As we know every two-consecutive numbers after the multiple of 3, are not devisible by 3.

Here are two cases,

The first, number is 1 which is more than the multiple of three,

The second number is 2 which is more than the multiple of three.

Case 1: For this case, one considers the value of n as,

n = 3k  +1

Since 3k+1 shows that it is one, more than the multiple of 3,

Now, by taking square root on both sides of the equation,

n^{2}=(3k+1)^{2}

Recalling the formula of square (a+b)^{2}=a^{2}+2ab+b^{2}, we get,

n^{2}=9k^{2}+6k+1

Since the resulting value is 9k^{2}+6k+1, which is not the multiple of three, this expression can be written as,

3k(3k + 2) + 1

Since the resulting number is also one more than multiple of three. Here our first case is proved.

Now, let us go towards the second case where, two is more than the multiple of three,

Let,

n = 3k + 2

It is clear that choosing number is no more than multiple of three, now taking square on both sides of the equation,

Recalling the formula of square (a+b)^{2}=a^{2}+2ab+b^{2}, we get,

n^{2}=9k^{2}+12k+4

The resulting number is 9k^{2}+12k+4. Which is not the multiple of three.

Now rearranging the resulting number as,

9k^{2}+12k+4=9k^{2}+12k+3+1

9k^{2}+12k+4=3(3k^{2}+4k+1)+1

Since this one is more than multiple of three. So, our second case is also true.

As we see we construct the two cases and check them separately. Both cases state that the statement is true.

The whole procedure is called proof by exhaustion.

We follow the following step to prove by exhaustion,

  1. Split the statement into several cases,
  2. Check the statement for each case.

Practical Examples:

Problem 1: Prove that n^{7}-n is divisible by 7 if n is a positive integer.

According to the statement, we have to prove that n^{7}-n is divisible of 7. Since there are many cases according to the statement. So this statement is difficult to prove by deduction technique.

n is an integer, so there should be 7 types of numbers. So, these problems are split into seven cases.

Case 1: n is the number, which is multiple of 7, then n can be written as n = 7q, where q is any positive integer.

Case 2: n is the number, which is one more than multiple of 7, then n can be written as n = 7q + 1, where q is any positive integer.

Case 3: n is the number, which is two more than multiple of 7, then n can be written as n = 7q + 2, where q is any positive integer.

Case 4: n is the number, which is three more than multiple of 7, then n can be written as n = 7q + 3, where q is any positive integer.

Case 5: n is the number, which is four more than multiple of 7, then n can be written as n = 7q + 4, where q is any positive integer.

Case 6: n is the number, which is five more than multiple of 7, then n can be written as n = 7q + 5, where q is any positive integer.

Case 7: n is the number, which is six more than multiple of 7, then n can be written as n = 7q + 6, where q is any positive integer.

After this n can be a number, which is multiple of 7.

Now we have to check each case separately.

Since in this expression, the power of n is 7, which is difficult to calculate. So, we factorize the expression to make calculation easy.

Consider,

n^{7}-n

Taking common n,

n(n^{6}-1)

Rewriting the expression in term of power,

n((n^{3})^{2}-1^{2})

Recall the formula (a^{2}-b^{2})=(a-b)(a+b)

n(n^{3}-1)(n^{3}+1)

Recall the formula of cube (a^{3}-b^{3})=(a-b)(a^{2}+ab+b^{2}), same is the positive sign,

n(n-1)(n^{2}+n+1)(n+1)(n^{2}-n+1)         (1)

Here is the factorized form of n^{7}-n.

Case 1:

In this case, n = 7q, in the expression (1) n is the factor. So, the expression can be written as,

7q(n-1)(n^{2}+n+1)(n+1)(n^{2}-n+1)

Since the above expression is divisible by 7.

Case 2:

In this case, n = 7q + 1, in expression (1), n – 1 is the factor. If we replace the value of n, in this factor we get,

n – 1 = 7q + 1 – 1⇒  n – 1 = 7q

Its mean in case two, the factor n – 1, becomes 7q. Expression (1) can be written as,

n(7q)(n^{2}+n+1)(n+1)(n^{2}-n+1)

The above expression is divisible by 7.

Case 3: 

In this case, n = 7q + 2 in expression (1), n^{2}+n+1 is the factor. If we replace the value of n, in this factor we get,

(7q + 2)^{2}+(7q + 2)+1

Recall the formula (a + b)^{2}=a^{2}+2ab+b^{2}

49q^{2} + 28q + 4 + 7q + 2 + 1

49q^{2} + 35q + 7

7(7q^{2} + 5q + 1)

Expression (1) becomes,

n(n-1)(7(7q^{2} + 5q + 1))(n+1)(n^{2}-n+1)

Since this is also divisible by 7. 

Case 4: 

In this case n = 7q + 3 in expression (1), n^{2}-n+1 is the factor. If we replace the value of n, in this factor we get,

(7q + 3)^{2}-(7q + 3)+1

Recall the formula (a + b)^{2}=a^{2}+2ab+b^{2},

49q^{2}+ 42q + 9- 7q- 3 + 1

49q^{2} + 35q + 7

7(7q^{2} + 5q + 1)

Expression (1) becomes,

n(n-1)(n^{2}+n+1)(n+1)(7(7q^{2} + 5q + 1))

Since this is also divisible by 7.

Case 5: 

In this case n = 7q + 4 in expression (1), n^{2}+n+1 is the factor. If we replace the value of n, in this factor we get,

(7q + 4)^{2}+(7q + 4)+1

Recall the formula (a + b)^{2}=a^{2}+2ab+b^{2},

49q^{2} + 56q + 16 + 7q + 4 + 1

49q^{2} + 63q + 21

7(7q^{2} + 9q + 3)

Expression (1) becomes,

n(n-1)(7(7q^{2} + 9q + 3))(n+1)(n^{2}-n+1)

Since this is also divisible by 7. 

Case 6: 

In this case n =7q + 5 in expression (1), n^{2}-n+1 is the factor. If we replace the value of n, in this factor we get,

(7q + 5)^{2}-(7q + 5)+1

Recall the formula (a + b)^{2}=a^{2}+2ab+b^{2},

49q^{2} + 70q + 25- 7q- 5 + 1

49q^{2} + 63q + 21

7(7q^{2} + 9q + 3)

Expression (1) becomes,

n(n-1)(n^{2}+n+1)(n+1)(7(7q^{2} + 9q + 3))

Since this is also divisible by 7.

Case 7:

In this case, n = 7q + 6, in expression (1), n + 1 is the factor. If we replace the value of n, in this factor we get,

n + 1 = 7q + 6+1⇒  n + 1 = 7q + 7

n + 1 = 7q + 1

It means in case two, the factor n + 1, becomes 7(q + 1). Expression (1) can be written as,

n(n-1)(n^{2}+n+1)(7(q+1))(n^{2}-n+1)

The above expression is divisible by 7.

Since every case satisfies the statement. From this proves we can say that proof by exhaustion is a very lengthy process.

Problem 2: Show that m^{2}-1 is multiple of 3 if m is not multiple of 3. 

This should be proved by the exhaustion technique. The statement is going towards the cases. If an integer is not the multiple of 3, then it should be one or two more than the multiple of 3.

Three cases will be listed as:

Case 1: If m is one more than multiple of 3, then m = 3k + 1, k is an integer.

Case 2: If m is two more than multiple of 3, then m = 3k + 2, k is an integer.

Now check each case one by one,

Case 1:

Let m = 3k + 1

m^{2}-1

(3k+1)^{2}-1

Recall the formula (a^{2}-b^{2})=(a-b)(a+b),

9k^{2}+6k+1-1

9k^{2}+6k

3(3k^{2}+3k)

Since the above expression is multiple of 3.

Case 2:

Let m = 3k + 2

m^{2}-1

(3k+2)^{2}-1

Recall the formula (a^{2}-b^{2})=(a-b)(a+b),

9k^{2}+12k+4-1

9k^{2}+12k+3

3(3k^{2}+4k+1)

Since the above expression is multiple of 3.

Every case satisfies the statement.

Summary

In this section, we read about the proof by exhaustion and see that it is a lengthy procedure, but it helps us to prove the statement by splitting it into cases.

Source:

AS Level Mathematics Textbook by Aaran Karia
Pure mathematics 1 by Sophie Goldie