Formal MethodsKey to Homework Assignment 3, Part 2February 12, 2007• Prove that multiplication of rational numbers is well-defined.Proof. Suppose m, n, p, q, r, s, t and u are integers such that n, q, s, and u are nonzero,m/n = r/s, and p/q = t/u. We want to see thatmnpq=rstu,or, equivalentlympnq=rtsu.From the definition of e quality of rational numbers, we need to see thatmpsu = nqr t.But by assumption m/n = r/s and p/q = t/u. So ms = nr and pu = qt. Substitutinginto the left-hand side of the equation mpsu = nqrt, we getnrqt = nqrt.Reversing the steps, then, we see thatmnpq=rstu,and multiplication of rational numbers is well-defined.89. Is the converse of “if n is any prime, then 2n+ 1 prime” true? If your answer is yes,prove the statement. Otherwise find a counterexample.The converse is “if 2n+ 1 is prime, then n is prime.” This is false. For example,24+ 1 = 17, but 4 isn’t prime.94. Prove that if a and b are rational numbers with a < b, then there exists a rationalnumber r such that a < r < b.1Proof. Define r = (a + b)/2. Then if m, n, p, and q are integers with n and q nonzero,such that a = m/n and b = p/q, we haver =mn+pq12=mq + npnq12=mq + np2nq.Since mq + np is an integer and 2nq is a nonzero integer, we see that r is a rationalnumber.To check that a < r < b, we can check that the differences r − a and b − r are bothpositive. We have thatr − a =a + b2− a =a + b − 2a2=b − a2Since a < b, we know that b −a > 0. So r −a > 0 and a < r. The argument that b −ris positive is entirely analogous:b − r = b −a + b2=2b − a − b2=b − a2,which, as we’ve just seen is positive. So r is a rational number such that a < r < b.95. Prove that if x is a positive real number, then x + 1/x ≥ 2.Proof. This is similar to problem 80, which we proved by contradiction. So let’s tryassuming the contrary. That is, we assume that x is a positive real numb er such thatx + 1/x < 2. Since x is positive, we can multiply both sides of this inequality by x andgetx2+ 1 < 2x,or, equivalently,x2− 2x + 1 = (x − 1)2< 0.However, since x is a real number (x − 1)2≥ 0, and this is a contradiction. So theassumption that x + 1/x < 2 must be false, and x + 1/x ≥ 2 for all positive realnumbers x.96. (a) Find positive real numbers x and y such that√x + y 6=√x +√y.If x = y = 1, then x and y are positive, and√x + y =√2 but√x +√y = 2.Since 2 is rational and√2 is irrational, 2 6=√2.(b) Prove that if x and y are positive real numbers, then√x + y ≤√x +√y.First Proof. We’ve proved a number of inequalities involving real numbers byusing contradiction. So let’s try contradiction. So we assume that x and y arepositive real numbers such that√x + y >√x +√y.Since the function f(z) = z2is increasing on the positive reals, we know that if0 < a < b then 0 < a2< b2. So(√x + y)2> (√x +√y)2.2Simplifying, givesx + y > x + 2√xy + y,and subtracting x + y from both sides gives0 > 2√xy,but since x and y are positive reals,√xy > 0. So 2√xy > 0, which is a contra-diction. So the assumption that√x + y >√x +√y must be false, and we havethat√x + y ≤√x +√y, for all positive real numbers x and y.Second Proof. We can reverse the steps in the argument given in the first proofand give a direct proof of the the result. Suppose that x and y are positive realnumbers. Then√xy > 0, and 2√xy > 0. Thusx + y ≤ x + 2√xy + y,or, equivalently,(√x + y)2≤ (√x +√y)2.Since the function g(z) =√z is increasing on the positive reals, we can takesquare roots of both sides of this inequality, and get√x + y ≤√x +√y.Note. Since√xy > 0, this proof actually shows that√x + y <√x
View Full Document