There are no integers that are both even and odd! Examples: ii is even since E = [2){3}, E is even since 8 = {2][4), I] is even since ID = [2){0}, 3...

4. Lesson 4

For these exercises, you will need to know the definitions of even and odd integers. An integer n is even if n = 2k for some integer k. An integer n is odd if n = 2k + 1 for some integer k. There are no integers that are both even and odd! Examples: 6 is even since 6 = (2)(3), −8 is even since −8 = (2)(−4), 0 is even since 0 = (2)(0), 3 is odd since 3 = 2(1) + 1, and −9 is odd since −9 = (2)(−5) + 1.

(1) Give a direct proof that the sum of an odd integer and an even integer is odd. Hint: Start by letting m be an odd integer and letting n be an even integer. That means m = 2k + 1 for some integer k and n = 2j for some integer j. Notice that if we let the odd and even integers be 2k + 1 and 2k, the proof will only account for the cases in which n is one less than m. That is why we need to have m = 2k + 1 and n = 2j for integers k, j, so that the sum of any odd and any even will be considered. You are interested in m + n, so add them up and see what you get. Why is the thing you get an odd integer (think about the definition of odd)?

(2) Give an indirect proof that if n 3 is even, then n is even. Hint: Study the solution of a similar statement in the sample solutions for this lesson.

(3) Give a proof by contradiction that if 5n − 4 is odd, then n is odd. Hint: This is the problem in this set that gives the most grief. Study the section in the notes where the mechanics of proving a statement of the form If P, then Q by contradiction is discussed. Be sure you understand why the first line of the proof should be something like Suppose 5n − 4 is odd and n is even.

(4) Give an example of a predicate P(n) about positive integers n, such that P(n) is true for every positive integer from 1 to one billion, but which is never-the-less not true for all positive integers. (Hints: (1) There is a really simple choice possible for the predicate P(n), (2) Make sure you write down a predicate with variable n, and not a proposition!) The purpose of this problem is to convince you that when checking a for all type proposition, it is not good enough to just check the truth for a few sample cases, or, for that matter, even a few billion sample cases. A general proof that covers all possible cases is necessary.

(5) Give a counterexample to the proposition Every positive integer that ends with the digits 13 is a prime.

(6) (bonus) The maximum of two numbers, a and b, is a provided a ≥ b. Notation: max(a, b) = a. The minimum of a and b is a provided a ≤ b. Notation: min(a, b) = a. Examples: max(2, 3) = 3, max(5, 0) = 5, min(2, 3) = 2, min(5, 0) = 0, max(4, 4) = min(4, 4) = 4. Give a proof by cases (two cases is the natural choice for this problem) that for any numbers s, t, min(s, t) + max(s, t) = s + t.

is. There are no integers that are both even and odd! Examples: ii is even since E = [2){3},—E is even since —8 = {2][—4), I] is even since ID = [2){0}, 3 is odd since 3 = 2(1) + 1, and—9 is odd since —9 = {EH—5] + 1. {1] Give a direct proof that the sum of an odd integer and an even integer is odd. Hint: Start by letting m be an odd integer and letting it be an even integer. That meansto = 23:: + 1 for some integer in and n. = 2;: for some integer 3‘. Notice that if we let the oddand even integers he 2!: + 1 and 2.1:, the proof will only account for the cases in which n isone less than at. That is why we need to have m = 2}: +1 and n = 23‘ for integers Raj, sothat the sum of any odd and any even will be considered. You are interested in m + n, soadd them up and see what you get. 1Why is the thing you get an odd integer {think aboutthe deﬁnition of odd]? {2) Give an indirect proof that if n3 is even, then it is even. Hint: Study the solution of asimilar statement in the sample solutions for this lesson. {3] Give a proof by contradiction that if 511. — :1 is odd, then u. is odd.Hint: This is the problem in this set that gives the most grief. Study the section in thenotes where the mechanics of proving a statement of the form [f P, then Q by contradiction is discussed. Be sure you understand why the ﬁrst line of the proof should be somethinglike Suppose 5n. — :1 is odd and n is seen. {41] Give an example of a predicate P[n] about positive integers n, such that P[n) is true forevery positive integer from 1 to one billion, but which is never-the—less not true for all pos—itive integers. (Hints: [1] There is a really simple choice possible for the predicate P[n),[2) Make sure you write down a predicate with variable it, and not a proposition!) Thepurpose of this problem is to convince you that when checking a for all type proposition, itis not good enough to just check the truth for a kw sample cases, or, for that matter, evena ﬂaw billion sample cases. A general proof that covers all possible cases is necessary. {5] Give a counterexample to the proposition Every positive integer that ends with the digits13 is a prime. (ti) (bonus) The maximum of twn numbers, a and b, is o provided a 2 b. Notation: maxﬁo, b} =o. The minimum of a and b is o; provided a if. 5:. Notation: min[o;,b] = {1. Examples:max[2,3) = 3, max[5,ﬂ) = 5, min(2,3] = 2, min(5,ﬂ) = ID, max[4,4) = min{4,4] = :1. Give a proof by cases {two cases is the natural choice for this problem) that for any numbers3! t! min{s, t) + max{s, t) = s + t.