102
Proofs, Induction, and Number Theory
We’ll never again do a proof like the one in Example 4, and you won’t have
to either! A much more informal proof would be perfectly acceptable in most
circumstances.
13. xy = (2m)(2n)
11, 12, substitution of equals
14. xy = 2(2mn)
13, multiplication fact
15. m is an integer
7, sim
16. n is an integer
10, sim
17. 2mn is an integer
15, 16, number fact
18. xy = 2(2mn) ` 2mn is an integer
14, 17, con
19. (Ek)(k an integer ` xy = 2k)
18, eg
20. (4x)((Ek)(k an integer ` x = 2k) S
number fact (definition
x is even integer)
of even integer)
21. (Ek)(k an integer ` xy = 2k) S
20, ui
xy is even integer
22. xy is an even integer
19, 21, mp
It is understood that x and y are arbitrary, but this could be stated by expressing the
conjecture as
(4x)(4y)(x is an even integer ` y is an even integer S
the product xy is an even integer)
Universal generalization can be applied twice to the result we already have in order
to put the universal quantifiers on the front.
The proof in Example 5 does not explicitly state the hypothesis (that x and
y are even), and it makes implicit use of the definition of an even integer. Even
in informal proofs, however, it is important to identify the hypothesis and the
conclusion, not just what they are in words but what they really mean, by applying appropriate definitions. If we do not clearly understand what we have (the
hypothesis) or what we want (the conclusion), we cannot hope to build a bridge
from one to the other. That’s why it is important to know definitions.
eXAMPLe 5
Following is an informal direct proof that the product of two even integers is even.
Let x = 2m and y = 2n, where m and n are integers. Then xy = (2m)(2n) =
2(2mn), where 2mn is an integer. Thus xy has the form 2k, where k is an integer, and
xy is therefore even.
Notice that we set x = 2m for some integer m (the definition of an even
number), but we set y = 2n. In the formal proof of Example 4, the restriction
on the use of ei required that we use a different multiple of 2 for y than we used
for x. Informally, if we were also to set y = 2m, we would be saying that x and
y are the same integers, which is a very special case.
Proofs, Induction, and Number Theory
We’ll never again do a proof like the one in Example 4, and you won’t have
to either! A much more informal proof would be perfectly acceptable in most
circumstances.
13. xy = (2m)(2n)
11, 12, substitution of equals
14. xy = 2(2mn)
13, multiplication fact
15. m is an integer
7, sim
16. n is an integer
10, sim
17. 2mn is an integer
15, 16, number fact
18. xy = 2(2mn) ` 2mn is an integer
14, 17, con
19. (Ek)(k an integer ` xy = 2k)
18, eg
20. (4x)((Ek)(k an integer ` x = 2k) S
number fact (definition
x is even integer)
of even integer)
21. (Ek)(k an integer ` xy = 2k) S
20, ui
xy is even integer
22. xy is an even integer
19, 21, mp
It is understood that x and y are arbitrary, but this could be stated by expressing the
conjecture as
(4x)(4y)(x is an even integer ` y is an even integer S
the product xy is an even integer)
Universal generalization can be applied twice to the result we already have in order
to put the universal quantifiers on the front.
The proof in Example 5 does not explicitly state the hypothesis (that x and
y are even), and it makes implicit use of the definition of an even integer. Even
in informal proofs, however, it is important to identify the hypothesis and the
conclusion, not just what they are in words but what they really mean, by applying appropriate definitions. If we do not clearly understand what we have (the
hypothesis) or what we want (the conclusion), we cannot hope to build a bridge
from one to the other. That’s why it is important to know definitions.
eXAMPLe 5
Following is an informal direct proof that the product of two even integers is even.
Let x = 2m and y = 2n, where m and n are integers. Then xy = (2m)(2n) =
2(2mn), where 2mn is an integer. Thus xy has the form 2k, where k is an integer, and
xy is therefore even.
Notice that we set x = 2m for some integer m (the definition of an even
number), but we set y = 2n. In the formal proof of Example 4, the restriction
on the use of ei required that we use a different multiple of 2 for y than we used
for x. Informally, if we were also to set y = 2m, we would be saying that x and
y are the same integers, which is a very special case.