we define addition, multiplication, subtraction and division, though we
will use these operations freely. We accept and use such things as the
distributive and commutative properties of addition and multiplication, as
well as other standard properties of arithmetic and algebra.
As mentioned in Section 1.9, we accept as fact the natural ordering
of the elements of N, Z, Q and R, so that (for example) statements such as
“5 < 7,” and “x < y implies −x > − y,” do not need to be justified.
In addition, we accept the following fact without justification or proof.
Fact 4.1
Suppose a and b are integers. Then:
• a + b ∈ Z
• a − b ∈ Z
• ab ∈ Z
These three statements can be combined. For example, we see that if a, b
and c are integers, then a2b − ca + b is also an integer.
We will also accept as obvious the fact that any integer a can be divided
by a non-zero integer b, resulting in a unique quotient q and remainder r.
For example, b = 3 goes into a = 17 q = 5 times with remainder r = 2. In
symbols, 17 = 5 · 3 + 2, or a = qb + r. This fact, called the division algorithm,
was mentioned on page 29.
(The Division Algorithm) Given integers a and b with b > 0, there exist
unique integers q and r for which a = qb + r and 0 ≤ r < b.
Another fact that we will accept without proof (at least for now) is
that every natural number greater than 1 has a unique factorization into
primes. For example, the number 1176 can be factored into primes as
1176 = 2 · 2 · 2 · 3 · 7 · 7 = 23 · 3 · 72. By unique we mean that any factorization
of 1176 into primes will have exactly the same factors (i.e., three 2’s, one 3
and two 7’s). Thus, for example, there is no valid factorization of 1176 that
has a factor of 5. You may be so used to factoring numbers into primes
that it seems obvious that there cannot be different prime factorizations
of the same number, but in fact this is a fundamental result whose proof
is not transparent. Nonetheless, we will be content to assume that every
natural number greater than 1 has a unique factorization into primes.
(We will revisit the issue of a proof in Section 10.2.)
We will introduce other accepted facts, as well as definitions, as needed.
92
Direct Proof
4.3 Direct Proof
This section explains a simple way to prove theorems or propositions
that have the form of conditional statements. The technique is called
direct proof. To simplify the discussion, our first examples will involve
proving statements that are almost obviously true. Thus we will call the
statements propositions rather than theorems. (Remember, a proposition
is a statement that, although true, is not as significant as a theorem.)
To understand how the technique of direct proof works, suppose we
have some proposition of the following form.
Proposition
If P, then Q.
This proposition is a conditional statement of form P ⇒ Q. Our goal
is to show that this conditional statement is true. To see how to proceed,
look at the truth table.
P
Q
P ⇒ Q
T
T
T
T
F
F
F
T
T
F
F
T
The table shows that if P is false, the statement P ⇒ Q is automatically
true. This means that if we are concerned with showing P ⇒ Q is true, we
don’t have to worry about the situations where P is false (as in the last
two lines of the table) because the statement P ⇒ Q will be automatically
true in those cases. But we must be very careful about the situations
where P is true (as in the first two lines of the table). We must show that
the condition of P being true forces Q to be true also, for that means the
second line of the table cannot happen.
This gives a fundamental outline for proving statements of the form
P ⇒ Q. Begin by assuming that P is true (remember, we don’t need to worry
about P being false) and show this forces Q to be true. We summarize this
as follows.
Outline for Direct Proof
Proposition
If P, then Q.
Proof. Suppose P.
...
Therefore Q.
■
Direct Proof
93
So the setup for direct proof is remarkably simple.
The first line
of the proof is the sentence “Suppose P .” The last line is the sentence
“Therefore Q .” Between the first and last line we use logic, definitions and
standard math facts to transform the statement P to the statement Q. It
is common to use the word “Proof” to indicate the beginning of a proof,
and the symbol
to indicate the end.
As our first example, let’s prove that if x is odd then x2 is also odd.
(Granted, this is not a terribly impressive result, but we will move on to
more significant things in due time.) The first step in the proof is to fill
in the outline for direct proof. This is a lot like painting a picture, where
the basic structure is sketched in first. We leave some space between the
first and last line of the proof. The following series of frames indicates the
steps you might take to fill in this space with a logical chain of reasoning.
Proposition
If x is odd, then x2 is odd.
Proof. Suppose x is odd.
Therefore x2 is odd.
■
Now that we have written the first and last lines, we need to fill in the
space with a chain of reasoning that shows that x being odd forces x2 to
be odd.
In doing this it’s always advisable to use any definitions that apply.
The first line says x is odd, and by Definition 4.2 it must be that x = 2a + 1
for some a ∈ Z, so we write this in as our second line.
Proposition
If x is odd, then x2 is odd.
Proof. Suppose x is odd.
Then x = 2a + 1 for some a ∈ Z , by definition of an odd number.
Therefore x2 is odd.
■
Now jump down to the last line, which says x2 is odd. Think about what
the line immediately above it would have to be in order for us to conclude
that x2 is odd. By the definition of an odd number, we would have to have
x2 = 2a + 1 for some a ∈ Z. However, the symbol a now appears earlier in
the proof in a different context, so we should use a different symbol, say b.
94
Direct Proof
Proposition
If x is odd, then x2 is odd.
Proof. Suppose x is odd.
Then x = 2a + 1 for some a ∈ Z, by definition of an odd number.
Thus x2 = 2b + 1 for an integer b .
Therefore x2 is odd, by definition of an odd number.
■
We are almost there. We can bridge the gap as follows.
Proposition
If x is odd, then x2 is odd.
Proof. Suppose x is odd.
Then x = 2a + 1 for some a ∈ Z, by definition of an odd number.
Thus x2 = (2a + 1)2 = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1 .
So x2 = 2b + 1 w
here b is the integer b = 2a2 + 2a.
Thus x2 = 2b + 1 for an integer b.
Therefore x2 is odd, by definition of an odd number.
■
Finally, we may wish to clean up our work and write the proof in paragraph
form. Here is our final version.
Proposition
If x is odd, then x2 is odd.
Proof. Suppose x is odd. Then x = 2a+1 for some a ∈ Z, by definition
of an odd number. Thus x2 = (2a+1)2 = 4a2 +4a+1 = 2(2a2 +2a)+1, so
x2 = 2b + 1 where b = 2a2 + 2a ∈ Z. Therefore x2 is odd, by definition
of an odd number.
■
At least initially, it’s generally a good idea to write the first and last line
of your proof first, and then fill in the gap, sometimes jumping alternately
between top and bottom until you meet in the middle, as we did above. This
way you are constantly reminded that you are aiming for the statement
at the bottom. Sometimes you will leave too much space, sometimes not
enough. Sometimes you will get stuck before figuring out what to do. This
is normal. Mathematicians do scratch work just as artists do sketches for
their paintings.
Direct Proof
95
Here is another example. Consider proving following proposition.
Proposition
Let a, b and c be integers. If a | b and b | c, then a | c.
Let’s apply the basic outline for direct proof. To clarify the procedure
we will write the proof in stages again.
Proposition
Let a, b and c be integers. If a | b and b | c, then a | c.
Proof. Suppose a | b and b | c.
Therefore a | c.
■
Our first step is to apply Definition 4.4 to the first line. The definition
says a | b means b = ac for some integer c, but since c already appears in
a different context on the first line, we must use a different letter, say d.
Similarly let’s use a new letter e in the definition of b | c.
Proposition
Let a, b and c be integers. If a | b and b | c, then a | c.
Proof. Suppose a | b and b | c.
By Definition 4.4, we know a | b means there is an integer d with b = ad .
Likewise, b | c means there is an integer e for which c = be .
Therefore a | c.
■
We have almost bridged the gap. The line immediately above the last line
should show that a | c. According to Definition 4.4, this line should say
that c = ax for some integer x. We can get this equation from the lines at
the top, as follows.
Proposition
Let a, b and c be integers. If a | b and b | c, then a | c.
Proof. Suppose a | b and b | c.
By Definition 4.4, we know a | b means there is an integer d with b = ad.
Likewise, b | c means there is an integer e for which c = be.
Thus c = be = (ad)e = a(de) , so c = ax for the integer x = de .
Therefore a | c.
■
The next example is presented all at once rather than in stages.
96
Direct Proof
Proposition
If x is an even integer, then x2 − 6x + 5 is odd.
Proof. Suppose x is an even integer.
Then x = 2a for some a ∈ Z, by definition of an even integer.
So x2−6x+5 = (2a)2−6(2a)+5 = 4a2−12a+5 = 4a2−12a+4+1 = 2(2a2−6a+2)+1.
Therefore we have x2 − 6x + 5 = 2b + 1, where b = 2a2 − 6a + 2 ∈ Z.
Consequently x2 − 6x + 5 is odd, by definition of an odd number.
■
One doesn’t normally use a separate line for each sentence in a proof,
but for clarity we will often do this in the first few chapters of this book.
Our next example illustrates a standard technique for showing two
quantities are equal. If we can show m ≤ n and n ≤ m then it follows that
m = n. In general, the reasoning involved in showing m ≤ n can be quite
different from that of showing n ≤ m.
Recall Definition 4.6 of a least common multiple on page 90.
Proposition
If a, b, c ∈ N, then lcm(ca, cb) = c · lcm(a, b).
Proof. Assume a, b, c ∈ N. Let m = lcm(ca, cb) and n = c · lcm(a, b). We will
show m = n. By definition, lcm(a, b) is a multiple of both a and b, so
lcm(a, b) = ax = b y for some x, y ∈ Z. From this we see that n = c · lcm(a, b) =
cax = cb y is a multiple of both ca and cb. But m = lcm(ca, cb) is the smallest
multiple of both ca and cb. Thus m ≤ n.
On the other hand, as m = lcm(ca, cb) is a multiple of both ca and cb,
1
we have m = cax = cb y for some x, y ∈ Z. Then
m
c
= ax = b y is a multiple of
both a and b. Therefore lcm(a, b) ≤ 1 m
c
, so c · lcm(a, b) ≤ m, that is, n ≤ m.
We’ve shown m ≤ n and n ≤ m, so m = n. The proof is complete.
■
The examples we’ve looked at so far have all been proofs of statements
about integers. In our next example, we are going to prove that if x and y
p
p
are positive real numbers for which x ≤ y, then
x ≤
y. You may feel that
the proof is not as “automatic” as the proofs we have done so far. Finding
the right steps in a proof can be challenging, and that is part of the fun.
p
p
Proposition
Let x and y be positive numbers. If x ≤ y, then
x ≤
y.
Proof. Suppose x ≤ y. Subtracting y from both sides gives x − y ≤ 0.
p 2 p
This can be written as
x − y2 ≤ 0.
p
p
p
p
Factor this to get ( x −
y)( x + y) ≤ 0.
p
p
p
p
Dividing both sides by the positive number
x + y produces
x − y ≤ 0.
p
p
p
Adding
y to both sides gives
x ≤
y.
■
Direct Proof
97
This proposition tells us that whenever x ≤ y, we can take the square
p
p
root of both sides and be assured that
x ≤
y. This can be useful, as we
will see in our next proposition.
p
That proposition will concern the expression 2 x y ≤ x + y. Notice when
you substitute random positive values for the variables, the expression is
p
p
true. For example, for x = 6 and y = 4, the left side is 2 6 · 4 = 4 6 ≈ 9.79,
p
which is less than the right side 6 + 4 = 10. Is it true that 2 x y ≤ x + y for
any positive x and y? How could we prove it?
To see how, let’s first cast this into the form of a conditional statement:
p
If x and y are positive real numbers, then 2 x y ≤ x + y. The proof begins
p
with the assumption that x and y are positive, and ends with 2 x y ≤ x + y.
In mapping out a strategy, it can be helpful to work backwards, working
p
from 2 x y ≤ x + y to something that is obviously true. Then the steps can
p
be reversed i
n the proof. In this case, squaring both sides of 2 x y ≤ x + y
gives us
4x y ≤ x2 + 2xy + y2.
Now subtract 4x y from both sides and factor.
0
≤ x2 − 2x y + y2
0
≤ (x − y)2
But this last line is clearly true, since the square of x− y cannot be negative!
This gives us a strategy for the proof, which follows.
p
Proposition
If x and y are positive real numbers, then 2 x y ≤ x + y.
Proof. Suppose x and y are positive real numbers.
Then 0 ≤ (x − y)2, that is, 0 ≤ x2 − 2x y + y2.
Adding 4x y to both sides gives 4x y ≤ x2 + 2x y + y2.
Factoring yields 4x y ≤ (x + y)2.
Previously we proved that such an inequality still holds after taking the
p
square root of both sides; doing so produces 2 x y ≤ x + y.
■
Notice that in the last step of the proof we took the square root of both
p
p
sides of 4x y ≤ (x + y)2 and got
4x y ≤
(x + y)2, and the fact that this did
not reverse the symbol ≤ followed from our previous proposition. This
is an important point. Often the proof of a proposition or theorem uses
another proposition or theorem (that has already been proved).
98
Direct Proof
4.4 Using Cases
In proving a statement is true, we sometimes have to examine multiple
cases before showing the statement is true in all possible scenarios. This
section illustrates a few examples.
Our examples will concern the expression 1 + (−1)n(2n − 1). Here is a
table showing its value for various integers for n. Notice that 1+(−1)n(2n−1)
is a multiple of 4 in every line.
n
1 + (−1)n(2n − 1)
1
0
2
4
3
−4
4
8
5
−8
6
12
Is 1 + (−1)n(2n − 1) always a multiple of 4? We prove the answer is “yes”
in our next example. Notice, however, that the expression 1 + (−1)n(2n − 1)
behaves differently depending on whether n is even or odd, for in the first
case (−1)n = 1, and in the second (−1)n = −1. Thus the proof must examine
these two possibilities separately.
Proposition
If n ∈ N, then 1 + (−1)n(2n − 1) is a multiple of 4.
Proof. Suppose n ∈ N.
Then n is either even or odd. Let’s consider these two cases separately.
Case 1. Suppose n is even. Then n = 2k for some k ∈ Z, and (−1)n = 1.
Thus 1 + (−1)n(2n − 1) = 1 + (1)(2 · 2k − 1) = 4k, which is a multiple of 4.
Book of Proof Page 14
