Page 112 - Discrete Mathematics and Its Applications

1.7 Introduction to Proofs 91

Exercises

1. Use a direct proof to show that the sum of two odd integers 23. Show that at least ten of any 64 days chosen must fall on
is even. the same day of the week.
2. Use a direct proof to show that the sum of two even inte- 24. Show that at least three of any 25 days chosen must fall
gers is even. in the same month of the year.
3. Show that the square of an even number is an even number 25. Use a proof by contradiction to show that there is no ratio-
3
using a direct proof. nal number r for which r + r + 1 = 0. [Hint: Assume
4. Show that the additive inverse, or negative, of an even that r = a/b is a root, where a and b are integers and a/b
number is an even number using a direct proof. is in lowest terms. Obtain an equation involving integers
3
by multiplying by b . Then look at whether a and b are
5. Prove that if m + n and n + p are even integers, where
m, n, and p are integers, then m + p is even. What kind each odd or even.]
of proof did you use? 26. Prove that if n is a positive integer, then n is even if and
only if 7n + 4 is even.
6. Use a direct proof to show that the product of two odd
numbers is odd. 27. Prove that if n is a positive integer, then n is odd if and
only if 5n + 6 is odd.
7. Use a direct proof to show that every odd integer is the 2 2
difference of two squares. 28. Prove that m = n if and only if m = n or m =−n.
8. Prove that if n is a perfect square, then n + 2 is not a 29. Prove or disprove that if m and n are integers such that
perfect square. mn = 1, then either m = 1 and n = 1, or else m =−1
and n =−1.
9. Use a proof by contradiction to prove that the sum of an
irrational number and a rational number is irrational. 30. Show that these three statements are equivalent, where a
and b are real numbers: (i) a is less than b,(ii) the average
10. Use a direct proof to show that the product of two rational
of a and b is greater than a, and (iii) the average of a and
numbers is rational.
b is less than b.
11. Prove or disprove that the product of two irrational num- 31. Show that these statements about the integer x are equiv-
bers is irrational. 2
alent: (i)3x + 2 is even, (ii) x + 5 is odd, (iii) x is even.
12. Prove or disprove that the product of a nonzero rational 32. Show that these statements about the real number x are
number and an irrational number is irrational.
equivalent: (i) x is rational, (ii) x/2 is rational, (iii)3x − 1
13. Prove that if x is irrational, then 1/x is irrational. is rational.
14. Prove that if x is rational and x = 0, then 1/x is rational. 33. Show that these statements about the real number x are
15. Use a proof by contraposition to show that if x + y ≥ 2, equivalent: (i) x is irrational, (ii)3x + 2 is irrational,
where x and y are real numbers, then x ≥ 1or y ≥ 1. (iii) x/2 is irrational.
16. Prove that if m and n are integers and mn is even, then m 34. Is this reasoning for finding the solutions of the equa-
√ √
is even or n is even. tion 2x − 1 = x correct? (1) 2x − 1 = x is given;
2
2
2
2
3
17. Show that if n is an integer and n + 5 is odd, then n is (2)2x − 1 = x , obtained by squaring both sides of (1);
2
2
even using (3) x − 1 = 0, obtained by subtracting x from both
sides of (2); (4) (x − 1)(x + 1) = 0, obtained by factor-
a) a proof by contraposition. 2
ing the left-hand side of x − 1; (5) x = 1or x =−1,
b) a proof by contradiction.
which follows because ab = 0 implies that a = 0or
18. Prove that if n is an integer and 3n + 2 is even, then n is b = 0.
even using √
35. Are these steps for finding the solutions of x + 3 =
a) a proof by contraposition. √
3 − x correct? (1) x + 3 = 3 − x is given; (2) x + 3 =
b) a proof by contradiction. 2
x − 6x + 9, obtained by squaring both sides of (1);(3)
19. Prove the proposition P(0), where P(n) is the proposi- 0 = x − 7x + 6, obtained by subtracting x + 3 from
2
2
tion “If n is a positive integer greater than 1, then n >n.” both sides of (2);(4)0 = (x − 1)(x − 6), obtained by
What kind of proof did you use? factoring the right-hand side of (3);(5) x = 1or x = 6,
20. Prove the proposition P(1), where P(n) is the proposi- which follows from (4) because ab = 0 implies that
2
tion “If n is a positive integer, then n ≥ n.” What kind a = 0or b = 0.
of proof did you use? 36. Show that the propositions p 1 , p 2 , p 3 , and p 4 can be
21. Let P(n) be the proposition “If a and b are positive real shown to be equivalent by showing that p 1 ↔ p 4 , p 2 ↔
n
n
n
numbers, then (a + b) ≥ a + b .” Prove that P(1) is p 3 , and p 1 ↔ p 3 .
true. What kind of proof did you use? 37. Show that the propositions p 1 ,p 2 ,p 3 ,p 4 , and p 5 can
22. Show that if you pick three socks from a drawer contain- be shown to be equivalent by proving that the conditional
ing just blue socks and black socks, you must get either statements p 1 → p 4 , p 3 → p 1 , p 4 → p 2 , p 2 → p 5 , and
a pair of blue socks or a pair of black socks. p 5 → p 3 are true.