Video Transcript
In this video, we will learn how to
prove mathematical statements by deductive reasoning or by exhaustion or disprove
them using a counterexample.
One of the main concepts we want to
consider in this video is what constitutes a mathematical proof. In concrete terms, a mathematical
proof is a logical and systematic argument that shows a statement to be true or
false. Having said that, it may be unclear
exactly what logical and systematic means.
Let us consider an example
statement. If 𝑚 and 𝑛 are even numbers, then
𝑚 plus 𝑛 is even. To show that this is true, it may
be tempting to just select random even numbers for 𝑚 and 𝑛, to compute their sums,
and then to conclude that since they are all even, the statement probably holds. However, the reality is that we
would need to check every pair of even numbers possible in order to conclusively
prove this statement is true. Since there are infinitely many
even numbers to choose from, there is no way we can do this.
To mathematically prove something,
we have to prove it for all cases using a logical argument. How would we do this? Well, let us first start by
considering the assumption. If possible, it is helpful to be
able to write any assumptions in mathematical terms so that we can use algebraic
arguments to get to what we are trying to prove.
One helpful property we can use is
that if 𝑚 and 𝑛 are even, then they are each divisible by two. So we can write them as 𝑚 equals
two 𝑘 and 𝑛 equals two 𝑗, where 𝑘 and 𝑗 are integers. Then if we add 𝑚 and 𝑛, we are
adding two 𝑗 and two 𝑘, which we can factor two out of. Thus, we can see that we have a
product of two and an integer, which must be an even number. Therefore, 𝑚 plus 𝑛 must be
even.
Now let us analyze what we have
done. We started from a known property of
even numbers based on our assumption. We then applied a sequence of
logical steps based on algebraic properties. And finally, we arrived at the
conclusion. As it turns out, this is actually
an example of a proof by deduction, also known as a direct proof. A proof by deduction starts from a
known fact or definition and then follows a series of logical steps to a
conclusion. As a diagram, we can write the
process like this. Now let us consider an example of
analyzing a proof by deduction.
Liam wants to prove the statement
that 𝑥 squared plus two 𝑥 plus three is positive for any real value of 𝑥. He does the following
calculation. 𝑥 squared plus two 𝑥 plus three
is greater than zero. 𝑥 plus one squared minus one plus
three is greater than zero. 𝑥 plus one squared plus two is
greater than zero. Since 𝑥 plus one squared is
greater than or equal to zero for all real values of 𝑥, the statement is true. Identify a potential problem with
Liam’s calculation.
For now, let us focus on the
argument presented to us. Recall that a proof by deduction
requires us to start from a known fact or definition, proceed through a series of
logical steps, and reach a conclusion. If we consider each step of the
proof, we can see that they are logically sound. We complete the square, subtract
one from three, and state that 𝑥 plus one squared is nonnegative.
However, a proof needs to start
from something we already know and arrive at what we are trying to prove. The issue with this argument is
that the very first line is not a known fact, but rather it is the statement we are
trying to prove, which means that the proof is not valid.
If we were to write an actual proof
of this, we would need to start from the known fact that 𝑥 plus one squared is
greater than or equal to zero, since the square of any number is greater than or
equal to zero. Then we could proceed with the
steps in effectively the reverse order. First, we add two to the left-hand
side to make it strictly greater than zero. Then we expand the parentheses to
get 𝑥 squared plus two 𝑥 plus one plus two is greater than zero. And finally, by combining the
constant terms, we finish with the line that we are trying to prove.
If we consider the five possible
options for this question, we can see that the correct option is (E). That is, the problem with Liam’s
calculation is that he starts with the conclusion that he is trying to prove.
Let us consider another method of
proof: proof by exhaustion. In a proof by exhaustion, we break
a statement down into a series of individual cases and prove each one
separately. We call this method a proof by
exhaustion since we are exhausting all the possibilities until everything is
proved.
For example, suppose we wanted to
show that 𝑥 to the four minus six 𝑥 cubed plus seven was negative for integer
values of 𝑥 between two and five. There are numerous ways we could
show this, but with a proof by exhaustion, we just have to consider the value of the
function for each 𝑥 in the given interval. We can do this by making a table,
calculating the left-hand side of the inequality for each value. And we can conclude that since they
are all negative, the inequality is indeed true for these values.
An important aspect of this method
is that it only works when we can divide a statement into a finite number of cases
that we can check. If 𝑥 was not restricted to a small
number of values, this would not be feasible.
Let us now consider an example
where we need to determine the kind of proof that can be used to prove a
statement.
Anthony wants to prove that there
are no positive integers 𝑎, 𝑏, or 𝑐 all less than five such that 𝑎 cubed plus 𝑏
cubed equals 𝑐 cubed. Is this possible? If so, what kind of proof should he
use? Is the answer (A) no, it is not
possible? (B) Yes, it is possible using
deductive proof. Or (C) yes, it is possible using
proof by exhaustion.
The key to this example is
understanding what kind of proof is suitable for the given statement. We can recall that a deductive
proof is one that starts from a known fact and follows a series of logical steps to
a conclusion. On the other hand, a proof by
exhaustion breaks a statement down into cases and proves each one separately. Strictly speaking, it is possible
to prove that there are no positive integers such that 𝑎 cubed plus 𝑏 cubed equals
𝑐 cubed. However, doing this using a simple
deductive proof is almost certainly not possible. Or at least, we would not be able
to fit it all on the screen. And in any case, it is not
necessary for proving the given statement.
Instead, we should be aware that we
only have to prove the statement for a limited number of cases, rather than all
positive integers. Therefore, we should consider a
proof by exhaustion, where we consider each combination of 𝑎, 𝑏, and 𝑐 that is
four or less.
Let us list these values in a
table. To make things easier, we only have
to include cases where 𝑎 and 𝑏 are less than 𝑐, since otherwise the left-hand
side would end up being bigger. This excludes 𝑎 or 𝑏 from being
four. And we can also ignore any cases
that are just 𝑎 and 𝑏 swapped around. Overall, this gives us 10
cases. Then we can work out the left- and
right-hand sides of the equation. And we can see that in no case is
𝑎 cubed plus 𝑏 cubed equal to 𝑐 cubed. Thus, we have proved by exhaustion
that there are no positive integers 𝑎, 𝑏, and 𝑐 all less than five such that 𝑎
cubed plus 𝑏 cubed equals 𝑐 cubed. This corresponds to option (C).
Let us now consider another example
of proof by exhaustion.
Olivia wants to prove that all the
cube numbers between one and 100 inclusive can be written in the form nine 𝑘 minus
one, nine 𝑘 or nine 𝑘 plus one, 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? For the second part, Olivia now
wants to prove the statement for all possible cube numbers by considering 𝑛 cubed
for different cases of 𝑛. Is this possible? If so, which cases of 𝑛 would she
need to check?
Let us start off by just
considering the first part. Recall that proving a statement by
exhaustion means breaking the statement down into cases and proving each one
separately. If we consider the statement that
we are trying to prove, we can see that we are interested in the cube numbers
between one and 100 inclusive. In particular, if we can show that
all of the numbers in this interval can be written in one of the three given forms,
then we can prove the statement by exhaustion.
Now we know that the cube numbers
can be obtained by cubing the positive integers one, two, three, and so on, which
are one, eight, 27, 64, 125, and so on. And we can see that the ones
between one and 100 are the first four of these cubes. While not required to answer the
question, it is indeed possible to show that each of these numbers can be written in
one of the given forms. For example, one is equal to nine
𝑘 plus one, where 𝑘 is zero. Eight is equal to nine times one
minus one. And similarly, the other two cubes
can also be written in these forms. In any case, the answer is that
Olivia will need to check four numbers to prove the statement by exhaustion.
Now we need to consider how to
prove the statement for all 𝑛 by considering different cases of 𝑛. It may help us to consider the
potential options here. We have (A) no, is not
possible. (B) Yes, it is possible by checking
𝑛 equals two 𝑘 minus one and 𝑛 equals two 𝑘. (C) Yes, it is possible by checking
𝑛 equals nine 𝑘 minus one, nine 𝑘, and nine 𝑘 plus one. (D) Yes, it is possible by
considering every integer value of 𝑛. Or (E) yes, it is possible by
checking 𝑛 equals three 𝑘 minus one, three 𝑘, and three 𝑘 plus one.
Leaving aside the possibility for
now that there is no way to solve this by considering cases of 𝑛, let us consider
the other options. We can also discount option (D),
since we will need to divide up the integers into cases in some way. Otherwise, we will not obtain three
different forms. If we consider the remaining cases,
we can see that, unlike in the first part, we are not considering individual values
for 𝑛, but rather different partitions of the integers.
For example, for option (B), by
considering 𝑛 equals two 𝑘 minus one or two 𝑘, we can see that we are implicitly
considering odd or even numbers. Similarly, in option (E), we are
considering multiples of three and numbers that are one less than or one greater
than a multiple of three, which together comprises all the integers. However, in option (C), we can see
that this division of the integers will not cover all possible cases, so it will not
work.
For the two remaining options, let
us do as the question suggests and try considering 𝑛 cubed for the different cases
to see whether we can get the different forms. For instance, if 𝑛 equals two 𝑘,
then 𝑛 cubed is two 𝑘 all cubed, which is eight 𝑘 cubed. But we need nine rather than eight
here, so this is probably not useful. If, on the other hand, we consider
𝑛 equals three 𝑘, then 𝑛 cubed is three 𝑘 all cubed, which is 27𝑘 cubed.
Now since three 𝑘 cubed is an
integer, we could let three 𝑘 cubed be 𝑗, say, where 𝑗 is an integer. So we can write this as nine
𝑗. And we can see that this is the
same form as nine 𝑘 just using a different letter, since 𝑘 and 𝑗 are both
integers. So we have obtained one of the
desired forms.
Let us now consider the case where
𝑛 equals three 𝑘 minus one. Then 𝑛 cubed is three 𝑘 minus one
all cubed, which we can expand to get 27𝑘 cubed minus 27𝑘 squared plus nine 𝑘
minus one. And we can factor nine 𝑘 out of
the first three terms. Now using a similar approach to the
first case, we note that 𝑘 times the expression inside the parentheses is an
integer, which we can denote by 𝑗. So this is just nine 𝑗 minus one
for some integer 𝑗, which corresponds exactly to the form nine 𝑘 minus one.
We also note that the case for
three 𝑘 plus one is pretty much the same, except we replace all the negative signs
with positive signs. Hence, this case corresponds to the
final form nine 𝑘 plus one. Thus, we can conclude that the
answer is (E). That is, it is possible to prove
that all cube numbers can be written in the three given forms by checking 𝑛 equals
three 𝑘 minus one, 𝑛 equals three 𝑘, and 𝑛 equals three 𝑘 plus one.
Having now seen how to prove
mathematical statements, it remains to be seen how one could prove something is not
correct. In order to prove something is not
true, we only need to find a single case that contradicts it. This is called a
counterexample. Consider, for example, the
statement that all prime numbers are odd. A counterexample to this would be
that two is a prime number, yet it is even, which disproves the statement.
Sometimes finding a counterexample
is easy, but sometimes it requires some more thought. As a slightly more difficult
example, take the statement that for any integer 𝑛, there are more positive
integers less than 𝑛 with an odd number of prime factors than an even number. For example, eight has three prime
factors, since it is two times two times two. But six only has two, since it is
two times three. So if we considered 𝑛 equals 10
for instance, we would find it has five numbers less than it with an odd number of
prime factors and only four with an even number of prime factors. Thus, the property holds for 𝑛
equals 10.
As it turns out, this property
holds for most of the everyday numbers that we might consider. In fact, the first number for which
this is not true is 𝑛 equals 906,150,257. Fortunately, we will not usually
have to consider numbers this large when finding counterexamples. Let us consider a full example of
disproving statements using this method.
Select the counterexample to each
of the given statements. “All integers have an even number
of distinct factors.” Is it (A) 12, (B) three, (C) six,
(D) nine, or (E) 15? “The expression two 𝑛 squared
minus five 𝑛 plus one is positive for all values of 𝑛.” Is it (A) negative one, (B)
negative two, (C) four, (D) two, or (E) zero?
Recall that a counterexample is a
single example that refutes a statement, thus disproving it. Since we have been given five
options in each case, we just have to consider each of them in turn to see whether
they contradict the corresponding statement or not.
In the first case, it is stated
that all integers have an even number of distinct factors. So let us list the factors of each
given option. For example, for 12, we see that it
is equal to one times 12, or three times four, or six times two. Therefore, we can write its factors
as a set of these numbers. Since there are six distinct
factors, which is an even number, 12 is not a counterexample.
Continuing this for the remaining
options, we see that three has factors one and three; six has one, two, three, and
six; nine has one, three, and nine; and 15 has one, three, five, and 15. We see that only nine has an odd
number of distinct factors, which happens because it is a perfect square. And the factor three is
repeated. Thus, the answer is (D) nine.
Now let us consider the second
statement. To find whether the given values
are positive for two 𝑛 squared minus five 𝑛 plus one, we must substitute each of
them for 𝑛 in the expression. So for 𝑛 equals negative one, we
have two times negative one squared minus five times negative one plus one, which is
two plus five plus one. And this is eight, which is
positive. So it is not a counterexample.
For 𝑛 equals negative two, after
some calculations, we get 19, which is also positive. For 𝑛 equals four, we get 13,
which is also positive. But for 𝑛 equals two, we get
negative one, which is not positive, so two is a counterexample to the
statement. For the sake of completeness, we
check 𝑛 equals zero to find it is one; therefore, it is not a counterexample. Thus, the counterexample to the
expression two 𝑛 squared minus five 𝑛 plus one being positive for all values of 𝑛
is option (D) two.
Let us finish by considering the
key points we have learned in this video.
First of all, a mathematical proof
is a logical and systematic argument that shows a statement to be true or false. Proof by deduction, or direct
proof, starts from a known fact and then proceeds in a series of logical steps to a
conclusion. Proof by exhaustion means breaking
a statement down into a series of cases and proving each one individually. And disproof by counterexample
means showing a statement is false using a single example that contradicts it.
