Mathematical thinking problem solving and proofs solution manual 4

183 Chapter 13: The Real Numbers 184 SOLUTIONS FOR PART IV 13. THE REAL NUMBERS 13.1. Sequences. a) 〈x〉 defined by xn = n is monotone but not bounded. Each succeeding term is larger than the previous term, so the sequence is increasing and hence monotone. The set of terms is the set of natural numbers, which is unbounded, so the sequence is unbounded. b) 〈y〉 defined by yn = 1/n is monotone but not bounded. Each succeed- ing term is smaller than the previous term, so the sequence is decreasing and hence monotone. Since 0 < yn ≤ 1 for all n, the sequence is bounded. 13.2. The proverb “A lot of a little makes a lot” describes Theorem 13.9; if a is “a little”, then n can be made large enough so that na is “a lot”. 13.3. Every bounded sequence of real numbers converges—FALSE. The se- quence 〈x〉 with xn = (−1)n is a counterexample. However, it is true that every bounded monotone sequence convergers. 13.4. The interval (a, b) contains its infimum and its supremum—FALSE. The infimum and supremum are a and b, which are not in the open interval. The closed interval [a, b] does contain its infimum and its supremum. 13.5. If the sequence 〈x〉 does not converge to zero, then there exists � > 0 so that for all n, |xn| > �—FALSE. However, it is true that when 〈x〉 does not converge to zero, there exists ε > 0 so that for infinitely many n, |xn| > ε. 13.6. A countable sequence of real numbers. Listing numbers according to the position of the last nonzero digit in their decimal expansions lists only numbers with finitely many nonzero digits in their expansions. All such numbers are rational, so the set listed is countable. 13.7. Every infinite subset of a countable set is countable. Let A be an infinite subset of a countable set B. Since B is countable, there is a bijection f : N → B; it lists the elements of B in some order. The elements of A occur as a subsequence of this, and thus we also have a sequence listing the elements of A. Thus A is countable. Every set that contains an uncountable set is uncountable. Let A be a subset of a set B. If B is finite or countable, then bijections make A also finite or countable. The contrapositive states that if A is uncountable, then B is uncountable. For example, to show that R is uncountable it suffices to show that [0, 1] is uncountable. 13.8. If S is a bounded set of real numbers, and S contains sup(S) and inf(S), then S is a closed interval — FALSE. Counterexamples include the finite set S = {0, 1} and the uncountable set S = [0, 1] ∪ [2, 3]. 13.9. If f : R → R is defined by f (x) = 2x−8x2−8x+17 , then the supremum of the image of f is 1—TRUE. We show that 1 is an upper bound on f (x) and that 1 is in the image. The latter claim follows from f (5) = 2/2 = 1. Since x2 − 8x + 17 ≤ (x − 4)2 + 1, this quadratic polynomial is never zero. Hence the inequality f (x) ≤ 1 is equivalent to 2x − 8 ≤ x 2 − 8x + 17, which is equivalent to 0 ≤ x2 −10x +25. Since x2 −10x +25 = (x −5)2 ≥ 0, the desired inequality is always true. 13.10. Every positive irrational number is the limit of a nondecreasing se- quence of rational numbers—TRUE. For each irrational number α, let αn denote the decimal expansion of α to n places. This defines a nondecreasing sequence of rational numbers with limit α. 13.11. a) If 〈a〉 and 〈b〉 converge and lim an < lim bn, then there exists N ∈ N such that n ≥ N implies an < bn — TRUE. Let L = lim an and M = lim bn. Let ε = (M−L)/2. The definition of convergence implies that there exist N1 and N2 such that n ≥ N1 implies |an − L| < ε and n ≥ N2 implies |bn − M| < ε. Let N = max{N1, N2}. For n ≥ N , we have an < L + ε = M − ε < bn. b) If 〈a〉 and 〈b〉 converge and lim an ≤ lim bn, then there exists N ∈ N such that n ≥ N implies an ≤ bn — FALSE. If an = 2/n and bn = 1/n, then lim an = 0 = lim bn, so lim an ≤ lim bn, but an > bn for all n. 13.12. If S is a bounded set of real numbers, and xn → sup(S) and yn → inf(S), then lim xn + yn ∈ S—FALSE. Consider S = {1, 2}. If xn = 1 for all n, and yn = 2 for all n, then xn + yn converges to 3, which is not in S. The counterexample still works when we consider lim xn+yn2 , since xn+yn 2 = 3/2 /∈ S. 13.13. If x > 0 and x2 6= 2, then y = 12 (x + 2/x) satisfies y2 > 2. We show that y2 − 2 is a square. We have y2 − 2 = [ 12 (x + 2x )]2 − 2 = 14 (x2 + 4 + 4x2 )− 84 = 14 ( x2 − 4 + 4x2 ) = 14 (x − 2x )2 > 0. Note that x2 6= 2 implies that x − 2/x 6= 0. 13.14. To six places, the base 3 expansion of 1/10 is .002200. We have (73/729) > (1/10) > (72/729). The base 3 expansion of 72 is 2200, since 72 = 2 · 27 + 2 · 9 + 0 · 3 + 0 · 1. Dividing by 729 = 36 yields .002200. Since 185 Chapter 13: The Real Numbers 186 1/10 exceeds 72/729 by less than 1/729, the expansion of 1/10 agrees with this through the first six places. 13.15. Reciprocals of positive integers with one-digit expansions. In base k, we seek positive integer solutions to 1n = ik with 1 ≤ i < k. Rewriting this as n = k/ i , we get a solution for each divisor of k less than k. For k = 10, the fractions are 1/2, 1/5, 1/10. For k = 9, they are 1/3, 1/9. For k = 8, they are 1/2, 1/4, 1/8. 13.16. In base 26, the string B AD represents the decimal number 679. D(26)0 + A(26)1 + B(26)2 = 3 + 0 + 1(676) = 679. In base 26, the string .M M M M M M M M M M M M M · · · represents 12/25. Let x be the desired value. Note that the value of M is 12. From 26x = M.M M M M M M M M M M M · · ·, we have 26x = 12 + x , and thus x = 12/25. 13.17. When q is odd, the base q expansion of 1/2 consists of (q − 1)/2 in each position. See the more general result in the next solution. 13.18. When q ≡ 1 (mod 3), the base q expansion of 1/3 consists of (q −1)/3 in each position. In general, we prove that if q ≡ 1 (mod k), then the base q expansion of 1/k consists of (q − 1)/k in each position. The alternative expansion of 1 in base q consists of q − 1 in every position. Since k|(q − 1), the distributive law for series allows us to divide the sum of the series ∑ (q − 1)q−n by dividing each coefficient to obtain the series expansion 1/k = ∑ q−1k q−n. 13.19. If f is a bounded function on an interval I , then sup({− f (x): x ∈ I }) = − inf({ f (x): x ∈ I }). Let α = sup({− f (x): x ∈ I }), and S = { f (x): x ∈ I }. We have α ≥ − f (x) and hence −α ≤ f (x) for all x ∈ I , so −α is a lower bound for S. On the other hand, Prop 13.15 yields a sequence 〈x〉 of numbers in I such that − f (xn) → α. Thus f (xn) → −α. We now apply the analogue of Prop 13.15 for infimum. Since −α is a lower bound for S and − f (xn) defines a sequence of elements of S converging to −α, we conclude that −α = inf(S). 13.20. Sequence converging to infimum or to supremum. a) S = {x ∈ R: 0 ≤ x < 1}. We have xn = 1 − 1/(n + 1) → 1 = sup(S) and yn = 1/(n + 1) → 0 = inf(S). b) S = { 2+(−1)nn : n ∈ N}. The set S consists of the terms of a sequence that begins 1, 3/2, 1/3, 3/4, . . .. The constant sequence converges to the supremum: xn = 3/2 = sup(S). A monotone sequence converging to the infimum is given by yn = 3/(2n) → 0 = inf(S). 13.21. The Least Upper Bound Property holds for an ordered field F if and only if the Greatest Lower Bound Property holds for F. Given a set S, let −S denote {x : −x ∈ S}. Upper bounds on −S are the negatives of lower bounds on S, and lower bounds on −S are the negatives of upper bounds on S. The LUB Property implies for nonempty S that −S has a least upper bound α, which implies that S has a greatest lower bound −α, and the GLB Property follows. Conversely, the GLB Property implies for nonempty S that −S has a greatest lower bound α, which implies that S has a least upper bound −α, and the LUB Property follows. 13.22. Determination of sup(S) and inf(S). a) S = {x : x2 < 5x}. Rewrite S as S = {x : x(x − 5) < 0}. Thus x ∈ S if and only if x and x − 5 have opposite signs. This requires x > 0 and x < 5, and that suffices, so S is the open interval (0, 5). This set is bounded (by 0 and 5), and sup(S) = 5 and inf(S) = 0. b) S = {x : 2x2 < x3 + x}. Rewrite S as S = {x : x(x − 1)2 > 0}. The condition holds if and only if x > 0 and x 6= 1. This set is unbounded, but its infimum is 0. c) S = {x : 4x2 > x3+x}. The inequality is equivalent to x(x2−4x +1) < 0. The zeros of the quadratic factor are at x = 2 ± √ 3. Thus S = (−∞, 0) ∪ (2 − √ 3, 2 + √ 3). The set has no lower bound, but sup(S) = 2 + √ 3. 13.23. If A, B ⊂ R have upper bounds and C = {x + y ∈ R: x ∈ A, y ∈ B}, then C is bounded and sup C = sup A + sup B. Let α = sup A and β = sup B. We prove first that α + β is an upper bound for C . For each z ∈ C , the definition of C implies that z = x + y for some x ∈ A and y ∈ B. By the definition of upper bound, x ≤ α and y ≤ β. Hence z = x + y ≤ α + β, and α + β is an upper bound for C . To prove that α + β is the least upper bound, consider q such that q < α +β. Thus q = α +β − ε for some ε > 0. Since α = sup A, the number α−ε/2 is not an upper bound for A, and there exists x ∈ A with x > α−ε/2. Similarly, there exists y ∈ B with y > β − ε/2. This constructs z ∈ C such that z = x + y > α + β − ε = q. Hence q is not an upper bound for C . Alternative proof: Instead of showing directly that C has no smaller upper bound, it also suffices to show that C contains the elements of a sequence converging to α + β. This can be obtained by taking a sequence 〈x〉 in A converging to α and a sequence 〈y〉 in B converging to β. The sum consists of elements of C : zn = xn + yn → α + β. Comment: Since α + β may not lie in C , one cannot prove that α + β is the least upper bound for C without using the properties of supremum. For example, if A = {x ∈ R: 0 < x < 1} and B = {x ∈ R: 2 < x < 3}, then C = {x ∈ R: 2 < x < 4}; none of these sets contains its supremum. 187 Chapter 13: The Real Numbers 188 13.24. When f, g: R → R are bounded functions such that f (x) ≤ g(x) for all x , with images F, G respectively, the following possibilities may occur (pictures omitted): a) sup(F) < inf(G). Let f (x) = 0 and g(x) = 1 for all x . b) sup(F) = inf(G). Let f (x) = g(x) = 0 for all x . c) sup(F) > inf(G). Let f (x) = |x | for |x | ≤ 1 and f (x) = 1 for |x | > 1. Let g(x) = |x | for |x | ≤ 2 and g(x) = 2 for |x | > 2. Now sup( f (x)) = 1 and inf(g(x)) = 0. 13.25. lim √ 1 + n−1 = 1. Given ε > 0, let N = d1/εe. Note that √ 1 + n−1 < 1 + n−1 when n > 0. For n ≥ N , we have ∣∣∣√1 + n−1 − 1∣∣∣ < ∣∣1 + n−1 − 1∣∣ = n−1 ≤ N−1 ≤ ε. Thus √ 1 + n−1 → 1, by the definition of limit. Comment: Let an = √ 1 + n−1. A less efficient approach first uses MCT to prove that 〈a〉 converges. Letting L = lim an, we have a2n → L2. Proving a2n → 1 directly yields L = ±1, and positivity of an then yields L = 1. 13.26. If lim an = 1, then lim[(1 + an)−1] = 12 . Consider ε > 0. Because lim an = 1, the definition of limit tells us that there exists N1 ∈ N such that n ≥ N1 implies |an − 1| < ε. Also |1 + an| = |1 + 1 − 1 + an| ≤ 2 + |an − 1| < 2 + ε. Let N = N1. Now n ≥ N implies∣∣∣∣ 11 + an − 1 2 ∣∣∣∣ = ∣∣∣∣2 − 1 − an2(1 + an) ∣∣∣∣ = |1 − an|2(1 + an) < ε 2(2 + ε) < ε. Thus lim[(1 + an)−1 = 1/2, by the definition of limit. 13.27. If an = √ n2 + n − n, then lim an = 12 . We multiply and divide an by√ n2 + n + n, simplify the result, and use Exercises 13.25–13.26. Thus an = √ n2 + n − n = ( √ n2 + n − n)( √ n2 + n + n) ( √ n2 + n + n) = n 2 + n − n2√ n2 + n + n = 1√ 1 + 1/n + 1 → 1 2 . 13.28. If xn → 0 and |yn| ≤ 1 for n ∈ N, then lim(xn yn) = 0. One cannot argue that lim(xn yn) = lim(xn) lim(yn) = 0 · lim(yn) = 0, since lim(yn) need not exist. A correct proof uses |yn| ≤ 1 to argue that |xn yn| = |xn| |yn| ≤ |xn|. Given ε > 0, the convergence of 〈x〉 yields N ∈ N such that n ≥ N implies |xn| < ε. By our first computation, |xn yn| ≤ |xn| < ε for such n, and thus lim xn yn = 0. 13.29. The limit of the sequence 〈x〉 defined by xn = (1 + n)/(1 + 2n) is 1/2. Since the denominator exceeds the numerator and both are positive, we have 0 < xn < 1 for all n ∈ N. We also compute xn+1 − xn = n + 2 2n + 3 − n + 1 2n + 1 = (2n + 1)(n + 2) − (2n + 3)(n + 1) (2n + 3)(2n + 1) = −1 (2n + 3)(2n + 1) < 0. Since 〈x〉 is a decreasing sequence bounded below, the Monotone Conver- gence Theorem implies that limn→∞ xn exists. To prove that limn→∞ xn = 1/2, we compute xn −1/2 = n+12n+1 − 12 = 14n+2 . Given ε > 0, choose N ∈ N such that N > 4/ε. Now n > N implies that |xn − 1/2| = 14n+2 < ε. Since this holds for each ε > 0, we have xn → 1/2, by the definition of limit. 13.30. The sequence 〈x〉 defined by xn = 1n+1 + 1n+2 +· · ·+ 12n converges. By the Monotone Convergence Theorem, it suffices to prove that 〈x〉 is increasing and bounded above by 1. For the first statement xn+1−xn = n+1∑ i=1 1 n + 1 + i − n∑ i=1 1 n + i = 1 2n + 1+ 1 2n + 2− 1 n + 1 = 1 2n + 1− 1 2n + 2 > 0. For the second statement, xn = ∑n i=1 1 n+i < ∑n i=1 1 n+1 = nn+1 ≤ 1. 13.31. xn = (1 + (1/n)n defines a bounded monotone sequence. Let rn = xn+1/xn. We show that rn > 1 to prove that 〈x〉 is increasing. Writing xn as ( n+1n ) n, we have rn = [ n + 2 n + 1 /n + 1 n ]n n + 2 n + 1 = ( n2 + 2n n2 + 2n + 1 )n n + 2 n + 1 = ( 1 − 1 (n + 1)2 )n n + 2 n + 1 . Since (1 − a)n ≥ 1 − na (Corollary 3.20) when α > 0, we have rn ≥ ( 1 − n (1 + n)2 ) n + 2 n + 1 = n2 + n + 1 n2 + 2n + 1 n + 2 n + 1 = n3 + 3n2 + 3n + 2 n3 + 3n2 + 3n + 1 > 1. To show that 〈x〉 is bounded, we write xn = (1 + 1/n)n = ∑n k=0 (n k ) n−k . Since ∏k−1 i=0 (n − i) < nk , we obtain xn ≤ ∑n k=0 1/k!. Thus it suffices to show that this sum is bounded. We have 1/k! < 1/2k for k ≥ 4. Therefore,∑n k=0 1 k! = 1 + 1 + 12 + 16 + ∑n k=4 1 k! < 8 3 + ∑∞ k=4 1/2 k = 83 + 18 = 6724 . 13.32. The Nested Interval Property. A nested sequence of closed intervals, with In of length dn, satisfies In+1 ⊆ In for all n and dn → 0. The Nested 189 Chapter 13: The Real Numbers 190 Interval Property states that for such a sequence, there is exactly one point that belongs to each In. Let In = [an, bn]. a) The Completeness Axiom implies the Nested Interval Property. For all n, we have an ≤ an+1 ≤ bn ≤ b1 and bn ≥ bn+1 ≥ an ≥ a1. Thus both 〈a〉 and 〈b〉 are bounded monotone sequences. By the Montone Convergence Theorem, 〈a〉 increases to its supremum, A, and 〈b〉 decreases to its infi- mum, B. Since bn − an = dn → 0, we obtain lim an = lim bn, so A = B. This implies that A belongs to every In. b) The Nested Interval Property implies the Completeness Axiom. As- sume that the Nested Interval Property holds, and let S be a nonempty set with an upper bound b1. Choose x1 ∈ S. We construct a sequence of intervals {[xn, bn]: n ∈ N. Having constructed [xn, bn], consider the midpoint zn = (xn + bn)/2 of the interval. If zn is an upper bound for S, then let bn+1 = zn and xn+1 = xn. Otherwise, choose xn+1 as an element of S larger than zn, and let bn+1 = bn. The Nested Interval Property implies that 2−n → 0. Since 0 ≤ bn − xn ≤ (b1 − x1)/2n−1, also dn = xn −bn → 0. By the Nested Interval Property, there is exactly one point α belonging to each In. Since xn → α, S contains a sequence of elements converging to α, and there is no upper bound less than α. Since bn → α, no element of S is larger than α, because this would contradict that every bn is an upper bound. Hence α is the least upper bound for S, and the supremum indeed exists. 13.33. The k-ary expansion of 1/2. When k is even, with k = 2n, the expan- sion is .n. When k is odd, with k = 2n+1, the expansion 1 = .(2n)(2n)(2n) · · · yields (1/2) = .nnn · · ·. 13.34. There is a rational number between any two irrational real numbers and an irrational number between any two rational numbers. The rational numbers expressible as fractions whose denominators are powers of 10 are the numbers with terminating decimal expansions. Let a, b be the canonical decimal expansions of two irrational numbers α, β with α < β. Since they are distinct real numbers, there is a first digit where they differ. Truncate the expansion of β at that digit to obtain the expansion of a rational number γ . Since β is irrational, its decimal expansion cannot terminate, and thus γ < β. Since α is irrational, its decimal expansion cannot end with all 9’s. Since its expansion is less than that of γ in the first place where they differ, we thus have α < γ . Now suppose that a, b are distinct rational numbers with a < b. Proof 1 (by irrationality of √ 2). Let c = a + ( √ 2/2)(b − a). Since 0 < √ 2/2 < 1, the number c is between a and b. If c is rational, then closure of operations on rational numbers implies that 2(c − a)/(b − a) is rational, but this equals √ 2. Proof 2 (by uncountability of the interval (0, 1)). Map the interval (a, b) to the interval (0, 1) by f (x) = (x −a)/(b−a). This function is a bijec- tion, and thus the intervals have the same cardinality. Since the interval (0, 1) is uncountable and the set of rationals is countable, there must be a number in the interval (a, b) that is not rational. Proof 3 (by k-ary expansions). Express a and b as fractions via a = p/q and b = r/s. Let k be the least common multiple of q and s. Now a and b are expressible as fractions with denominator k. Thus they have finite k- ary expansions; indeed, the expansions have only one nonzero term in the fractional part. Form the k-ary expansion of c by appending to the k-ary expansion of a the k-ary expansion of any irrational number. 13.35. A real number has more than one k-ary expansion if and only if it is expressible as a fraction with a denominator that is a power of k. Suppose that α = m/kn for some positive integer m. We may assume that m < kn (otherwise, we subtract the integer part) and that m is not a multiple of k (otherwise, we cancel a factor of k to obtain such an expression with a smaller power of k). Now α has the terminating k-ary expansion a1a2 · · · an with an 6= 0. Also α has the nonterminating k-ary expansion 〈c〉, where ci = ai for i < n, cn = an − 1, and ci = k − 1 for i > n. For the converse, suppose that α has k-ary expansions a and a ′. A k-ary expansion of α yields a bounded increasing sequence with limit α. If the sequence of digits is 〈a〉, then the sequence 〈b〉 converging to α is defined by bn = ∑n i=1 ai/ki . Similarly, we have b′n → α, where b′n = ∑n i=1 a ′ i/ki . If a and a′ differ, let n be the first position where they differ. We may assume that an < a′n. We have bn ≤ b′n − 1/kn. The contribution from all remaining terms of the expansion a is at most 1/kn, with equality achieved only if all the remaining positions in a are k −1. Hence α ≤ bn +1/kn ≤ b′n ≤ α. Since equality holds throughout, the contribution from all remaining positions in the expansion a ′ must be 0. This requires that every remaining position in b′ is 0. Hence b′n = α is a rational number expressible with denominator kn, and 〈a〉 is its alternative nonterminating expansion. 13.36. a) Long division of a by b (in base 10) yields the decimal expan- sion of a/b. Let α = a/b, with b > a. The decimal expansions is .c1 + .0c2 + .00c3 + · · ·. For k-ary expansion in general, we want a = b(c1k−1 + c2k−2 + c3k−3 + · · ·. In the long division process, we find one digit at a time, always computing a remainder. In the first step, we append a 0 to the k-ary representation of a, multiplying it by k. We then apply the Di- vision Algorithm to write ak = c1b + r1. Thus r1 = ak − c1b, where c1 is the first digit in the k-ary expansion, and r1 is the remainder. Long division proceeds using r1 instead of a; the expansion of this fol- lows c1. We add a zero to the end of r1 (multiplying it by k) and use the Divi- 191 Chapter 13: The Real Numbers 192 sion Algorithm to write r1k = c2b + r2. In general, we generate cj and r j by r j−1k = cj b+r j . By induction on j , this yields a/b = ( ∑ j i=1 ci k−i )+r j/(bk− j ), and thus this process produces a k-ary expansion. The proof of the induc- tion step is a b = ( j−1∑ i=1 ci k−i ) + r j−1 bk−( j−1) = ( j−1∑ i=1 ci k−i ) + cj b + r j bk− j = ( j∑ i=1 ci k−i ) +