“mcs”一2017/6/5一19：42一page25一#33 1.10.References 25 where w.x,y,z are nonnegative integers.Let P be the assertion that z is even,and let R be the assertion that all three of w,x,y are even.Prove by cases that P IFF R. Hint:An odd number equals 2m+1 for some integer m,so its square equals 4(m2+m)+1. Exam Problems Problem 1.12. Prove that there is an irrational number a such that a3 is rational. Hint:Considerand argue by cases. Problems for Section 1.8 Practice Problems Problem 1.13. Prove that for any n>0,if a"is even,then a is even. Hint:Contradiction. Problem 1.14. Prove that if a·b=,then either a or b must be≤√n,where a,b,and n are nonnegative real numbers.Hint:by contradiction,Section 1.8. Problem 1.15. Let n be a nonnegative integer. (a)Explain why if n2 is even-that is,a multiple of 2-then n is even. (b)Explain why if n2 is a multiple of 3,then n must be a multiple of 3. Problem 1.16. Give an example of two distinct positive integers m,n such that n2 is a multiple of m,but n is not a multiple of m.How about having m be less than n?
“mcs” — 2017/6/5 — 19:42 — page 25 — #33 1.10. References 25 where w; x; y; z are nonnegative integers. Let P be the assertion that z is even, and let R be the assertion that all three of w; x; y are even. Prove by cases that P IFF R: Hint: An odd number equals 2m C 1 for some integer m, so its square equals 4.m2 C m/ C 1. Exam Problems Problem 1.12. Prove that there is an irrational number a such that a p 3 is rational. Hint: Consider p3 2 p 3 and argue by cases. Problems for Section 1.8 Practice Problems Problem 1.13. Prove that for any n > 0, if a n is even, then a is even. Hint: Contradiction. Problem 1.14. Prove that if a b D n, then either a or b must be p n, where a; b, and n are nonnegative real numbers. Hint: by contradiction, Section 1.8. Problem 1.15. Let n be a nonnegative integer. (a) Explain why if n 2 is even—that is, a multiple of 2—then n is even. (b) Explain why if n 2 is a multiple of 3, then n must be a multiple of 3. Problem 1.16. Give an example of two distinct positive integers m; n such that n 2 is a multiple of m, but n is not a multiple of m. How about having m be less than n?
“mcs”一2017/6/5一19：42一page26一#34 26 Chapter I What is a Proof? Class Problems Problem 1.17. How far can you generalize the proof of Theorem 1.8.1 that v2 is irrational?For example,how about√3？ Problem 1.18. Prove that log4 6 is irrational. Problem 1.19. Prove by contradiction that v3+v2 is irrational. Hint:(√3+√2)(5-√2) Problem 1.20. Here is a generalization of Problem 1.17 that you may not have thought of: Lemma.Let the coefficients of the polynomial ao+ax+a2x2+...+am-1xm-1+xm be integers.Then any real root of the polynomial is either integral or irrational. (a)Explain why the Lemma immediately implies that k is irrational whenever k is not an mth power of some integer. (b)Carefully prove the Lemma. You may find it helpful to appeal to: Fact.If a prime p is a factor of some power of an integer,then it is a factor of that integer. You may assume this Fact without writing down its proof,but see if you can explain why it is true. Exam Problems Problem 1.21. Prove that log 12 is irrational
“mcs” — 2017/6/5 — 19:42 — page 26 — #34 Chapter 1 What is a Proof?26 Class Problems Problem 1.17. How far can you generalize the proof of Theorem 1.8.1 that p 2 is irrational? For example, how about p 3? Problem 1.18. Prove that log4 6 is irrational. Problem 1.19. Prove by contradiction that p 3 C p 2 is irrational. Hint: . p 3 C p 2/.p 3 p 2/ Problem 1.20. Here is a generalization of Problem 1.17 that you may not have thought of: Lemma. Let the coefficients of the polynomial a0 C a1x C a2x 2 C C am1x m1 C x m be integers. Then any real root of the polynomial is either integral or irrational. (a) Explain why the Lemma immediately implies that mp k is irrational whenever k is not an mth power of some integer. (b) Carefully prove the Lemma. You may find it helpful to appeal to: Fact. If a prime p is a factor of some power of an integer, then it is a factor of that integer. You may assume this Fact without writing down its proof, but see if you can explain why it is true. Exam Problems Problem 1.21. Prove that log9 12 is irrational
“mcs”一2017/6/5一19：42一page27一#35 1.10.References 27 Problem 1.22. Prove that log218 is irrational. Problem 1.23. A familiar proof that7is irrational depends on the fact that a certain equation among those below is unsatisfiable by integers a,b>0.Note that more than one is unsatisfiable.Indicate the equation that would appear in the proof,and explain why it is unsatisfiable.(Do not assume that 72 is irrational.) i.a2=72+b2 ii.a3=72+b3 ii.a2=72b2 iv.a3=72b3 v.a3=7b3 vi.(ab)3=72 Homework Problems Problem 1.24. The fact thatthat there are irrational numbers a,b such that ab is rational was proved in Problem 1.9 by cases.Unfortunately,that proof was nonconstructive:it didn't reveal a specific pair a,b with this property.But in fact,it's easy to do this: let a::=V2 and b::=2l0g2 3. We know a =v2 is irrational,and ab=3 by definition.Finish the proof that these values for a,b work,by showing that 2log2 3 is irrational. Problem 1.25. Here is a different proof that v2 is irrational,taken from the American Mathemat- ical Monthly,v.116,#1,Jan.2009,p.69: Proof.Suppose for the sake of contradiction that v2 is rational,and choose the least integer >0 such that (2-1)g is a nonnegative integer.Let ':: (-1)q.Clearlyg.But an easy computation shows that(' is a nonnegative integer,contradicting the minimality of q
“mcs” — 2017/6/5 — 19:42 — page 27 — #35 1.10. References 27 Problem 1.22. Prove that log12 18 is irrational. Problem 1.23. A familiar proof that p3 7 2 is irrational depends on the fact that a certain equation among those below is unsatisfiable by integers a; b > 0. Note that more than one is unsatisfiable. Indicate the equation that would appear in the proof, and explain why it is unsatisfiable. (Do not assume that p3 7 2 is irrational.) i. a 2 D 7 2 C b 2 ii. a 3 D 7 2 C b 3 iii. a 2 D 7 2b 2 iv. a 3 D 7 2b 3 v. a 3 D 7 3b 3 vi. .ab/3 D 7 2 Homework Problems Problem 1.24. The fact that that there are irrational numbers a; b such that a b is rational was proved in Problem 1.9 by cases. Unfortunately, that proof was nonconstructive: it didn’t reveal a specific pair a; b with this property. But in fact, it’s easy to do this: let a WWD p 2 and b WWD 2 log2 3. We know a D p 2 is irrational, and a b D 3 by definition. Finish the proof that these values for a; b work, by showing that 2 log2 3 is irrational. Problem 1.25. Here is a different proof that p 2 is irrational, taken from the American Mathematical Monthly, v.116, #1, Jan. 2009, p.69: Proof. Suppose for the sake of contradiction that p 2 is rational, and choose the least integer q > 0 such that p 2 1 q is a nonnegative integer. Let q 0 WWD p 2 1 q. Clearly 0 < q0 < q. But an easy computation shows that p 2 1 q 0 is a nonnegative integer, contradicting the minimality of q.
“mcs”一2017/6/5一19：42一page28一#36 28 Chapter I What is a Proof? (a)This proof was written for an audience of college teachers,and at this point it is a little more concise than desirable.Write out a more complete version which includes an explanation of each step. (b)Now that you have justified the steps in this proof,do you have a preference for one of these proofs over the other?Why?Discuss these questions with your teammates for a few minutes and summarize your team's answers on your white- board. Problem 1.26. For n =40,the value of polynomial p(n)::=n2+n+41 is not prime,as noted in Section 1.1.But we could have predicted based on general principles that no nonconstant polynomial can generate only prime numbers. In particular,let g(n)be a polynomial with integer coefficients,and let c::=q(0) be the constant term of q. (a)Verify that g(cm)is a multiple of c for all m Z. (b)Show that if g is nonconstant and c 1,then as n ranges over the nonnegative integers N there are infinitely many g(n)EZ that are not primes. Hint:You may assume the familiar fact that the magnitude of any nonconstant polynomial q(n)grows unboundedly as n grows. (c)Conclude that for every nonconstant polynomial g there must be an n E N such that g(n)is not prime.Hint:Only one easy case remains
“mcs” — 2017/6/5 — 19:42 — page 28 — #36 Chapter 1 What is a Proof?28 (a) This proof was written for an audience of college teachers, and at this point it is a little more concise than desirable. Write out a more complete version which includes an explanation of each step. (b) Now that you have justified the steps in this proof, do you have a preference for one of these proofs over the other? Why? Discuss these questions with your teammates for a few minutes and summarize your team’s answers on your whiteboard. Problem 1.26. For n D 40, the value of polynomial p.n/ WWD n 2 C n C 41 is not prime, as noted in Section 1.1. But we could have predicted based on general principles that no nonconstant polynomial can generate only prime numbers. In particular, let q.n/ be a polynomial with integer coefficients, and let c WWDq.0/ be the constant term of q. (a) Verify that q.cm/ is a multiple of c for all m 2 Z. (b) Show that if q is nonconstant and c > 1, then as n ranges over the nonnegative integers N there are infinitely many q.n/ 2 Z that are not primes. Hint: You may assume the familiar fact that the magnitude of any nonconstant polynomial q.n/ grows unboundedly as n grows. (c) Conclude that for every nonconstant polynomial q there must be an n 2 N such that q.n/ is not prime. Hint: Only one easy case remains
“mcs”一2017/6/5一19：42一page29一#37 2 The Well Ordering Principle Every nonempty set of nonnegative integers has a smallest element. This statement is known as The Well Ordering Principle(WOP).Do you believe it?Seems sort of obvious,right?But notice how tight it is:it requires a nonempry set-it's false for the empty set which has no smallest element because it has no elements at all.And it requires a set of nonnegative integers-it's false for the set of negative integers and also false for some sets of nonnegative rationals-for example,the set of positive rationals.So,the Well Ordering Principle captures something special about the nonnegative integers. While the Well Ordering Principle may seem obvious,it's hard to see offhand why it is useful.But in fact,it provides one of the most important proof rules in discrete mathematics.In this chapter,we'll illustrate the power of this proof method with a few simple examples. 2.1 Well Ordering Proofs We actually have already taken the Well Ordering Principle for granted in proving that v2 is irrational.That proof assumed that for any positive integers m and n, the fraction m/n can be written in lowest terms,that is,in the form m'/n'where m'and n'are positive integers with no common prime factors.How do we know this is always possible? Suppose to the contrary that there are positive integers m and n such that the fraction m/n cannot be written in lowest terms.Now let C be the set of positive integers that are numerators of such fractions.Then m C,so C is nonempty.By WOP,there must be a smallest integer mo C.So by definition of C,there is an integer no >0 such that 1m0 the fraction cannot be written in lowest terms. no This means that mo and no must have a common prime factor,p>1.But mo/p mo no/p no
“mcs” — 2017/6/5 — 19:42 — page 29 — #37 2 The Well Ordering Principle Every nonempty set of nonnegative integers has a smallest element. This statement is known as The Well Ordering Principle (WOP). Do you believe it? Seems sort of obvious, right? But notice how tight it is: it requires a nonempty set—it’s false for the empty set which has no smallest element because it has no elements at all. And it requires a set of nonnegative integers—it’s false for the set of negative integers and also false for some sets of nonnegative rationals—for example, the set of positive rationals. So, the Well Ordering Principle captures something special about the nonnegative integers. While the Well Ordering Principle may seem obvious, it’s hard to see offhand why it is useful. But in fact, it provides one of the most important proof rules in discrete mathematics. In this chapter, we’ll illustrate the power of this proof method with a few simple examples. 2.1 Well Ordering Proofs We actually have already taken the Well Ordering Principle for granted in proving that p 2 is irrational. That proof assumed that for any positive integers m and n, the fraction m=n can be written in lowest terms, that is, in the form m0=n0 where m0 and n 0 are positive integers with no common prime factors. How do we know this is always possible? Suppose to the contrary that there are positive integers m and n such that the fraction m=n cannot be written in lowest terms. Now let C be the set of positive integers that are numerators of such fractions. Then m 2 C, so C is nonempty. By WOP, there must be a smallest integer m0 2 C. So by definition of C, there is an integer n0 > 0 such that the fraction m0 n0 cannot be written in lowest terms. This means that m0 and n0 must have a common prime factor, p > 1. But m0=p n0=p D m0 n0 ;