CMPS 211 Homework Assignment 05 Solution, Fall 2014

CMPS 211 – Fall 2014 1 Assignment 5 Solution Exercise 1: a) Let a + b = 2n + 1 Let b + c = 2m + 1 a + 2b + c = 2(n + m) + 2 a + c = 2(n + m – b + 2) � (a + c) is even [Direct proof] b) RTP: ab is odd → a is odd and b is odd Suppose that a or b are even If a is even, then a = 2k, then ab = 2k*b, then ab is even If b is even, then b = 2m, then ab = 2m*a, then ab is even then: a or b is even → ab is even [Direct proof] � ab is odd → a is odd and b is odd [Contraposition] Exercise 2: Let a be an irrational number and b, c, d and e integers different from zero • a irrational • ! ! and ! ! rational, o which means − ! ! is also rational o and ! ! is also rational a) RTP: the sum of a rational number and an irrational number is irrational Now, Suppose that the sum of irrational number and rational number is rational; then a + ! ! = ! ! , for some values of {a, b, c, d, e}; then a = !"!!" !" � but !"!!" !" is rational since the addition of two rational numbers is rational � then a is rational (contradiction) � The sum of an irrational and a rational number is irrational CMPS 211 – Fall 2014 2 b) RTP: the product of a nonzero rational number and an irrational number is irrational Suppose that the product of a nonzero rational number and an irrational number is rational So a × ! ! = ! ! a = !" !" which is rational (contradiction) � The product of a nonzero rational number and an irrational number is irrational Exercise 3: • P(1) is if n is a positive integer which in this case it is (1) then 2 ≥ 2 which is true [Constructive Existence Proof] • 2*n >= n+1 → n >= 1, 1>=1, implies P(1) is true [Direct Proof] Exercise 4: RTP: If n is perfect cube, then n+3 is not a perfect cube Assume that their exists n such that it is a perfect cube, and n+3 is also a perfect cube Then n = a3 , and n+3 = b3, for some integers a and b b3 -­‐ a3 = (b -­‐ a) (b2 + ba + a2) = 3 since a and b are integers, then (b-­‐a) is integer, and (b2 + ba + a2), then one of these is correct: • (b -­‐ a)=3 and (b2 + ba + a2)=1 ==>b=3+a ==> 0=8+9a+2a2, then a is not integer ==> contradiction • (b -­‐ a)=1 and (b2 + ba + a2)=3==>b=1+a ==> 0=-­‐2+3a+3a2, then a is not integer ==> contradiction Then if n is a perfect cube, n+3 can’t be a perfect cube Exercise 5: RTP: n is odd ↔ 3n + 2 is odd RTP: n is odd → 3n + 2 is odd (1) 3n + 2 is odd → n is odd (2) To prove (1), we use direct proof CMPS 211 – Fall 2014 3 n = 2k + 1 3(2k + 1) + 2 = 2(3k + 2) + 1 = 2s + 1 which is odd (proved) To prove (2), we use contraposition Suppose that n is even so n = 2m 3(2m) + 2 = 2(3m + 1) = 2t which is even � 3n + 2 is odd → n is odd � n is odd ↔ 3n + 2 is odd Exercise 6: No. This line of reasoning shows that if 5𝑥! − 4 = 𝑥, then we must have x = 1 or x = − 1. These are therefore the only possible solutions, but we have no guarantee that they are solutions, since not all of our steps were reversible (in particular, squaring both sides). Therefore we must substitute these values back into the original equation to determine whether they do indeed satisfy it. Exercise 7: There exists n such that !!! k !!! = n Let n = 3 => 0 + 1 + 2 = 3 [Constructive] Exercise 8: 1. x is rational → x = ! ! where a and b are integers and b is not 0 a. ! ! = ! !" = ! ! where c = 3b => ! ! is rational [Direct proof] b. 5x – 2 = !" ! − 2 = !"!!" ! = ! ! => 5x – 2 is rational [Direct proof] 2. ! ! is rational → ! ! = ! ! a. ! ! = ! ! → 𝑥 = !" ! => x is rational [Direct proof] b. x is rational (a), then 5x is rational, then 5x – 2 is rational [Direct proof] 3. 5x – 2 is rational → 5x − 2 = ! ! a. → 5x = ! ! − 2 → x = !!!! !! then x is rational [Direct proof] b. then ! ! is rational from (1) [Direct proof] x is rational ↔ x/3 is rational ↔ 5x+2 is rational CMPS 211 – Fall 2014 4 Exercise 9: 1. n2 is even then n is even as shown in Ex 1-­‐b, since if n is odd, n2 is odd ==> n =2k a. 1-­‐n = 1-­‐2k = -­‐(2k-­‐1), then 1-­‐n is odd b. n2 is even and n is even, then n3 as shown in Ex 1-­‐b c. n2+1, then n2+1 = (2k)2+1, then n2+1 = 2(2k2)+1, then n2+1 is odd 2. 1-­‐n is odd, then 1-­‐n=2k+1 a. 1-­‐n =2k+1, then n = -­‐2k, then n is even, then n2 is even as shown in Ex 1-­‐b b. n is even and n2 is even, then n3 is even as shown in Ex 1-­‐b c. n = -­‐2k, then n2+1 = 4k + 1 = 2(2k) +1 then n2+1 is odd 3. n3 is even, then n2 or n is even, as shown in Ex1-­‐b; a. if n2 is even, then n is even. b. If n is even then n2 is even as shown in Ex1-­‐b � n3 → n and n2 are even, then all the other statements follow as shown in part 1 4. if n2+1 is odd, then n2+1 = 2k+1 then n2 = 2k then n2 is even, then all the other statements follow as shown in part 1 n2 is even ↔ 1-­‐n is odd ↔ n3 is even ↔ n2+1 is odd