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
) +