108
Proofs, Induction, and Number Theory
3. Provide counterexamples to the following statements.
a. Every geometric figure with four right angles is a square.
b. If a real number is not positive, then it must be negative.
c. All people with red hair have green eyes or are tall.
d. All people with red hair have green eyes and are tall.
4. Provide counterexamples to the following statements.
a. If a and b are integers where a 0 b and b 0 a, then a = b.
b. If n
2
> 0 then n > 0.
c. If n is an even number, then n
2
+ 1 is prime.
d. If n is a positive integer, then n
3
> n!.
5. Provide a counterexample to the following statement: The number n is an odd integer if and only if
3n + 5 is an even integer.
6. Provide a counterexample to the following statement: The number n is an even integer if and only if
3n + 2 is an even integer.
7. a. Find two even integers whose sum is not a multiple of 4.
b. What is wrong with the following “proof” that the sum of two even numbers is a multiple of 4?
Let x and y be even numbers. Then x = 2m and y = 2m, where m is an integer, so x + y = 2m + 2m = 4m,
which is an integral multiple of 4.
8. a. Find an example of an odd number x and an even number y such that x − y = 7.
b. What is wrong with the following “proof” that an odd number minus an even number is always 1?
Let x be odd and y be even. Then x = 2m + 1, y = 2m, where m is an integer, and x − y = 2m + 1 − 2m = 1.
For Exercises 9–46, prove the given statement.
9. If n = 25, 100, or 169, then n is a perfect square and is a sum of two perfect squares.
10. If n is an even integer, 4 ≤ n ≤ 12, then n is a sum of two prime numbers.
11. For any positive integer n less than or equal to 3, n! < 2
n
.
12. For 2 ≤ n ≤ 4, n
2
≥ 2
n
.
13. The sum of two even integers is even (do a direct proof).
14. The sum of two even integers is even (do a proof by contradiction).
15. The sum of two odd integers is even.
16. The sum of an even integer and an odd integer is odd.
17. An odd integer minus an even integer is odd.
18. If n is an even integer, then n
2
− 1 is odd.
19. The product of any two consecutive integers is even.
20. The sum of an integer and its square is even.
21. The square of an even number is divisible by 4.
22. For every integer n, the number 3(n
2
+ 2n + 3) − 2n
2
is a perfect square.
23. If a number x is positive, so is x + 1 (do a proof by contraposition).
24. If n is an odd integer, then it is the difference of two perfect squares.
25. The number n is an odd integer if and only if 3n + 5 = 6k + 8 for some integer k.
26. The number n is an even integer if and only if 3n + 2 = 6k + 2 for some integer k.
Proofs, Induction, and Number Theory
3. Provide counterexamples to the following statements.
a. Every geometric figure with four right angles is a square.
b. If a real number is not positive, then it must be negative.
c. All people with red hair have green eyes or are tall.
d. All people with red hair have green eyes and are tall.
4. Provide counterexamples to the following statements.
a. If a and b are integers where a 0 b and b 0 a, then a = b.
b. If n
2
> 0 then n > 0.
c. If n is an even number, then n
2
+ 1 is prime.
d. If n is a positive integer, then n
3
> n!.
5. Provide a counterexample to the following statement: The number n is an odd integer if and only if
3n + 5 is an even integer.
6. Provide a counterexample to the following statement: The number n is an even integer if and only if
3n + 2 is an even integer.
7. a. Find two even integers whose sum is not a multiple of 4.
b. What is wrong with the following “proof” that the sum of two even numbers is a multiple of 4?
Let x and y be even numbers. Then x = 2m and y = 2m, where m is an integer, so x + y = 2m + 2m = 4m,
which is an integral multiple of 4.
8. a. Find an example of an odd number x and an even number y such that x − y = 7.
b. What is wrong with the following “proof” that an odd number minus an even number is always 1?
Let x be odd and y be even. Then x = 2m + 1, y = 2m, where m is an integer, and x − y = 2m + 1 − 2m = 1.
For Exercises 9–46, prove the given statement.
9. If n = 25, 100, or 169, then n is a perfect square and is a sum of two perfect squares.
10. If n is an even integer, 4 ≤ n ≤ 12, then n is a sum of two prime numbers.
11. For any positive integer n less than or equal to 3, n! < 2
n
.
12. For 2 ≤ n ≤ 4, n
2
≥ 2
n
.
13. The sum of two even integers is even (do a direct proof).
14. The sum of two even integers is even (do a proof by contradiction).
15. The sum of two odd integers is even.
16. The sum of an even integer and an odd integer is odd.
17. An odd integer minus an even integer is odd.
18. If n is an even integer, then n
2
− 1 is odd.
19. The product of any two consecutive integers is even.
20. The sum of an integer and its square is even.
21. The square of an even number is divisible by 4.
22. For every integer n, the number 3(n
2
+ 2n + 3) − 2n
2
is a perfect square.
23. If a number x is positive, so is x + 1 (do a proof by contraposition).
24. If n is an odd integer, then it is the difference of two perfect squares.
25. The number n is an odd integer if and only if 3n + 5 = 6k + 8 for some integer k.
26. The number n is an even integer if and only if 3n + 2 = 6k + 2 for some integer k.