Select your language

Suggested languages for you:
Log In Start studying!
StudySmarter - The all-in-one study app.
4.8 • +11k Ratings
More than 3 Million Downloads
Free
|
|

All-in-one learning app

  • Flashcards
  • NotesNotes
  • ExplanationsExplanations
  • Study Planner
  • Textbook solutions
Start studying

Proof by Exhaustion

Proof by Exhaustion

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²-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 is a multiple of 3.

n²-1 = (3k + 1) ² -1

=

= 9k² + 6k

= 3 (3k² + 2k)

As 3 (3k² + 2k) is 3 times (3k² + 2k), we can conclude that 3 (3k2 + 2k) is a multiple of 3.

So, n² -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² -1 is a multiple of 3.

=

= 9k² + 12k + 3

= 3 (3k² + 4k + 1)

The resulting expression 3 (3k² + 4k + 1) is also a multiple of 3 for any value of k. So, n² -1 is a multiple of 3 for n = 3k + 2.

As both the 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 is not a multiple of 4, where n is an integer, 2≤n≤7.

Solution:

Step 1: Split the statement into a finite number of cases.

It is given that 2≤n≤7 and for each value of n, we need to check if p = n² +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 and check if the value obtained is a multiple of 4 or not.

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 and check if the value obtained is a multiple of 4 or not.

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 and check if the value obtained is a multiple of 4 or not.

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 and check if the value obtained is a multiple of 4 or not.

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 and check if the value obtained is a multiple of 4 or not.

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 and check if the value obtained is a multiple of 4 or not.

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≤n≤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.

(p - 1) (p + 1) = (5-1) (5 + 1)

= (4) (6)

= 24

= 2 (12)

(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.

(p - 1) (p + 1) = (7-1) (7 + 1)

= (6) (8)

= 48

= 4 (12)

(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.

(p-1) (p + 1) = (11-1) (11 + 1)

= (10) (12)

= 120

= 10 (12)

(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.

(p - 1) (p + 1) = (13-1) (13 + 1)

= (12) (14)

= 168

= 14 (12)

(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.

(p - 1) (p + 1) = (17-1) (17 + 1)

= (16) (18)

= 288

= 24 (12)

(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.

(p - 1) (p + 1) = (19-1) (19 + 1)

= (18) (20)

= 360

= 30 (12)

(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.

(p-1) (p + 1) = (23-1) (23 + 1)

= (22) (24)

= 528

= 44 (12)

(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 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 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 and prove each case one by one.

So,

Now, let us check each case one by one.

Case 1: To check is divisible by 7 for, n = 7q, where q is an integer.

has a factor n = 7q.

So, the expression is divisible by 7.

Case 2: To check is divisible by 7 for, n = 7q + 1, where q is an integer.

has a factor n-1 = 7q + 1-1 = 7q.

So, the expression is divisible by 7.

Case 3: To check is divisible by 7 for, n = 7q + 2, where q is an integer.

has a factor

= 49q² + 28q + 4 + 7q + 2 + 1

= 49q² + 35q + 7

= 7 (7q² + 5q + 1)

So, the expression is divisible by 7.

Case 4: To check is divisible by 7 for, n = 7q + 3, where q is an integer.

has a factor n²-n + 1 =

= 49q² + 42q + 9-7q-3 + 1

= 49q² + 35q + 7

= 7 (7q² + 5q + 1)

So, the expression is divisible by 7.

Case 5: To check is divisible by 7 for, n = 7q + 4, where q is an integer.

has a factor n² + n + 1 =

= 49q² + 56q + 16 + 7q + 4 + 1

= 49q² + 63q + 21

= 7 (7q² + 9q + 3)

So, the expression is divisible by 7.

Case 6: To check is divisible by 7 for, n = 7q + 5 where q is an integer.

has a factor

= 49q² + 70q + 25-7q-5 + 1

= 49q² + 63q + 21

=

So, the expression is divisible by 7.

Case 7: To check is divisible by 7 for n = 7q + 6, where q is an integer.

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

Frequently Asked Questions about Proof by Exhaustion

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

Yes

Final Proof by Exhaustion Quiz

Question

What is a conjecture?

Show answer

Answer

A conjecture is a mathematical statement that has not yet been rigorously proven.

Show question

Question

How is proof by exhaustion unique?

Show answer

Answer

We need not draw logical arguments. It's enough to show that ‘none of the cases disproves the conjecture, thus the conjecture is true’.

Show question

Question

How many cases will we need to evaluate to prove by exhaustion that a²+1 is not divisible by 3, where 6≤a≤10?

Show answer

Answer

5

Show question

Question

What are the cases we need to evaluate to prove by exhaustion that a²+1 is not divisible by 3, where 6≤a≤10?

Show answer

Answer

a=6

a=7

a=8

a=9

a=10

Show question

Question

To prove that the sum of two consecutive square numbers between 40 and 100 is an odd number, how many cases will we need to evaluate?

Show answer

Answer

2

Show question

Question

To prove that the sum of two consecutive square numbers between 40 and 100 is an odd number, what are the cases we need to evaluate?

Show answer

Answer

1) sum of 49 and 64

2) sum of 64 and 81

Show question

Question

What is an exhaustive proof?

Show answer

Answer

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

Show question

Question

Is proof by exhaustion a direct proof?

Show answer

Answer

Yes

Show question

More about Proof by Exhaustion
60%

of the users don't pass the Proof by Exhaustion quiz! Will you pass the quiz?

Start Quiz

Discover the right content for your subjects

No need to cheat if you have everything you need to succeed! Packed into one app!

Study Plan

Be perfectly prepared on time with an individual plan.

Quizzes

Test your knowledge with gamified quizzes.

Flashcards

Create and find flashcards in record time.

Notes

Create beautiful notes faster than ever before.

Study Sets

Have all your study materials in one place.

Documents

Upload unlimited documents and save them online.

Study Analytics

Identify your study strength and weaknesses.

Weekly Goals

Set individual study goals and earn points reaching them.

Smart Reminders

Stop procrastinating with our study reminders.

Rewards

Earn points, unlock badges and level up while studying.

Magic Marker

Create flashcards in notes completely automatically.

Smart Formatting

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.