In this explainer, we will learn how to prove mathematical statements by deductive reasoning or by exhaustion or disprove them using a counterexample.
The ability to argue logically and construct a rigorous proof is a very powerful skill in mathematics.
Definition: Mathematical Proof
A mathematical proof is a logical and systematic argument that shows a statement to be true (or false).
A claim that has not yet been proven is called a conjecture. Sometimes, we are presented with a conjecture and must use a logical argument to establish whether it is true or false.
A result that has been established by means of a mathematical proof is often referred to as a theorem. It is a factual statement that describes the general behavior of a mathematical system under a given set of conditions, meaning that we do not have to check individual examples on a case-by-case basis. For instance, the Pythagorean theorem states that in any right triangle, the square of the hypotenuse is equal to the sum of the squares of the two shorter sides. Therefore, whenever we meet a right triangle, we can always assume that this relationship holds between its side lengths without having to check that it is true.
If required, we can quote relevant theorems in building up our own proofs because these results are necessarily true and hence can be used to provide logical justification for other claims.
Mathematical proof is the only way to establish certainty in mathematics. Even if we find thousands of examples that seem to point toward a particular rule, this always leaves open the possibility of discovering a new example that contradicts it. However, the existence of numerous examples fitting particular patterns has often been the inspiration for mathematicians to formulate conjectures, and many of these conjectures have later been proved to give theorems.
In this explainer, we will cover two main types of mathematical proof: proof by deduction and proof by exhaustion.
Definition: Proof by Deduction
Proof by deduction (or deductive proof) starts from a known fact or definition and then proceeds in a series of logically justified steps until it reaches a final conclusion.
Proof by deduction is the most common type of proof. Since this method can be applied in a variety of contexts, we will illustrate the process through three different examples.
Proof by Deduction 1
Prove that the following statement is true: The product of any two even numbers is always divisible 4.
To prove that a worded statement is true, we must first rewrite it using some mathematical notation. Note that any two even numbers can be written in the form and , where and are integers. This is a useful convention to remember when representing even numbers; similarly, we could write and to represent two odd numbers.
The product of these numbers is therefore
Clearly, the number has 4 as a factor, which means it is divisible by 4. We conclude that the original statement is true.
Note that we will never be asked to prove that a statement is true if it is actually false! In general, it is important to read the question carefully to make sure we understand any initial assumptions and proceed in the correct way.
We can also construct deductive proofs for statements expressed as inequalities. In cases like this, we start with one side of the inequality (usually the left-hand side) and work through a series of deductive steps until we arrive at the other side, making sure that the inequality symbol is the correct way round.
Proof by Deduction 2
Prove that for all values of .
Here, we are asked to prove that a quadratic inequality holds. As the left-hand side is a quadratic expression, a sensible step to try is completing the square. This follows because completing the square is the customary technique for determining the vertex of the parabola represented by a quadratic expression. Consequently, it would not be surprising if this vertex was relevant when seeking an upper or lower bound for the corresponding quadratic expression.
Completing the square and simplifying, we get
As a squared number is always nonnegative, we have , so
Our chain of inequalities proves that for all values of .
A third type of proof by deduction relates to proving mathematical identities, which are statements such as . The symbol stands for βis identically equal to,β meaning that the identities are true for all permissible values of the variables involved. This is in contrast to equations, which are true only for certain values of the featured variables. For example, the equation is true only when , whereas the identity is true for all values of .
We prove identities by starting with the expression on one side (usually the left-hand side) and manipulating it algebraically until we arrive at the expression on the other side. Let us look at an example of this type.
Proof by Deduction 3
Prove that .
Starting with the left-hand side, observe that it has three terms, while the right-hand side has only one. In situations like these, a sensible strategy is to rewrite the terms on the left-hand side over a common denominator and then simplify the result. This gives
Therefore, we have shown that the left-hand side is equivalent to the right-hand side, which proves the identity.
Next, we investigate proof by exhaustion.
Definition: Proof by Exhaustion
Proof by exhaustion means breaking a statement down into a series of individual cases and proving each one separately.
It is only feasible to use proof by exhaustion if there is a limited number of cases to check. For instance, suppose we are asked to prove the statement βThere are no prime numbers between 32 and 36 (inclusive).β Such a proof would involve checking just five numbers, which is straightforward to do.
A proof by exhaustion would go along the following lines.
Since all even numbers are divisible by 2, we can immediately rule out 32, 34, and 36, because they have a divisor other than 1 and themselves. Hence, they cannot be prime.
We are left to dispose of the cases 33 and 35. As and , then both of these numbers have factors other than 1 and themselves, so they cannot be prime either.
We conclude that there are no prime numbers between 32 and 36 (inclusive).
Note, however, that when working by hand, this would not be a viable method of proof for problems that split into hundreds or thousands of cases. It is always worth considering the practicality of using proof by exhaustion to solve a given problem.
Now that we have introduced the two main types of proof to be covered in this explainer, let us try an example that tests our understanding of proof construction.
Example 1: Proving an Inequality Holds True by Completing the Square
Adel wants to prove the statement that is positive for any real value of . He does the following calculation:
.
Since for all real values of , the statement is true.
Identify a potential problem with Adelβs calculation.
- The statement is only true for positive values of .
- The step of completing the square is not correct.
- The inequality symbol is written the wrong way around.
- He has not covered all the possible cases.
- He starts with the conclusion that he is trying to prove.
Answer
Recall that a deductive proof starts from a known fact or definition and then proceeds in a series of logically justified steps until it reaches a final conclusion. To prove a statement expressed as an inequality, we start with one side of the inequality (usually the left-hand side) and work through the deductive steps until we arrive at the other side, making sure that the inequality symbol is the correct way round.
In this case, Adel wants to prove that for any real value of . Therefore, according to the usual pattern of a deductive proof for an inequality, he should start with the expression and manipulate it until he has shown that its value is greater than zero. However, notice that in his first line of working, he has just restated the inequality he wants to prove. This is a mistake in the logic of constructing a proof. Even if all the steps that follow on from the first line are logically justified, the proof has started from an incorrect assumption and so cannot be a valid argument.
Using some of the ideas from Adelβs attempted proof, we can construct a correct version as follows.
Starting with the quadratic expression and completing the square, we get
The last expression is the sum of a squared term (which must have a nonnegative value) and a positive integer, so
Our chain of inequalities shows that , so we have proved that is positive for any real value of .
Returning to the answer options, we see that a potential problem with Adelβs working is E: he starts with the conclusion that he is trying to prove.
Next, we consider an example from a geometric context. It is important to realize that even mathematical scenarios with obvious visual representations must be proved using rigorous logical arguments.
Example 2: Proving That Three Given Points Are the Vertices of a Shape
Nader wants to prove mathematically that , , and are the vertices of a right triangle. He draws an accurate diagram of the triangle and measures the angle between the two shorter sides as . Is his method correct? If not, why?
- Yes, his method is correct.
- No, he should have given a deductive proof.
- No, he should have given a proof by exhaustion by measuring all three angles.
- No, he should have asked someone else to check his measurements.
Answer
Recall that a deductive proof starts from a known fact or definition and then proceeds in a series of logically justified steps until it reaches a final conclusion. Proof by exhaustion means breaking a statement down into a series of individual cases and proving each one separately.
Here, Nader is faced with a geometric problem. However, even though he has given a visual demonstration that points , , and are the vertices of a right triangle, this is not sufficient to prove mathematically that they are. Therefore, his method is incorrect, so we can rule out answer option A. We can also rule out D, because even if Nader asked someone else to check his measurements, this would still not constitute a mathematical proof.
We are left to consider options B and C. Referring back to the definition of proof by exhaustion, it is clear that C involves a misunderstanding about what this term means. Hence, we can rule out this option too, so the correct answer is B: Naderβs method is incorrect and he should have given a deductive proof.
In order to construct such a proof, it helps to draw a sketch of the situation.
One possible means of providing a deductive proof is to apply the converse of the Pythagorean theorem. Write for the length of the longest side of the triangle (the side opposite vertex ) and and for the lengths of the two shorter sides (the sides opposite vertices and respectively). The converse of the Pythagorean theorem states that if , the triangle is a right triangle. On the other hand, if , the triangle is not a right triangle.
Now, recall that for two points and , the distance between them is given by the formula
Therefore, the distance between and is
Similarly, the distance between and is and the distance between and is
For , we have and . Therefore, , so by the converse of the Pythagorean theorem, points , , and are the vertices of a right triangle.
In our next example, we must work out which method of proof to apply to a given problem.
Example 3: Understanding Different Methods of Proof
Fares wants to prove that there are no positive integers , , or all less than 5 such that . Is this possible? If so, what kind of proof should he use?
- Yes, it is possible by using deductive proof.
- Yes, it is possible by using proof by exhaustion.
- No, it is not possible.
Answer
Referring to the answer options, recall that a deductive proof starts from a known fact or definition and then proceeds in a series of logically justified steps until it reaches a final conclusion. Proof by exhaustion means breaking a statement down into a series of individual cases and proving each one separately; it is only feasible to use this method if there is a limited number of cases to check.
In this question, Fares wants to prove that there are no positive integers , , or all less than 5 such that . There are in fact only a few cases to check for the following reasons.
The values of , , and can be at most 4. As Fares must check if , he can assume that the value of is greater than that of or , as otherwise it would be impossible for the equation to be satisfied. This immediately excludes any cases with or . Furthermore, for any case where and have different values (say and ), Fares does not need to check the reverse case ( and ), as this would yield the same result for the sum . This means that a full proof by exhaustion reduces to checking only the 10 cases shown in the table below.
| 1 | 1 | 2 | 2 | 8 |
| 1 | 1 | 3 | 2 | 27 |
| 1 | 1 | 4 | 2 | 64 |
| 1 | 2 | 3 | 9 | 27 |
| 1 | 2 | 4 | 9 | 64 |
| 1 | 3 | 4 | 28 | 64 |
| 2 | 2 | 3 | 16 | 27 |
| 2 | 2 | 4 | 16 | 64 |
| 2 | 3 | 4 | 35 | 64 |
| 3 | 3 | 4 | 54 | 64 |
Since none of these cases satisfy , this proves by exhaustion that there are no positive integers , , or all less than 5 such that .
Therefore, the correct answer to whether it is possible for Fares to prove this result is B: yes, it is possible by using proof by exhaustion.
Now, we try another example that features proof by exhaustion.
Example 4: Proving a Statement about Cubes by Exhaustion
Samar wants to prove that all the cube numbers between 1 and 100 (inclusive) can be written in the form , , or , where is an integer.
- If she wants to prove this by exhaustion by checking each number directly, how many numbers will she need to check?
- 100 numbers
- 1 number
- 3 numbers
- 4 numbers
- 0 numbers
- Samar now wants to prove the statement for all possible cube numbers by considering for
different cases of . Is this possible? If so, which cases of would she need
to check?
- Yes, it is possible by checking , , and .
- Yes, it is possible by checking , , and .
- Yes, it is possible by considering every integer value of .
- Yes, it is possible by checking and .
- No, it is not possible.
Answer
Recall that proof by exhaustion means breaking a statement down into a series of individual cases and proving each one separately.
Part 1
Samar wants to prove by exhaustion that all the cube numbers between 1 and 100 (inclusive) can be written in one of the three stated forms. To do a direct check, she must first find all the cube numbers in this range. Then, she can write them as follows:
Note that Samar does not need to go any further because , which is greater than 100. Hence, as there are 4 cube numbers between 1 and 100 (inclusive), the correct answer is D.
Part 2
Next, Samar wishes to prove that all possible cube numbers can be written in one of the three stated forms by considering for different cases of . Therefore, she is seeking another proof by exhaustion.
Recall that it is only feasible to use this method if there is a limited number of cases to check. This means that we can immediately discount option C, since checking the result for all integer values of would clearly take forever! Of the remaining options, we can also rule out B; this follows because the majority of integers cannot be written in the form , , or , so this check would not cover all possible cases.
We are left to consider options A and D. Note that D corresponds to checking the results for odd and even integers respectively. However, for odd integers , we get
Similarly, for even integers , we get
In other words, splitting the integers into the two separate cases of odd and even does not provide Samar with enough information about whether can be written in one of the three stated forms. Thus, we can also rule out option D.
Finally, we look at A. For this case, if , then
Similarly, if , then
Furthermore, if , then
In other words, splitting the integers into these three separate cases does provide Samar with the information she requires about whether can be written in one of the three stated forms. She can therefore prove the statement for all possible cube numbers by using this proof by exhaustion. We conclude that the correct answer is A.
As we have discovered, to prove that a general statement is true, it is necessary to construct a systematic argument. However, to disprove a general statement, it is sufficient to give a single example that contradicts the statement; we refer to this as a counterexample.
Definition: Disproof by Counterexample
Disproof by counterexample is a method of showing that a general statement is false by finding a single example that contradicts it.
For a given general statement, there may be many possible counterexamples, but the existence of just one is sufficient to disprove the statement.
For instance, suppose we wish to disprove the statement that for all nonzero numbers . One suitable counterexample is , because and so we have for this case. In fact, there is an infinite number of possible counterexamples to this statement, since any number satisfies . Nevertheless, to disprove the statement, it is sufficient to give just one.
Our final question gives us further practice in identifying counterexamples.
Example 5: Identifying a Sufficient Counterexample to Prove That a Statement Does Not Hold
Select the counterexample to each of the given statements.
- All integers have an even number of distinct factors.
- 3
- 6
- 9
- 12
- 15
- The expression is positive for all values of .
- 0
- 4
- 2
Answer
Recall that to disprove a general statement, it is sufficient to give a single example, called a counterexample, that contradicts the statement.
Part 1
To find the correct counterexample to the statement βAll integers have an even number of distinct factors,β we first need to list the different factors for all the given options. Thus, we have
All of these numbers have an even number of factors except (the square number) 9, which has three. Therefore, the correct answer is C.
Part 2
To find the correct counterexample to the statement βThe expression is positive for all values of ,β we must substitute for using the five given options as follows:
When , we have .
When , we have .
When , we have .
When , we have .
When , we have .
We get a positive result in all cases except , so the correct answer is D.
Let us finish by recapping some key concepts from this explainer.
Key Points
- A mathematical proof is a logical and systematic argument that shows a statement to be true (or false).
- Proof by deduction (or deductive proof) starts from a known fact or definition and then proceeds in a series of logically justified steps until it reaches a final conclusion.
- Proof by exhaustion means breaking a statement down into a series of individual cases and proving each one separately. It is only feasible to use this method if there is a limited number of cases to check.
- To prove that a general statement is true, it is necessary to construct a systematic argument. However, to disprove a general statement, it is sufficient to give a single example, called a counterexample, that contradicts the statement.
