REAL ANALYSIS
REAL ANALYSIS FRANK MORGAN
AmmiucArr MATHEMATICAL SOCIETY
Providence, Rhode Island
2000 Mathematics Subject Classzficatzon. Primary 26XX.
Front cover: The cover illustrates how continuous functions can converge nonuniformly to a discontinuous function. It is based on Figure 17.1, page 76. The balls in the background illustrate an open cover, as in the definition of the important concept of compactness (Chapter 9, page 41). , Back cover: The author, in the Math Library outside his office at Williams College. Photo by Cesar Silva. Cover design by Erin Murphy of the American Mathematical Society, on a suggestion by Ed Burger.
For additional information and updates on this book, visit
www.ams.org/bookpages/real
Library of Congress CataloginginPublication Data Morgan, Frank. Real analysis / Frank Morgan. p. cm. Includes index. ISBN 0821836706 (alk. paper) 1. Mathematical analysis. I. Title.
QA300.M714 2005 515dc22
2005041221
Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy a chapter for use in teaching or research. Permission is granted to quote brief passages from this publication in reviews, provided the customary acknowledgment of the source is given. Republication, systematic copying, or multiple reproduction of any material in this publication is permitted only under license from the American Mathematical Society. Requests for such permission should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, Rhode Island 029042294, USA. Requests can also be made by email to reprintpermissionmams. org. © 2005 by the author. All rights reserved. Printed in the United States of America.
Q The paper used in this book is acidfree and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at http://www.ams.org/ 100908070605 10987654321
Contents
Preface
vii
Part I. Real Numbers and Limits Chapter
1.
Numbers and Logic
Chapter 2. Infinity Chapter
3.
Sequences
Chapter 4. Functions and Limits
3 9 13
21
Part H. Topology Chapter 5.
Open and Closed Sets
27
Chapter 6.
Continuous Functions
33
Chapter 7.
Composition of Functions
35
Chapter 8. Subsequences
37
Chapter 9.
41
Compactness
Chapter 10. Existence of Maximum
45
Chapter 11.
Uniform Continuity
47
Chapter 12.
Connected Sets and the Intermediate Value Theorem
49
Chapter 13.
The Cantor Set and Fractals
53
v
Contents
vi
Part III. Calculus Chapter 14.
The Derivative and the Mean Value Theorem
61
Chapter 15.
The Riemann Integral
65
Chapter 16.
The Fundamental Theorem of Calculus
71
Chapter 17.
Sequences of Functions
75
Chapter 18.
The Lebesgue Theory.
81
Chapter 19.
Infinite Series E a7
85
Chapter 20.
Absolute Convergence
89
Chapter 21.
Power Series
93
Chapter 22.
Fourier Series
99
Chapter 23.
Strings and Springs
105
Chapter 24.
Convergence of Fourier Series
109
Chapter 25.
The Exponential Function
111
Chapter 26.
Volumes of nBalls and the Gamma Function
115
Part IV. Metric Spaces Chapter 27.
Metric Spaces
121
Chapter 28.
Analysis on Metric Spaces
125
Chapter 29.
Compactness in Metric Spaces
129
Chapter 30.
Ascoli's Theorem
133
Partial Solutions to Exercises
137
Greek Letters
147
Index
149
Preface
Our lives and the universe barely work, but that's OK; it's amazing and great that they work at all. I think it has something to do with math, and especially real analysis, the theory behind calculus, which barely works. Did
you know that there are functions that are not the integral of their derivatives, and that a function can be increasing and have a negative derivative? But if you're a little careful you can get calculus to work. You'll see.
The theory is hard, subtle. After Newton and Leibniz invented the calculus in the late 1600s, it took puzzled mathematicians two hundred years,
until the latter 1800s, to get the theory straight. The powerful modern approach using open and closed sets came only in the 1900s. Like many others, I found real analysis the hardest of the math major requirements; it took me half the semester to catch on. So don't worry: just keep at it, be patient, and have fun. This text is designed for students. It presents the theoretical intellectual breakthroughs which made calculus rigorous, but always with the student in mind. If a shortcut or some more advanced comments without proof provide better illumination, we take the shortcut and make the comments. The result is a complete course on real analysis that fits comfortably in one semester.
vii
Preface
This text developed with my onesemester undergraduate analysis course at Williams College. I would like to thank my colleagues and students, especially Ed Burger, Tom Garrity, Kris Tapp, and Nasser AlSabah `05, and my editors Ed Dunne and Tom Costa. Frank Morgan
Department of
Mathematics: and Statistics
Williams College Williamstown, Massachusetts
www.williams.edu/Mathematics/fmorgan
[email protected]
Part I
Real Numbers and Limits
Chapter 1
Numbers and Logic
1.1. Numbers. Calculus and real analysis begin with numbers: The natural numbers
N = {1, 2, 3.... I. The integers
Z = {... , 3, 2, 1, 0, 1, 2, 3, ... } (Z stands for the German word Zahl for number). The rationals Q _ {p/q in lowest terms: p E Z, q E N} _ {repeating or terminating decimals}. (Q stands for quotients). The reals I[8 = {all decimals}
with the understanding that .999 . = 1, etc. Reals which are not rational are called irrational. Thus the set of irrationals is the complement of the set of rationals, and we write
{irrationals} _ Q6 = IR  Q.
1.2. Intervals in R. For a < b, define intervals
[a,b]={xEIR:a<x
ae
and so on. 3
1. Numbers and Logic
4
1.3. R. We will consider the plane 1l 2 of pairs (x, y) of real numbers and more generally ndimensional space IW of ntuples (x1, X 2 , . , xn) of real numbers. In these spaces, by rationals we'll mean ntuples of rationals. There are fancier number systems, such as the complex numbers (which will make a solo appearance in. Chapter 25) and the much fancier "quaternions" (which maybe you'll see in some future course).
1.4. Distance. The (Euclidean) distance between real numbers x and y is given by l y  xI. More generally, the distance between two vectors (xi), (yi) in I[8n is given by )2)1/2.
ly  xI = ((yl  x1)2 + (y2  x2)2 +... + (yn  n
Distance satisfies the triangle inequality, which says that the length of one side of a triangle with vertices x, y, z is less than or equal to the sum of the lengths of the other two sides:
Ix  zI < xyl+yzl. The Ancient Greeks discovered with dismay that not every real is rational, with the following example.
1.5. Proposition. v/ is irrational. Proof. Suppose that
equals p/q, in lowest terms, so that p and q have no common factors. Since 2 = p2/q2 2q2 = p2.
Thus p must be even: p = 2p'. Hence 2q2 = 4P 2,
q2 =
2P/2,
which means that q must be even, a contradiction of lowest terms, since p and q both have 2 as a factor. There is an easier example:
1.6. Proposition. log10 5 is irrational. Proof. Suppose that log10 5 equals p/q, which means that 10P/q = 5 or 10P = 59.
But 10P ends in a 0, while 5q ends in a 5, contradiction.
1.8. Implication
5
Probably the easiest way to give an example of an irrational is just to write down a nonrepeating, nonterminating decimal like .01 001 0001, 00001000001 ....
although that's no number you've ever heard of.
1.7. Logic and ambiguous English. English is a treacherous language, and we have to be very careful. For example, there are two meanings of "or" in English:
(1) A crazy "exclusive" or, meaning "one or the other, but not both." I had lunch in the French Quarter, and they offered me a choice of blackeyed peas or greens, but they wouldn't give me both. (2) The sensible, mathematical "inclusive" or, meaning "one or the other or both." You can work on your real analysis homework day or night.
1.8. Implication. There are many ways to say that one statement A implies another statement B. The following all mean exactly the same thing:
If A, then B. A implies B, written A = B.
Aonly ifB. B if A, written B = A. Here are some examples of such equivalent statements:
If a number n is divisible by four, then it is even. n divisible by four implies n even. n is divisible by four only if it is even (never if it is odd). n is even if divisible by four. Such an implication is true if B is true or if A is false (in which case we say that the implication is "vacuously true"). For example, "If 5 is even, then 15 is prime" is vacuously true. This is pure logic and has nothing to do with causation. (Indeed, from the point of view of causation, if 5 were even, then 15, as a multiple of 5, would be even and hence not prime.) Such an implication is false only if A is true and B is false. Such an implication is logically equivalent to its contrapositive: not B implies not A. This is the basis for proof by contradiction. We assume the negation of the B we axe trying to prove, and arrive at a contradiction of the hypothesis A.
1. Numbers and Logic
6
Such an implication is logically distinct from its converse: B implies A.
If x is a Williams student, then x is a human being. True. If x is not a human being, then x is not a Wilhams student. Contrapositive, true. If x is a human being, then x is a Williams student. Converse, false in this case. If it happens that the implication and its converse are both true, i.e., if A = B and B = A, then we say that A and B are logically equivalent or
that A if and only if B
(A a B).
Example. Let S C Z. Consider the statements A: All elements of S are even. (For all x c S, x is even.) B: Some element of S is even. (There exists x E S, such that x is even.)
Does B A? Certainly not in general. Does A = B? Not in general because if S is the empty set 0, then A is true (vacuously), while B is false!
1.9. Abbreviations. Understand but avoid abbreviations such as
A and V or  not
3 exists V for all.
1.10. Sets. A set A is completely determined by the elements it contains:
A={x:xEA}. If all elements of A are elements of B, we say that A is a subset of B (A C B) or that B contains A (B D A). You have to be careful, because the word "contains" is used both for subsets and for elements, as determined by context. Proper containment (A C B and A # B) is denoted by A B.
Some texts denote ordinary containment by A C_ B to remind you that equality is allowed. We say that sets A, B intersect if AnB 0. The symbol n°°_1 A,, denotes the set of elements common to all of the sets A1, A2, A3....
xE nAn if and only if xEA,,,forall n. n=1
We define the complement of a set
AC={x:x0A}, and the difference of two sets
AB={xEA: x0B}.
Exercises 1
1.11. Functions. A function f : A p B takes an input x from a domain A and produces an output f (x) in some range B. For most of this book we'll assume that A C R and B C R. The set of all outputs
f(A)={f(x):xEA}CB is called the image of f . If the image is the whole range, then f is called onto
or surjective. If f maps distinct points to distinct values, then f is called injective or onetoone (11). If f is both injective and surjective, then f is called bijective or a 11 correspondence and f has an inverse function f1: B ' A. If X is a subset of A, then f (X) is the corresponding set of values:
f(X)={f(x):xEX}. Whether or not f 1 exists as a function on points, for a set Y C B, you can always take the inverse image
f 1Y = IX: f (x) E Y}. For example, if f (x) = sin x, then f1{0} = {0, ±ir, ±27r, ±37r.... }.
Exercises 1 1. Is the statement If x E Q, then x 2 E N true or false for the following values of x? Why?
a. x = 1/2.
b. x=2. c. x = v"2.
d. x= 42. 2. For which real values of x is the converse of the statement of Exercise 1 true? 3. Which of the following statements are true of the real numbers. a. For all x there exists a y such that y > x2. b. There exists a y such that for all x, y > x2. c. There exists a y such that for all x, y < x2. d. Va, b, c, Ix such that ax2 + bx + c = 0.
1. Numbers and Logic
8
4. Which of the following statements are true for all real numbers x. a. If x E (1, 2], then x2 E (1, 4]. b. If x E (1, 2], then x2 E (1, 4]. c. If x E (1, 2], then x2 E (1, 4].
5. a. What is the length of a diagonal of a unit square (with vertices (0, 0), (0,1), (1, 0), (1,1))? b. What is the length of a long diagonal of a unit cube? c. What is the length of the longest diagonal of a unit hypercube in ]R4? d. What is the length of the longest diagonal of a unit hypercube in R? 6. Prove that 4r2 is irrational.
7. Prove that log1015 is irrational. 8. Find infinitely many nonempty sets of natural numbers N3S13S23S33...
such that n°°_1 Sn = 0. 9. Identify each of the following functions f from JR to JR as injective (11), surjective (onto), neither, or both (bijective).
a. f (x) _ x. b. f(x) = x2. c. f (x) = sin x. d. f(x) = ex. e. f (x) = x3 + x2. 10. Give a counterexample to one of the following four formulas for images and inverse images of sets (the other three are true): f (X1 U X2) = f (X1) U f (X2), f1(y1 UY2)= f'(y1) U f1(Y2),
f(X1 nX2) = f(XI) n f(X2), f1(Yi nY2) = f1(Yi) n f1(Y2).
Chapter 2
Infinity
Although some infinite sets contain other infinite sets, there is a good intuition that in some sense all infinite sets are the same size. For example, although the even natural numbers are a proper subset of all the natural numbers, the two sets can be paired up by matching 2n with n: 2,
4,
6,
1,
2,
3,
8, 4,
10, 5,
Although many infinite sets are the same size as the natural numbers, it turns out that some really are much bigger in a mathematically precise sense.
2.1. Definition. A set is called countable if it is finite or it can be put in 11 correspondence with the natural numbers, i.e., if its elements can be listed. Examples of countable sets include the set 3N of positive multiples of 3 and the set 7G of all integers (including the negative ones):
N 3N
7L
1
3
0
2
6
1
4
12
2
5
15 2
3
9 1
It is clear that a subset of a countable set is countable because you can use the order of the list of. the set to list the subset. It turns out that even the apparently larger set of all rationals is still countable.
2.2. Proposition. The set Q of nationals is countable. 9
2. Infinity
10
Proof. It suffices to show that the positive rationals are countable; then the lists of positive and negative rationals and zero can be interspersed on a single list as for 7L above. Arrange all ratios in an infinite table like this: 1/1
1/2
1/3
1/4
1/5
...
2/1
2/2
2/3
2/4
2/5
...
3/1
3/2
3/3
3/4
3/5
...
4/1
4/2
4/3 4/4 4/5
...
5/1
5/2
5/3
5/4
...
5/5
Now starting at the upper lefthand corner, move through the northeasterly diagonals of this table, starting with 1/1, then 2/1 and 1/2, then 3/1, 2/2, and 1/3, and so on.
/ //
// // /
1/1
1/2
1/3
1/4
1/5
...
2/1
2/2
2/3
2/4
2/5
...
3/1
3/2
3/3 /3
3/4
3/5
...
4 /1
4/2
4/3
4/4
4/5
...
5/2
5/3
5/4
5/5
...
X /5/1
When you hit a repetition (like 2/2 = 1/1), skip it. This process puts the rationals on a list:
1/1, 2/1, 1/2, 3/1, 1/3, 4/1, 3/2, 2/3, 1/4, 5/1, 1/5, .... Therefore, the rationals are countable.
2.3. Proposition. The Cartesian product of two countable sets C1 X C2 = {(cl, c2) : c1 E C1 and C2 E C2}
is countable. A countable union of countable sets is countable.
(A "countable union" means "the union of countably many.")
Proof. The proofs (Exercises 4 and 5) are very similar to the proof of Proposition 2.2.
2.5. Uncountable infinities
11
By now you may be thinking that all sets are countable. Georg Cantor showed in the late 1800s that the reals R are not countable. This sounds very hard to prove. How could you show that there is no 11 correspondence between R and N? The proof is amazing.
2.4. Proposition. The set I[8 of reals is uncountable.
Proof. We will assume that Proposition 2.4 is false and derive a contradiction. In particular we will assume that the reals can be listed, and then exhibit a real number missing from the list, the desired contradiction. Since the argument applies to any list, that will complete the proof. Suppose that the reals were countable. Then the positive reals would be countable and could be listed, for example: 1.
2. 3.
4. 5. 6.
657.853260... 2.313333.. . 3.141592.. . .000207... 49.494949.. . .873257...
To obtain a contradiction, we just have to show that some real a (Greek letter alpha, see Table of Greek letters on page 147) has to be missing from this list. We'll construct such an a by making its first decimal place different
from the first decimal place of the first number on the list, by making its second decimal place different from the second decimal place of the second number on the list, and in general by making its nth decimal place different from the nth decimal place of the nth number on the list. To be specific, we'll make the nth decimal place 1, unless the nth decimal place of the nth number on the list is 1, in which case we'll make it 2. For our example, a = .122111.. .
As promised, we have found a number a missing from the list, because it differs from the nth number on the list in the nth decimal place. Since this argument applies to any list,.the reals cannot be listed.
2.5. Uncountable infinities. More generally, one can say that two infinite sets have the same size if they can be put in 11 correspondence. It turns out that there is an infinite hierarchy of infinitely many different size
infinities. What's bigger than I[8? Not IR2 or R; they turn out to be the same infinity as R. One bigger infinity is the set of all functions from IR to R. Another is the set of all subsets of R. Indeed, the set of all subsets of
2. Infinity
12
any set X is always bigger than X, so this is one way to keep going. The proof, which you could find on the internet, is short but tricky.
.
Exercises 2
1. Prove whether or not the set S is countable. a. S = {irrationals}. b. S = {terminating decimals}. c. S = [0, .001).
d. S=QxQ. e. S=IRxZ. 2. Prove that the intersection of two countable sets is countable. Hint: There is a very short answer. 3. Prove whether or not the intersection and union of two uncountable sets must be uncountable.
4. Prove that the Cartesian product of two countable sets
AxB={(a,b): aEAandbeB)} is countable. Hint: Imitate the proof of Proposition 2.2.
5. Prove that a countable union of countable sets is countable. Hint: Imitate the proof of Proposition 2.2.
Chapter 3
Sequences
Many would say that the hardest theoretical concept in analysis is limit. What does it mean for a sequence of numbers to converge to some limit? There just is no easy answer. Oh, we'll try to find one, but there will always be some sequences that a simple answer cannot handle. In the end, we'll be forced to do something a little complicated, and to make it worse, we'll follow tradition and use the Greek letter e (epsilon).
3.1. Discussion. The sequence (1)
1, 1/2, 1/3, 1/4, 1/5, ...
converges to 0. The sequence of digits of 7r (2)
3, 1, 4, 1, 5, 9, 2, ...
does not converge to anything; it just bounces around. The sequence (3)
1, 2, 3, 4, 5, ...
diverges to infinity. Those sequences are easy. But sometimes it is hard to decide. What about the sequence (4)
1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, ... ?
Common agreement is that it does not converge, but to decide we really need a good definition of "converge." How about this:
First attempt at a definition. A sequence a1, a2, a3, a4, a5, ... converges to, say, 0 if the terms get closer and closer to 0. 13
3. Sequences
14
According to this definition, (4) does not converge. Good, but what about the following sequences: (5)
8, 1, 4, 1/2, 2, 1/4, 1, 1/8, 1/2, 1/16, 1/4, 1/32, ...
(6)
12, 14, 18,116 ,132,...
1
1
1
1
1
The terms of (5) are not getting "closer and closer to 0," but the sequence does converge to 0. The terms of (6) are getting "closer and closer to 0," but the sequence does not converge to 0. (We will see that this sequence converges to 1.)
We need a more precise definition. The terms need to get and stay arbitrarily close to zero or whatever limit value L, eventually. "Arbitrarily close" means as close as anyone could prescribe, i.e., given any positive error,
the terms eventually have to stay within that tolerance of error. Since the letter e is already taken by 2.71828... , mathematicians usually use the Greek letter epsilon e for the given error. And what do we mean by "eventually"? We mean that given the tolerance of error e, we can come up with a big number N, such that all the terms after aN are within e of the limit value L. That is, given e > 0, we can come up with an N, such that whenever n > N, every subsequent an is within e of L. Now that's a good definition, and here it is written out concisely:
3.2. Definition of convergence. A sequence an converges to a limit L
an >L if given e > 0, there is some N, such that whenever n > N, Iany  LI < e.
Otherwise we say that the sequence diverges.
Notice that order in the definition is very important. First comes the sequence an and the proposed limit L. Second comes the tolerance of error e, which is allowed to depend on the sequence. Third comes the N, which is allowed to depend on E. A sequence which diverges might diverge to infinity like (3) or diverge by oscillation like (2). Some other things in the definition do not matter, such as whether the inequalities are strict or not. For example, if you knew only that you could get Ian  L I less than or equal to any given e, you could take a new e' = e/2 and get
Ian  LI <e'<E,
3.5. Proposition
15
strictly less than e. Similarly, it suffices to get l an  LI less than 3e, because
you can take e' = e/3 and get Ian  Ll < 36 = E.
So the final E could be replaced by any constant times e or anything that's small when E is small.
3.3. Example of convergence. Prove that an = 1/n2 converges to 0. First, let's think it through. Given e > 0, we have to see how big n has to be to guarantee that an = 1/n2 is within E of 0:
11/n20I <e. This will hold if 1/n2 < E, that is, if n > 1/\. So we can just take N to be 1//, and we'll have the following proof: Given E > 0, let N = 11 \. Then whenever n > N,
IanLI=11/n201=1/n2<1/N2=E. Notice how we had to work backwards to come up with the proof.
3.4. Bounded. A sequence an is bounded if there is a number M such that for all n, lan < M.
For example, the sequence an = siren is bounded by 1 (and by any M > 1). The sequence an = (1)n/n2 is bounded by 1. The sequence an = n2 is not bounded.
3.5. Proposition. Suppose that the sequence an converges. Then (1) the limit is unique; (2) the sequence is bounded.
Before starting the proof of (1), let's think about why a sequence cannot
have two limits, 0 and 1/4 for example. It's easy for the terms an to get within 1 of both, or to get within 1/2 of both, but no better than within e = 1/8 of both (see Figure 3.1). Similarly, if a sequence had any two different limits Ll < L2, you should get a contradiction when E = (1/2)(L2  Ll). I think I'm ready to write the proof.

1/8
1/8 1
0
1
I 1/4
Figure 3.1. A number cannot be closer than distance 1/8 to both 0 and 1/4.
3. Sequences
16
Proof of (1). Suppose that a sequence an converges to two different limits L1 < L2. Let e = (1/2)(L2  Li). By the definition of convergence, there is some N1 such that whenever n > N1, Ian  Ll < E. Similarly there is some N2 such that whenever n > N2, Ian  L21 < e. Choose n greater than N1 and N2. Then
L2Ll < IanLIB+IL2and <e+E=2E=L2L1, a contradiction. The proof of (2) is easier. After a while the sequence is close to its limit L, and once an is within say 1 of L, ian < I L + 1. There are only finitely many other terms to worry about, and of course any finite set is bounded (by its largest element). I'm ready to write the proof:
Proof of (2). Let an be a sequence converging to L. Choose N such that whenever n > N, Ian  L < 1, so that I an I < I L I + 1. Let M = max{ILI + 1, lanl, with n < N}.
Then an < M.if n< N, an < M. If n > N, an < ILI + 1 <M. So always 3.6. Proposition. Suppose real sequences an, bn converge to a and b: >
bn + b.
Then (1) can * ca,
(2) an+bn * a +b, (3) anbn > ab,
(4) an/bn  a/b, assuming every bn and b is a nonzero real number. PREPARATION FOR PROOF. We'll prove (1) and (4), and leave (2) and (3)
as Exercises 13 and 14. As usual, it pays to build the proof backwards. At the end of the proof of (1), we'll need to estimate Ican  cal = IclIan  al < E,
which will hold if Ian  al < e/IcI (unless c = 0). I see how to do the proof.
Proof. We may assume that c # 0, since that case is trivial (it just says that 0, 0, 0, ... p 0). Since c is a fixed constant, given e > 0, since an > a, we can choose N such that whenever n > N, Ian  al < E/Icl. Then Ican  cai = Icl Ian  al < E, so that can + ca.
3.6. Proposition
17
The proof of (4) is harder, so we start with a discussion. At the end of the proof, we'll, need to estimate Ian/bn  a/bI in terms of things we know are small: Ian  al and I bn  bI. The trick is an old one that you first see in the proof of the quotient rule in calculus: go from an/bn to a/b in two steps, changing one part at a time, from an/bn to a/bn to a/b, to end up with some estimate like: Ian/bn  a/bI < Ian/bn  a/bn l+ I a/bn  a/bI = Ian  aI/IbnI + Ib  bnI Ia/bbnl
We know that Ian  al and Ib  bnI are small, and l a/bl is just a constant, but what about those 1/ I bn l? We need to know that bn is not too close to 0. Fortunately since bn > b, eventually IbnI > IbI/2 (as soon as bn gets within IbI/2 of b). Then 1/IbnI < 2/IbI. So the estimate can continue < Ian  aI(2/IbI) + Ib  bnI 12a/b21
<E/2+E/2=E, if we just make sure that Ian  al(2/IbI) and Ib  bnI I2a/b2I are less than E/2 by making Ian  al < Elbl/4 and Ib  bnI < EIb2/4al (which we interpret as no condition on bn if a = 0). Can we guarantee both of those conditions at
the same time? We can find an N1 to make the first one hold for n > N1, and we can find an N2 to make the second one hold for n > N2. To make both work, just take N to be the maximum of N1 and N2. In general, you can always handle finitely many conditions. Here's the whole proof from start to finish. Since an f a and bn > b, we can choose N such that whenever n > N, the following hold: Ian  al < Elbl/4, lb  bnl < EIb2/4a1,
lb  bnI < IbI/2,
and
which implies that 1/IbnI < 2/IbI
Then Ian/bn  a/bI
Ian/bn  a/bnl + Ia/bn  a/bl = Ian  aI/IbnI + Ib  bnIIa/bbnl < Ian  aI(2/IbI) + Ib  bnI 12a/b21 < E/2 + E/2 = E,
and consequently an/bn +'alb.
It would have been OK and simpler to start out by just requiring that Ian  al < E, I b bnI < E, and Ib  bnI < IbI/2, which implies that 1/IbnI < 2/IbI.
18
Then
3. Sequences
bn  a/bI < Ian,/bn  a/bnI + Ia/bn  a/bI = Ian  al/Ibnl + lb  bnIIa/bbnJ
< e(2/lbl) + E12a/b21 = CE,
where C is the constant (2/Ibl)+12a/b21. Although we haven't made it come out quite as neatly at the end, we've still shown that we can make the error arbitrarily small by choosing n large enough, which is sufficient.
3.7. Rates of growth. Limits of many sequences can be determined just by knowing that for n large,
1/n2 « 1/n< 1 « In n «
« n « n2 « n3 « 2n « en «
on
« n!
where f (n) < g(n) means that f becomes a negligible percentage of g, f (n)/g(n) > 0, so that in a limit as n  oo whenever you see f +g, or even cl f + c29, you can ignore the negligible f. For example, n4 + ln(n + 1) = lim n4 = 1 lim
5n$ + 16
5n$
V
3.8. Three famous limits. (1)
(2)
"2=21/n>20=1.
n n = nl/n = (elnn)1/n = e(Inn)/n

e° = 1.
(The exponent (Inn)/n 40 because Inn << n.) (3)
(1 + 1/n)n p e.
(This is sometimes used as the definition of the number e, after you check that the limit exists. Exercise 25.6 derives it from another definition.)
3.9. Accumulation points. A point p is an accumulation point of a set S if it is the limit of a sequence of points of S  {p}. It is equivalent to require that every ball (p  r, p + r) about p intersect S  {p} (Exercise 19). For example, 0 is an accumulation point of {1/n: n E N} because 0 = lim 1/n or because every ball (interval) about 0 intersects {1/n}. In this case the accumulation point is not in the original set. Every point of the unit interval [0, 1] is an accumulation point. In this case all of the accumulation points are in the set.
3.10. Rn. Almost everything in this chapter works for vectors in R' as well as for points in R. The exception is Proposition 3.6(4) because there is no way to divide vectors. Proposition 3.6(3) holds both for the dot product and for the cross product.
Exercises 3
19

Exercises 3 Does the sequence converge or diverge? If it converges, what is the limit?
1. 1, 0, 1/2, 0, 1/4, 0, 1/8, 0, ... 2. 3, 3.1, 3.14, 3.141, 3.1415, 3.14159, . ..
3. an = 1 + (1)"/n.
4. an =
1+(1)n n
.
5. an = (1)n(1  1/n). 6. an = 1 + (1)n.
7. an $. an 
9. an=
2n2 5n+1 7n +4n+3 ;j5
en +n5.
2R,. n
107 an= sinnnn
11. Prove that an = 1/n converges to 0. 12. Prove that an = 1000/n3 converges to 0. 13. Prove 3.6(2). 14. Prove 3.6(3).
15. Prove that if an < bn < c,,, and lim an = lim cn = L then lim bn = L. 16.
Prove or give a counterexample. Let an be a sequence such that
an+1  an > 0. Does an have to converge?
3. Sequences
20
17. A sequence an is called Cauchy if, given e > 0, there is an N suchthat whenever m, n > N, Ian,,  and < E. Prove that if a sequence in R is convergent, then it is Cauchy. (Exercise 8.6 will prove the converse in R, so that Cauchy gives a nice criterion for convergence without mentioning what the limit is.)
18. Prove that a Cauchy sequence is bounded. 19. Describe the set of accumulation points of the following sets: a. the rationals; b. the irrationals; c. [a, b);
d. the integers.
20. Prove that p is an accumulation point of S if and only if every ball B about p intersects S  {p}. 21.
Prove or give a counterexample: There are only countably many
sequences with limit 0.
22. Prove or give a counterexample: a real increasing sequence
a,
.
converges if and only if the differences an+1  an converge to 0.
Chapter 4
Functions and Limits
Recall that for us a function f takes an input x from some domain E C R' and produces an output f (x) E R. For example, for f (x) = 1/x, the natural
domain is E = R  {0}. We want to extend our notion of limit from a,,, of a sequence, such sequences to functions. Instead of the limit as lim,,,.... 1/n = 0, we want to consider a limit limxp f (x) of a function, such as limx,3 x2 = 9, to give a trivial example. Instead of going way out in our sequence (n rel="nofollow"> N), we will be taking x close to some fixed target p, taking Ix  pl small. To say how small, we'll use the Greek letter before epsilon e, namely delta b, and require that I x  PI < S.
4.1. Definitions. We say limx_,p f (x) = a ("the limit as x approaches p of f (x) equals a") if, given e > 0, there exists a b > 0 such that
0 < IxpI <s= If(x) al <E. Of course we have to assume that x lies in the domain E of f, and hence we need to assume that p is an accumulation point of E. Notice that by requiring that 0 < Ix  p1, we do not allow x to equal p. The limit depends only on values f (x) at nearby points, not on f (p). If it happens that f (x) = f (p), or p is not an accumulation point of E, then f is called continuous at p. Examples of continuous functions include powers of x, sin x, cos x, ex, and combinations of continuous functions such as ex cos x
x2+1 (as long as the denominator is never 0).
4.2. Example. Consider the function f (x) = sin 1, defined on E = lib{0}, graphed in Figure 4.1. Then limx,o f (x) does not exist (Exercise 4). 21
4. Functions and Limits
22
0.8
0.6
0.4
Al
0.2
10.4
0.6
0.8
s
Figure 4.1. For f (x) = sin 1, limyo f (x) does not exist.

4.3. Example. Consider the function f (x) = x sin 1, defined on E = II8 {O}, graphed in Figure 4.2. Then limx.o f (x) = 0 (Exercise 3). If we define f (0) = 0, then f will be continuous.
4.4. Example. Consider the function f (x) on IR which is 1 on nationals and 0 on irrationals. Then lim f (x) never exists, and f is continuous nowhere. This function is called the characteristic function of the rationals and written
f =XQ, using the Greek letter chi.
4.5. Proposition. If
f (x) exists, then it is unique.
Proof. The proof is just like the proof that the limit of a sequence is unique. Suppose that lim,;,P f (x) has two distinct values a, b. Choose S > 0 such
that if 0 < Ix  pI < 5, then
If(x)aI < IbaI/2
and
If(x)bI < IbaI/2.
Since for limits we always assume that p is an accumulation point of the domain, some xo satisfies 0 < Ixo  pI < S. Then lb  al < If  al + I f(xo)  bI < Ib  al/2 + lb  al/2 = Ib  al,
4.6. Proposition
23
Figure 4.2. For f (x) = x sin z , lima.o f (x) = 0.
the desired contradiction.
4.6. Proposition. Suppose that limp f (x) = a and limx,p g(x) = b. Then
(1) lim,p cf (x) = ca, (2) limx,r(f + g) (x) = a + b, (3) limx,p (f g) (x) = ab, and (4) limx,p (f /g) (x) = a/b if b
0.
Proof. The proof is similar to the proof of 3.6; see Exercises 5 and 6.
4. Functions and Limits
24
Exercises 4 1. Give an example of a function f : R + Il8 which is continuous except at the integers. 2. Give an example of a function f : JR  JR which is continuous only at 0.
3. Prove that for the function f (x) of Example 4.3, lim.,,o f (x) = 0.
4. Prove that for the function f (x) of Example 4.2, lim.,;,o f (x) does not equal 0. 5. Prove 4.6(2).
6. Prove 4.6(3).
7. Prove that the sum of two continuous functions is continuous. 8. Prove that the product of two continuous functions is continuous.
9. Give an example of a function which is continuous only at the integers. Graph it. 10. Give an example of two functions, both discontinuous at 0, whose sum is continuous at 0. Give an example of two functions, both discontinuous at 0, whose product is continuous at 0.
11. Consider the function f : JR + JR which is 0 at irrationals and 1/q at a rational p/q (in lowest terms with q positive). Where is f continuous?
Part II
Topology
Chapter 5
Open and Closed Sets
Although sequences played the crucial role in the rigorous understanding of calculus developed in the 1800s, over the next fifty years mathematicians sharpened the theory using the concepts of open and closed sets. If it took
mathematicians fifty years to get used to these more abstract ideas, you shouldn't worry if it takes you a couple of weeks. It's actually quite fun if you take your time and think about lots of examples.
5.1. Definition. A point p in RT is a boundary point of a set S in IRT if every ball about p meets both S and its complement So. The set of boundary points of S is called the boundary of S and written 8S. (That funny symbol, sometimes called del, is not a Greek letter. It is used for partial differentiation too.) It follows immediately that a set S and its complement SC have the same boundary. For example, consider a ball about a point a of radius r > 0:
B(a,r) _ {Ix  al < r} (see Figures 5.1 and 5.2). Its boundary is the sphere:
8B(a, r) =fix  al = r}. In this case the boundary of S is part of S. In R2, we sometimes call the ball a disc and we usually call its boundary a circle rather than a sphere. In II81, the ball B(a, r) is just the interval [a  r, a + r] and its boundary is just the two endpoints. 27
5. Open and Closed Sets
28
3D B(a,r)
Figure 5.1. The boundary of the ball B(a, r) is the sphere. The closed ball includes its boundary.
2D B(a,r)
1 D B(a,r)
a r Figure 5.2. The boundary of a 2D ball or "disc" is a circle. The boundary of a 1D ball or interval is two points.
As another example, consider all of R' with one point, the origin, removed:
S=R{0}. Its boundary is the single point {0}. In this case, the boundary of S is not part of S. The boundary of the rationals Q is all of R. The boundary of R is the empty set.
5.2. Definition. A set S in R' is open if it contains none of its boundary points. A set S in R7z is closed if it contains all of its boundary points. It follows immediately that a set S is open if and only if its complement So is closed.
Many a set contains just part of the boundary and hence is neither open nor closed. "Not closed" does not mean "open." These terms are not opposites!
5.3 Proposition
29
CLOSED
OPEN
NEITHER
Figure 5.3. Some sets are closed or open but most are neither.
For example, the ball B (a, r) is closed. If you remove its boundary, the resulting set is open and is called an open ball, for which unfortunately we have no special symbol. R'  {0} is open. The rationals Q are neither open nor closed. The reals R are both open and closed. See Figure 5.3 for a few more examples. Proposition 5.3 gives nice direct characterizations of open and closed. A set is open if it includes a ball about every point; of course the ball has to get smaller as you get close to the boundary. A set is closed if it includes all accumulation points. See Figure 5.4.
5.3. Proposition. A set S in R'ti is open if and only if about every point of S there is a ball completely contained in S. A set S is closed if and only if it contains all of its accumulation points.
Proof. Suppose that about some point p of S there is no ball completely contained in S. Then every ball about p contains a point of So as well as
5. Open and Closed Sets
30
Figure 5.4. An open set includes a ball about every point. A closed set includes all of its accumulation points.
the point p in S. Consequently, p is a boundary point of S, and S is not open. Conversely, suppose that S is not open. Then some point p of S is a boundary point, and there is no ball about p contained in S. Suppose that an accumulation point p of S is not contained in S. Then every ball about p contains a point of So (namely, p) and a point of S (because p is an accumulation point of S). Therefore, p is a boundary point not contained in S, so that S is not closed. Conversely, suppose that S is not closed. Then So contains some boundary point p of S, which is an accumulation point of S, so S does not contain all of its accumulation points.
5.4. Proposition. Any union of open sets is open. A finite intersection of open sets is open. Any intersection of closed sets is closed. A finite union of closed sets is closed.
Proof. To prove the first statement, suppose that x belongs to the union of open sets Ua. Then x belongs to some Up. By Proposition 5.3, some ball about x is contained in Up, and hence in the union of all the Ua. Therefore, by Proposition 5.3 again, the union is open. To prove the second statement, let U be the intersection of finitely many open sets U2. Let p belong to U. Since p belongs to Ui, there is a ball B(p, ri) contained in Ui. Let r = min{ri}. Then B(p, r) is contained in every Ui and hence in U. Therefore U is open. Let C be an intersection of closed sets Ca. Then CC is the union of the
open sets CC, and hence open. Therefore C is closed. Similarly let C be a union of finitely many closed sets Ci. Then CC is the intersection of the open sets CP, and hence open. Therefore C is closed.
5.5. Definitions (see Figure 5.5). The interior of a set S, denoted int S or S, is S  8S. The closure of S, denoted cl S or S, is S U ,9S. An isolated point of S is the only point of S in some ball about it.
Exercises 5
31
.
P
Figure 5.5. A set, its interior, its closure, and an isolated point p.
5.6. Proposition. The interior of S is the largest open set contained in S, and the closure of S is the smallest closed set containing S. Proof. Exercises 11 and 12.
5.7. Topology. In 1l? or in more general spaces, the collection of open sets is called the topology, which determines, as we'll soon see, continuity, compactness, connectedness, and other "topological" properties.
Exercises 5 1. Say whether the following subsets of T1 are open, closed, neither, or both. Give reasons.
a. [0,1); b. 7L;
_c. {xEIIB: sinx>0}, d. U= 2[1/n,1) 2. Show by example that the intersection of infinitely many open sets need not be open.
3. Show by example that the union of infinitely many closed sets need not be closed.
4. Is all of IR the only open set containing Q? Prove your answer correct.
5. If S = [0,1), what are 8S, S, and S?
32
5. Open and Closed Sets
6. If S = 7G, what are 8S, S, and S?
7. If S = B(0,1) in lR2, what are 8S, S, and S? 8. Give an example of open sets U1 D U2 D n UZ is closed and nonempty.
such that the intersection
9. Give an example of nonempty closed sets C1 D C2 D intersection n Cz is empty.
such that the
10. Prove that every point of S is either an interior point or a boundary point.
11. Prove that the interior of S is the largest open set contained in S. (First prove that it is open.) 12. Prove that the closure of S is the smallest closed set containing S. 13. Prove that a boundary point of S is either an isolated point or an accumulation point.
14. Prove or give a counterexample: two disjoint sets cannot each be contained in the other's boundary. 15. A subset So of a set S is dense in S if every ball about every point of S contains a point of So. Are the rationals dense in the reals? Are rationals with powers of 2 in the denominator dense in the reals? Are the points with rational coordinates dense in RI?
Chapter 6
Continuous Functions
Continuous functions are the bread and butter of calculus. We'll now give three equivalent definitions of continuous functions. The first, our original definition, uses the idea of limit. The second uses the concept of a convergent sequence. The third, modern definition uses the concept of open set. It is the shortest and the most abstract, and it takes a little while to get used to.
6.1. Proposition. Let f be a function from Rn to R. The following are equivalent definitions of what it means for f to be continuous everywhere:
(1) For every point p, given E > 0, there exists S > 0, such that
Ix  pI < S=> If(x)f(p)I <e. (2) For every point p, for every sequence xn 4p, f (xn) p f (p). (3) For every open set U in R, f l U is open.
(2) because if all points x near p have Proof. (1) 4* (2). Easily (1) values f(x) near f(p), then certainly the xn for n large will have values f (xn) near f (p). Conversely, suppose that (1) fails. This means that for some E > 0, no small 5 bound on IxpI, for example S = 1/n, guarantees that If (X)  f (p) I < E. Thus there must be some sequence x, with Ixn PI < 1/n and with If (xn)  f (p) I > e, so that (2) fails.
(1) = (3). Let p E f 1U. Then f (p) E U and hence some small ball B(f (p), E) C U. By (1), choose S > 0 such that
Ix  pI < S= If(x)f(p)I <e, and hence
IxpI <5/2= If(x)f(p)I <E. 33
6. Continuous Functions
34
In other words,
B(p, 6/2) C f1B(f (p), e) C f'U. So we have found a ball about p contained in f 1U, which means that f 1U is open. (3) = (1). Since f 1 of the open ball about f (p) of radius a is open and contains p, it contains some ball B(p, S). Therefore,
Ix  pl < 6=* If(x)f(p)I <e. 6.2. Remark. Proposition 6.1 holds for functions with any domain D C R', with the understanding that "f 1(U) open" means that every point of f 1(U) has a ball about it whose intersection with D is contained in f 1(U). You cannot expect to get whole balls in I[8" if D itself is not open. You just have to pretend that D is the whole universe and ignore other points of R. Sometimes such a condition is called "relatively open." For example, the function f (x) = x is a continuous function from [0, 2] C II8 into R. The inverse image f 1(1, 3) = (1, 2] is not an open subset of IR,
but it is (relatively) open as a subset of [0, 2] even at 2 because points of [0, 2] near 2 are contained in (1, 2]. By these agreements, a function is continuous at an isolated point of the domain.
Exercises 6 1. Use definition (2) to prove that the sum of two continuous functions is continuous.
2. Use definition (2) to prove that the product of two continuous functions is continuous. 3. Use each definition to prove that every function f : Z * JR is continuous. 4. Prove that a function f : IRT  I[8 is continuous at a point p if and only if for every open set U containing f (p), f 1(U) contains a ball B(p, r) about p.
Chapter 7
Composition of Functions
Composition is an important way to build more complicated functions out of simpler ones. Thus you can understand complicated functions by analyzing simpler ones.
7.1. Definition. The composition f o g of two functions is the function obtained by following one with the other:
(f o g)(x) = f (g(x)) For this to make sense, the image of g must be contained in the domain of f.
Examples. If f (x) = sin x and g(x) = x2, then
If f (x) =
(f o g) (x) = sin(x2),
usually written simply sin x2;
(g o f)(x) = (sin x)2,
usually written sin2 X.
and g(x, y) = x2 + y2, then
(f o g) (X) = Jx2 +y2
7.2. Theorem. The composition f o g of two continuous functions is continuous.
Proof. We will give three proofs, using the three equivalent definitions of continuous. See Figure 7.1. 35
7. Composition of Functions
36
.f °g
f(q)=f°g(p) Figure 7.1. The composition f o g of two functions.
ES definition. Given a point p in the domain of g, let q = g(p) be the resulting point in the domain of f , so that (f o g) (p) = f (q). Given E > 0, since f is continuous, we can choose El > 0 such that Iy  qI < El = If (y)  f (q) l < E. Since g is continuous, we can choose S > 0 such that (1)
Ix  pI < S= Ig(x)g(p)I <El. Now applying (1) with y = g(x) and q = g(p) implies that If (g(x))  f (g(p)) I < E,
as desired. Sequence definition. Suppose xn p x. Since g is continuous, g(xn) > 9(X)Then since f is continuous, f (g(x,,,)) > f (g(x)), as desired.
Open set definition. Just note that (f o g)1(U) = g1(f1(U)) (working backwards, we have to start with f). Suppose U is Since f is continuous, f 1(U) is open. Then since g is continuous, g1(f 1(U)) is open, as open..
desired.
Exercises 7 1. What is f o g(x) if a. f (x) = x and g(x) = x2 b. f (x) = sinx and g(x) = sin' x. 2. Show by counterexample that this converse of Theorem 7.2 is false: If the composition of two functions is continuous, then both are continuous.
Chapter 8
Subsequences
We like sequences to converge, but most don't. Fortunately, most sequences do have subsequences which converge.
8.1. Discussion. Limits are a kind of ideal, and in general we want sequences that converge. It's a way to find maxima in calculus and in life. Sequences don't always converge, but there's still hope. The sequence (1)
1
1
1
1
1
1
12, 12, 14, 14, 18, 18
1
'
116'
1
116, ...
does not converge, but the odd terms converge to 1, and the even terms converge to 1. These are called convergent subsequences, and these are good things. Given a sequence, a subsequence is some of the terms in the same order. One subsequence of (2)
al, a2, a3, a4, a5, a6, ..
would be (3)
a2, a3, a5, a7, all, ...,
obtained by using just some of the subscripts. The right way to say this, although it may seem a bit confusing at first, is that given a sequence a,,, we , where above can consider a subsequence a,,,,,, with ml < m2 < m3 <
ml=2,M2=3,M3=5, m4=7, m5=11, .... 8.2. Definition of subsequence. Given a sequence a,,, a subsequence a. consists of some of the terms in the same order.
Now given a sequence, what is the chance that it has a convergent subsequence? Of course if it is convergent, every subsequence, including the 37
8. Subsequences
38
original sequence, converges to the same limit. On the other hand, a divergent sequence like (1)
1, 2, 3, 4, ...
has no convergent subsequence because every subsequence diverges to oo. The following is a delightful and important theorem due to Bolzano and Weierstrass, around 1840. 8.3. Theorem. Every bounded sequence in R has a convergent subsequence.
Proof. We'll first do the case of nonnegative sequences and then treat the general case. So we consider a nonnegative sequence al, a2, a3, ..
Each an starts off with a nonnegative integer before the decimal point, followed by infinitely many digits (possibly 0) after the decimal point. Since the sequence an is bounded, some integer part D before the decimal place occurs infinitely many times. Throw away the rest of the an. Among the infinitely many remaining an that start with D, some first decimal place dl occurs infinitely many times. Throw away the rest of the an. Among the infinitely many remaining an that start with D.dl, some second decimal place d2 occurs infinitely many times. Throw away the rest of the an. Among the infinitely many an that start with D.dld2, some third decimal place d3 occurs infinitely many times. Keep going to construct L = D.dld2d3 .... We claim that there is a subsequence converging to L. Let a,,,,, be one of the infinitely many an which starts with D.dl. Let amt be a later an which starts with D.dld2. Let a,n3 be a later an which starts with D.dld2d3. The
amn converge to L because once n > N they agree with L for at least N decimal places.
Having treated the case of nonnegative sequences, we now consider a sequence with some negative terms. Since the sequence is bounded, we can translate it to the right to make it nonnegative, use the above argument to get a convergent subsequence, and then translate it back. 8.4. Corollary. An increasing sequence in R which is bounded above converges.
(Similarly, a decreasing sequence bounded below converges. The sequence need not be strictly increasing or strictly decreasing.)
Proof. Exercise 3.
Exercises 8
39
Exercises 8 1. Give an example of a sequence of real numbers with two different subsequences converging to two different limits.
2. Give an example of a sequence of real numbers with subsequences converging to each integer. 3. Prove Corollary 8.4.
4. Give an example of a sequence of real numbers with subsequences converging to every real number. 5. Prove that a set S C R is closed and bounded if and only if every sequence of points in S has a subsequence converging to a point of S. 6. Prove that every Cauchy sequence of reals converges. (Use Exercises 3.17 and 3.18.)
7. The lim sup of a sequence is defined as the largest limit of any subsequence, or ±oo. (It always exists.) What is the lim sup of the following sequences?
a. an = (1)"
b. 1, 1,2, 2,3,3.... c. an = n2
d. an = sin(nir/6) e. 1,11,21, 2 2 2 41,11,21, 4 8 4 81,11,21,... 8
f. {an}_Qn(0,1)
Similarly the lim inf of a sequence is defined as the smallest limit of any subsequence, or ±oo. Of course the lim inf is less than or equal to the lim sup. Give two examples of sequences for which the lim inf equals the 8.
lim sup.
Chapter 9
Compactness
Probably the most important new idea you'll encounter in real analysis is the concept of compactness. It's the compactness of [a, b] that makes a continuous function reach its maximum and that makes the Riemann integral exist. For subsets of R"h, there are three equivalent definitions of compactness. The first, 9.2(1), promises convergent subsequences. The second, 9.2(2) brings together two apparently unrelated adjectives, closed and bounded. The third, 9.2(3), is the elegant, modern definition in terms of open sets; it is very powerful, but it takes a while to get used to.
9.1. Definitions. Let S be a set in Rn. S is bounded if it is contained in some ball B(0, R) about 0 (or equivalently in a ball about any point). A collection of open sets {U} is an open cover of S if S is contained in U U(. A finite subcover is finitely many of the Ua which still cover S. Following Heine and Borel, S is compact if every open cover has a finite subcover.
9.2. Theorem. Compactness. The following are all equivalent conditions on a set S in ]Rn. (1) Every sequence in S has a subsequence converging to a point of S. (2) S is closed and bounded. (3) S is compact: every open cover has a finite subcover. Criterion (1) is the BolzanoWeierstrass condition for compactness, which you met for R in Theorem 8.3. The more modern HeineBorel criterion (3) will take some time to get used to. A nonclosed set such as (0, 1] is not compact because the open cover {(1/n, oo)} has no finite subcover. An 41
42
9. Compactness
unbounded set such as R is not compact because the open cover {(n, n)} has no finite subcover. This is the main idea of the first part of the proof.
Proof. We will prove that (3) (2) = (1) = (3)(3) = (2). Suppose that S is not closed. Let a be an accumulation point not in S. Then the open cover {{Ix  aI > 1/n}} has no finite subcover. Suppose that S is not bounded. Then the open cover {{JxI < n}} has no finite subcover. (2) = (1). Take any sequence of points in S C ]Rn. First look at just the
first of the n components of each point. Since S is bounded, the sequence of first components is bounded. By Theorem 8.3, for some subsequence, the first components converge. Similarly, for some further subsequence, the second components also converge. Eventually, for some subsequence, all of the components converge. Since S is closed, the limit is in S. (1) =:>. (3). Given an open cover {Ua}, first we find a countable subcover.
Indeed, every point x of S lies in a ball of rational radius about a rational point, contained in some Ua. Each of these countably many balls lies in some U,,. Let {Vi} be that countable subcover. Suppose that {V} has no finite subcover. Choose xl in S but not in V1. Choose X2 in S but not in V1 U V2. Continue, choosing xn in S but not in U{V : 1 < i < n}, which is always possible because there is no finite subcover. Note that for each i, only finitely many xn (for which n < i) lie in V. By (1), the sequence xn has a subsequence converging to some x in S, contained in some Vi. Hence infinitely xn are contained in Vi, a contradiction. 9.3. Proposition. A nonempty compact set S of real numbers has a largest element (called the maximum) and a smallest element (called the minimum).
Proof. We may assume that S has some positive numbers, by translating it to the right if necessary. Since S is bounded, there is a largest integer part D before the decimal place. Among the elements of S that start with D, there is a largest first decimal place d1. Among the elements of S that start with D.d1, there is a largest second decimal place d2. Keep going to construct a = D.dld2d3.... By construction, a is in the closure of S. Since S is closed, a lies in S and provides the desired maximum. A minimum is provided by  max(S).
Exercises 9
43
Exercises 9 1.
Prove that' the intersection of two compact sets is compact, using
criterion (2). 2.
Prove that the intersection of two compact sets is compact, using
criterion (1). 3.
Prove that the intersection of two compact sets is compact, using
criterion (3).
4. Prove that the intersection of infinitely many compact sets is compact. 5. Prove that the union of two compact sets is compact, using criterion (2). 6. Prove that the union of two compact sets is compact, using criterion (1). 7. Prove that the union of two compact sets is compact, using criterion (3). 8.
Is the union of infinitely many compact sets always compact? Give a
proof or counterexample.
9. Identify the class of sets in JR characterized by the following conditions and give two examples of such sets. a. Every open cover has a finite subcover. b. Every open cover has a countable subcover. c. Some open cover has a finite subcover. d. Every closed cover has a finite subcover. 10. Prove directly that (1) implies (2).
11. (Kristin Bohnhorst). Prove directly that (3) implies (1). Hint: Assume that some (infinite) sequence x,, has no convergent subse
quence. Then every point p of S has an open ball Up around it which contains x,, for only finitely many n. 12. Is the converse of Proposition 9.3 true? Give a proof or counterexample.
9. Compactness
44
13. Prove that if a nonempty closed set S of real numbers is bounded above, then it has a largest element. 14. Define the supremum sup S of a nonempty bounded set of real numbers as max S. Prove that sup S > s for all s in S and that sup S is the smallest number with that property. For this reason, sup S is often called the least upper bound. Similarly, the infimum inf S = min ,9 is called the greatest lower bound.            
inf S
sup S
(If S is not bounded above, sup S is defined to be +oo. If S is empty, sup S is defined to be oo.)
Chapter 10
Existence of Maximum
One of the main theorems of calculus is that a continuous function on a bounded, closed interval [a, b] attains a maximum (and a minimum). It is the reason that the calculus method of finding maxima and minima works. It appears as Corollary 10.2 below. As we will now see, this important result depends on the fact that the interval is compact.
10.1. Theorem. A continuous image of a compact set is compact. We will give two different proofs, one using the BolzanoWeierstrass sequen
tial characterization of compactness, and one using the HeineBorel open cover characterization of compactness. These are very general arguments, which hold in R, in Rn, and even in metric spaces (Chapter 29). We will not give a proof using the "closed and bounded" characterization of compactness because I do not know one. The two natural steps are false, as shown by Exercises 2 and 3. Somehow when the two notions are combined as in the sequential or open cover characterizations, the proof comes fast.
Proof using sequential characterization of compactness. Let f be a continuous function, let K be a compact set, and let a,, be a sequence in f (K). Choose b,,, in K such that f (b,,,) = a,,,. Since K is compact, a subsequence b,,,,n, converges to some limit b in K. Since f is continuous, the corresponding subsequence a,,i. = f (bmn) converges to f (b) in f (K).
Proof using the open cover characterization of compactness. Let {Ua} be an open cover of f (K). Then { f 'U,,,} is an open cover of K. Since K is compact, it has a finite subcover { f 1Uan}. Then {Uan} is the desired finite subcover of f (K). 45
10. Existence of Maximum
46
10.2. Corollary (Existence of extrema). A continuous function on a nonempty compact set K, such as a closed bounded interval [a, b], attains a maximum and a minimum.
Proof. By Theorem 10.1, f (K) is compact. By Proposition 9.3, f (K) has a maximum and a minimum. Remark. Corollary 10.2 depends crucially on the compactness of an interval [a, b] of real numbers. Note that it fails for the rationals. For example, on the interval of rationals from 0 to 2, the continuous function (x2  2)2 has no minimum; the continuous function 1/(x2  2) is not even bounded.
Exercises 10 Give an example of a function (not continuous) on [0, 1] which has no maximum and no minimum. 1.
2. Give an example of a continuous function on a closed (but unbounded) set A c I[8 that has no maximum. 3. Give an example of a continuous function on a bounded (but not closed) set A C 11 that has no maximum. 4. Give a counterexample to the following statement: If f is continuous and S is compact, then f1S is compact.
5. Prove that if K is compact and f and g are continuous, then (f o g) (K) is compact. What do you have to assume about the domains and images of f and g? 6. Prove or give a counterexample: A nonempty set K in IR is compact if and only if every continuous function on K has a maximum. 7. (Candice Corvetti). Prove or give a counterexample: A function f : IR IR is continuous if and only if the image of every compact set is compact.
Chapter 11
Uniform Continuity
For integration, it turns out that continuity is not quite strong enough. One needs a kind of "uniform continuity," independent of x.
11.1. Definition. A function f is uniformly continuous if, given E > 0, there is a S > 0 such that
ly  xI < 6= If(y)f(x)I
<E.
The only difference from mere continuity is that the 8 appears before the x, and consequently cannot depend on x. The same b must work for all x.
11.2. Theorem. A continuous function on a compact set K is uniformly continuous.
This theorem fails on general sets. For example, f (x) = x2 is continuous on IR but not uniformly continuous. To show that it is not uniformly continuous, we have to come up with an e for which no 8 works. In this case, any e will do; let's take e = 1. Now no matter how small S is, there are large x's within 8 of each other for which the values of x2 differ by more than 1. Exercise 4 asks for the details. Geometrically, the problem is that the slope goes to oo. Likewise, f (x) = 1/x is continuous on (0, 1) but not uniformly continuous (Exercise 5).
Proof of Theorem 11.2. Given e > 0, since f is continuous, for each x in K, there is a 8x > 0 such that (1)
ly  xI < sx= lf(y)f(x)I <E/2.
Consider the open ball Ux = {y: ly  xl < 8x/2}. The collection {Ux} of these open balls is an open cover of K. Since K is compact, it has a finite 47
11. Uniform Continuity
48
subcover {U.,2}. Let 6 = min{6,12} > 0. Suppose Iy  xI < J. Since xlies /2, in K, x lies in some Uxj and Ix  xjI < Sam, /2. Since Iy  xI < 6 < I y  xj I < 6x3. Therefore, by (1),
If(x)  f (xj) I< E/2 and If()  f (x3) I< E/2. We conclude that I f (y)  f (x) l
<
I f (x)  f (x;) I + I f (y)  f (x9) I < E/2 + E/2 = E.
Exercises 11 1. Give another example of a continuous function on a closed set which is not uniformly continuous. 2. Give another example of a continuous function on a bounded set which is not uniformly continuous. 3. Prove that a composition of uniformly continuous functions is uniformly continuous.
4. Prove that the function f (x) = x2 is not uniformly continuous on IR.
Hint: Take e = 1, any 6 > 0, x = 1/6, y = 1/6 + 6/2, and show that even
though Iy  xl < 6, If(y)f(x)I
>e.
5. Prove that the function f (x) = 1/x is not uniformly continuous on (0, 1). 6. Prove Theorem 11.2 using the sequential (BolzanoWeierstrass) criterion for compactness. A proof by contradiction might be easiest. 7. Prove that a uniformly continuous image of a Cauchy sequence is Cauchy. Show by counterexample that uniformly is necessary.
8. (Zan Armstrong). Prove or give a counterexample to the following converse of Theorem 11.2. A set S C R is compact if every continuous function on S is uniformly continuous.
Chapter 12
Connected Sets and the Intermediate Value Theorem
The third of the big Cs requisite for calculus, after "continuous" and "compact," is "connected." The famous Intermediate Value Theorem follows easily.
12.1. Definition. A set S is connected if it cannot be separated by two disjoint open sets U1 and U2 into two nonempty pieces S fl U1 and S fl U2 (such that S = (S fl Ul) U (S fl U2)).
For example, the subset S of the reals defined by S = {O} U [1, 3] is disconnected, as may be seen by taking U1 = (1/2,1/2), U2 = (1/2,4). The rationals Q are disconnected, as may be seen for example by taking U1 = (oo, f) and U2 = (f , oo). A singleton is obviously connected. Intervals of reals are connected, although that requires proof:
12.2. Proposition. An interval I of real numbers is connected. Proof. Suppose that I can be separated by two disjoint open sets into two nonempty pieces I fl U1 and I fl U2. Let ai E I fl Ui. We may suppose that al < a2. Let b1 be the largest element of [al, a2]  U2 (which is compact and nonempty because it has a1 in it). Let b2 be the smallest element of [bi, a2]  U1 (which is compact and nonempty because it has a2 in it). Then b1 < b2. Choose b1 < b3 < b2. By choice of b2, the point b3 E U1 and hence U2, which contradicts the choice of b1. b3 49
50
12. Connected Sets and the Intermediate Value Theorem
The converse also is true:
12.3. Proposition. Every connected subset S of R is an interval (or a single point or empty).
Proof. If S is not an interval (or a single point or empty), then there are points a, b in S and a point c between a and b not in S. Then U1 = (oo, c) and U2 = (c, oo) show that S is not connected. 12.4. Theorem. The continuous image of a connected set is connected. Proof. If f (S) is disconnected by U1, U2, then S is disconnected by f 1U1, f1U2 (which are open because f is continuous).
12.5. The Intermediate Value Theorem. Let f be a continuous realvalued function on a closed and bounded interval [a, b]. Then f attains all values between f(a) and f(b).
Proof. By 12.2 and 12.4, f ([a, b]) is connected. By Proposition 12.3, it contains all values between f (a) and f (b).
12.6. Definition. First note that a set is disconnected if and only if it can be separated by two disjoint open sets U1 and U2 into two nonempty pieces
S fl U1 and S fl U2. A set S is totally disconnected if it has at least two points and for all distinct points P1, P2 in S, the set S can be separated by two disjoint open sets U1 and U2 into two pieces Sf1U1 and SflU2 containing pi and P2, respectively. For example, the integers and the rationals are totally disconnected (Exercise 10). Note that every totally disconnected set is disconnected.
12.7. Proposition. A set of reals is totally disconnected if and only if it contains at least two points but no interval.
Proof. Exercise 11.
Exercises 12
51
Exercises 12 1. Prove from the definition that the integers are disconnected.
2. Give a counterexample to the following statement: if f : II8 i IR is continuous and S is connected, then f1S is connected. 3. a. Show that Q x Q C R2 is disconnected. b. Is Q x Q C R2 totally disconnected? 4. Is [0, 1) x [0, 1) C R2 connected?
5. Is the unit circle {x2 + y2 = 1} in R2 connected? 6. Prove that your height (in inches) once equaled your weight (in pounds).
7. Prove that if f is a continuous function from R to Q, then f is constant. 8. What can you say about the continuous image of an interval [a, b]?
9. Let f be a continuous function from R to R such that f (x)2 = x2. What are the possibilities for f? Prove your answer correct. 10. Prove that the integers Z and the rationals Q are totally disconnected. 11. Prove Proposition 12.7.
12. Do you think that there are any uncountable, closed, totally disconnected subsets of R? (Think about this question before discovering the answer in the next chapter.)
Chapter 13
The Cantor Set and Fractals
13.1. The Cantor set. You are now ready to see the Cantor set C, the prototypical fractal and one of the most interesting and amazing sets in analysis. Here's how you construct it. Start with the closed unit interval as in Figure 13.1. Remove the open middle third (1/3,2/3), leaving two closed intervals of length 1/3. Remove the open middle third of each, leaving four closed intervals of length 1/9. Continue. At the nth step you have a set S,, consisting of 2' closed intervals of length 1/3'x. Let c = n Si,. As a subset of the unit interval, C is bounded. As an intersection of closed sets, C is closed. Hence C is compact. C contains countably infinitely many boundary points of intervals, such as 0, 1, 1/3, 2/3, 1/9, 2/9, and so on. However, C contains lots more points:
.( )( {X Xl(
) x x (
)( ). )(X x (
) x }{.
Figure 13.1. The Cantor set C comes from the unit interval by successively removing middle thirds forever. 53
54
13. The Cantor Set and Fractals
......................... .........................................................................,....... .................................................................... ... .................................................................................
Figure 13.2. Sierpinski's Carpet has dimension 1093 8
1.9. (From
http://en.wikipedia.org/wiki/Sierpinski_carpet.)
13.2. Proposition. The Cantor set is uncountable. Proof. Represent elements of the Cantor set as base 3 decimals such as .021201222.... At the first step in the construction of the Cantor set we removed decimals with a 1 in the first decimal place. At the second step we removed remaining decimals with a 1 in the second decimal place. Hence C consists of base 3 decimals consisting just of Os and 2s, such as .020020222.... The rest of the proof is like the proof of Proposition 2.4 that the set R of reals is uncountable. Suppose that C is countable, listed. Construct an element of C not on the list by making the first digit different from the first one on the list, the second digit different from the second one on the list, and so on. Therefore C is not countable.
Although uncountable, the Cantor set has length or measure 0. To see this, just note that Sl has measure 2/3, that S2 has measure (2/3)2, and Sn has measure (2/3)", which approaches 0. Since C is contained in each S,,, its measure must be 0. (Measure is a general word that applies in all dimensions, meaning length
or area or volume. A rigorous treatment requires substantial mathematical development, as in a course on "measure theory.") We also note that the Cantor set is totally disconnected because between any two elements there are deleted intervals.
13.4. Theorem
55
Figure 13.3. The Menger sponge has dimension 1093 20 .:: 2.7. © Paul Bourke. http://astronomy.swin.edu.au/pbourke/index.html
13.3. Dimension and fractals (informal discussion). The plane is 2dimensional, and a region in the plane is 2dimensional. A curve in the plane, however, is just 1dimensional. Likewise, a line or the interval [0, 1] is 1dimensional. A single point is 0dimensional. (Some people say that the empty set has dimension 1, whatever that means.) What about the Cantor set? It seems higher dimensional than a point, but lower dimensional than the interval [0, 1]. In fact, it has dimension 1093 2 pz .63, according to an advanced mathematical concept of "Hausdorff dimension." It is the prototypical fractal, or fractional dimensional set. Like many fractals, it has self similarity: it is made up of two smaller copies of itself, each 1/3 as large as the whole. There is a nice formula for the dimension of such a selfsimilar set:
13.4. Theorem. A selfsimilar set made up of p smaller copies of itself, each 1/q as large as the whole, has dimension logo p.
13. The Cantor Set and F ractals
56
Figure 13.4. A random fractal landscape by R. F. Voss from The Fractal Geometry of Nature by Benoit Mandelbrot. Used by permission.
That the Cantor set has dimension 1093 2 .63 is one example. The unit interval is made up of n smaller copies, each 1/n as large, for dimension log, n = 1. A unit square region is made up of n2 smaller copies, each 1/n as large, for dimension logs n2 = 2. The proof of Theorem 13.4 is beyond the scope of this text.
13.5. More fractals. Figure 13.2 shows a planar fractal called Sierpinski's carpet. It is made up of 8 smaller copies of itself, each 1/3 as large. Hence by Theorem 13.4 its dimension is 1093 8 1.9. Figure 13.3 shows a spatial fractal called the Menger sponge. It is made
up of 20 smaller copies of itself, each 1/3 the size. Hence its dimension is 1093 20
2.7.
Benoit Mandelbrot, the Father of Fractals, discovered that fractals provide better models of physical reality than the smooth surfaces of calculus. Figure 13.4 from his famous book on The Fractal Geometry of Nature shows a random fractal mountain which looks much more realistic than the upsidedown paraboloids of calculus books.
Exercises 13
57
.
Figure 13.5. A fractal constructed by repeatedly removing everything but four corners each 1/4 as large. (From Morgan's Geometric Measure Theory book.)
Exercises 13 1. Show that every point of the Cantor set is an accumulation point. (Such sets are called perfect. Every nonempty perfect real set is uncountable.) 2. Construct a version of the Cantor set by removing middle fifths instead of middle thirds. Is it still compact, uncountable, totally disconnected, and of measure 0? 3. Construct a version of the Cantor set by starting with [0, 1], removing a middle interval of length 1/4, then removing two middle intervals of total length 1/8, then removing four middle intervals of total length 1/16. Is it still compact, uncountable, and totally disconnected? What is its measure? 4. What is the dimension of the fractal of Figure 13.5? 5. Give an example of a totally disconnected set S C [0, 1] whose closure is the whole interval. 6. Give examples, if possible, of continuous maps of the Cantor set onto I18, (0,1), and [0, 1], or say why not possible.
Part III
Calculus
Part III: Calculus. It is satisfying to see how naturally the theory of calculus follows from the basic concepts of real analysis, especially when you remember that after Newton and Leibniz invented the calculus in the late 1600s, it took mathematicians two hundred years to get the theory straight. This part focuses on R' rather than R, although Chapters 17 and 18 hold for realvalued functions on ][8' as well.
Chapter 14
The Derivative and the Mean Value Theorem
Differentiation and integration are the two distinguishing processes of calculus. The first major theorem about the derivative, the Mean Value Theorem, follows easily from the compactness of the interval [a, b], via Proposition 14.2 and Rolle's Theorem 14.3. We begin by recalling the definition of the derivative of a function on an interval in R.
14.1. Definition. Let f be a realvalued function on an open interval (a, b). Define the derivative f = df /dx by
f (t)  f (x) = lim A f f'(x) = lim t*x
tx
Ax,o Ox
If this limit exists, we say that f is differentiable at x. One important interpretation of the derivative is the slope of the graph. More generally, the derivative gives a rate of change. We assume the easy and familiar properties of the derivative and now state and prove the important theorems. We mention that if f is differentiable at x then f is continuous at x.
14.2. Proposition. If f is differentiable at a local interior minimum (or maximum) point x, then f'(x) = 0. Proof. For t near a local minimum point x, the numerator in the definition of the derivative is nonnegative. For t > x, the denominator is positive, and hence f'(x) is a limit of nonnegative numbers. For t < x, the denominator is negative, and hence f'(x) is a limit of nonpositive numbers. The only possibility is f'(x) = 0. The proof is similar for a local maximum. 61
14. The Derivative and the Mean Value Theorem
62
A
11
a
c
b
Figure 14.1. The Mean Value Theorem says that there is a point c where the instantaneous slope equals the average slope from a to b.
Remark. Proposition 14.2 is the basis for finding maxima and minima in calculus. You just have to check where the derivative is 0 (or does not exist) for interior extrema, and also the endpoints (or extreme cases such as x+ ±oo). 14.3. Rolle's Theorem. Suppose that f is continuous on [a, b] and differentiable on (a, b), and that f (a) = f (b). Then for some c E (a, b), f(c) = 0. Proof. As a continuous function on a compact set, f has a maximum and a minimum. If the maximum occurs on the interior, by Proposition 14.2 f' vanishes (is zero) there. Likewise if the minimum occurs on the interior, f' vanishes there. Otherwise, the maximum and minimum both occur at the endpoints, f is constant, and f vanishes everywhere.
14.4. The Mean Value Theorem. Suppose that f is continuous on [a, b] and differentiable on (a, b). Then for some c E (a, b),
PC) =
f (bb
 f (a)
Proof. See Figure 14.1. By horizontal scaling and translation, we may assume that [a, b] = [0, 1]. Unless f (0) = f (1) (in which case the result follows immediately from Rolle's Theorem), by vertical scaling and translation we may assume that f (0) = 0 and f (1) = 1. Let g(x) = f (x)  x. Then g(0) _ g(1) = 0, so by Rolle's Theorem, for some c E (a, b), 0 = g'(c) = f(c)  1. Therefore, f'(c) = 1 = f(bb

a(a).
14.6. The Cantor function
63
it
Figure 14.2. The Cantor function f has derivative 0 except on the Cantor set of measure 0, but it is not constant.
The following theorem is the only reason you need the Mean Value Theorem to do calculus.
14.5. Corollary of the Mean Value Theorem. On an interval where f' is always 0, f is constant.
Proof. Suppose a < b are any two points in the interval. By the Mean Value Theorem, f (b) = f (a).
0
14.6. The Cantor function. Corollary 14.5 may sound obvious, but it is almost false. There is a nonconstant continuous function on [0, 1] with derivative 0 except at a set of points of measure 0. The set is the Cantor set and the function is called the Cantor function. It is defined as follows (see Figure 14.2). Define f to be 0 at 0 and 1 at 1. On the middle third, define f to be 1/2. On the middle thirds of the remaining two intervals,
define f to be 1/4 and 3/4. On the middle thirds of the remaining four intervals, define f to be 1/8, 3/8, 5/8, and 7/8. Continue. f extends to a continuous function on [0, 1]. On the (open) complement of the Cantor set, f is constant on intervals, sand hence has derivative 0.
64
14. The Derivative and the Mean Value Theorem
Exercises 14 1. Check the Mean Value Theorem for the function f (x) = x3 on [0, 1].
2. Suppose that f : II. > IR satisfies f (0) = 0 and I f'(x) I < M. Prove that I f (x) I < MIx1. Apply this to the function f (x) = sinx. 3. Discuss the logical chain of reasoning from compactness of [a, b] to Corollary 14.5.
4. Show that the Cantor function is a continuous map of the Cantor set onto [0, 1], solving part of Exercise 13.6.
Define a map f from C into [0, 1] as follows. Given a point in the Cantor set, represent it by a base three decimal without is in it, such as 5.
.0222022002... , change the 2s to is to get something like .0111011001, and then interpret it as a base two decimal in [0,1]. Is f continuous? surjective?
Is f related to the Cantor function?
Chapter 15
The Riemann Integral
This chapter defines the standard, Riemann integral of a function on a bounded interval [a, b] in 11 and shows that the process works for every continuous function f on [a, b], using the fact that a continuous function on a compact set is uniformly continuous.
15.1. The Riemann integral. The Riemann integral fQ f (x) dx of a function f over an interval [a, b] represents the area under the graph. The area may be approximated as in Figure 15.1 by chopping the interval up into narrow subintervals of perhaps variable thickness Ax, approximating each subarea by a skinny rectangle of height f (x), thickness Ax, and area AA = f (x) .x, and adding them up:
A :: E f (x) Ax. This approximating sum is called the Riemann sum. To get the exact area,
we take the limit as the maximum thickness goes to 0, and call this the Riemann integral: fb
f (x) dx = lim E f (x) Ox. The limit must be independent of the choice of subintervals and of the choice
of where we evaluate f (x) in ;each subinterval. If the limit exists, we say that f is integrable on [a, b]. If f (x) is a constant c, then f is integrable and fb
f (x) dx = c(b  a). 65
15. The Riemann Integral
66
Figure 15.1. The area under the graph of f may be approximated by the sum of areas of skinny rectangles of height f (x) and thickness Ox.
Indeed, every Riemann sum
f(x)Ax=c>i x=c(ba). This corresponds to the fact that the area of a rectangle of height c and width b  a is c(b  a).
15.2. Nonintegrable functions. One function which is not integrable on [0, 1] is the characteristic function XQ of the rationals, which equals 1 on the rationals and 0 off the rationals. Indeed, no matter how small Ax, there .are Riemann sums equal to one, obtained by always choosing to evaluate XQ(x) at a rational, and there are Riemann sums equal to zero, obtained by always choosing to evaluate XQ(x) at an irrational. Another function which is not integrable on [0, 1] is the function f (x) _
1// because no matter how small Ax, there are Riemann sums arbitrarily large, obtained by choosing to evaluate f (x) at a point very close to 0 on the first subinterval. In general, an integrable function must be bounded (Exercise 3). Fortunately, every continuous function is integrable:
15.3. Theorem. Every continuous function is integrable on [a, b].
Proof. By Exercise 8.6, it suffices to show that any sequence of Riemann sums with Ax  0 is Cauchy. By Theorem 11.2, the continuous function f on the compact set [a, b] is uniformly continuous: given e > 0, there exists 5 > 0 such that (1)
JAXI <5= IOfI <e.
Now consider two Riemann sums both with I Ax I < 6/2. Their subintervals
intersect in smaller subintervals of thickness jAxI < 8/2. On each such subinterval, the values f (x) from the two Riemann sums come from points at distance at most 5/2 from a point in the intersection and hence at distance
15.5. Proposition
67
at most S from each other. By (1), these values differ by at most E. Summing over the smaller subintervals, we see that the absolute value of the difference of the Riemann sums equals
1: Af Ax <EI .fI Ax <EEAx=EEAx=e(ba). Therefore the sequence is Cauchy as desired and we conclude that the function is integrable.
Remark. The whole truth is that a function on [a, b] is integrable if and only if it is bounded and its set of discontinuities has measure 0.
15.4. Negative functions. Although for the motivating interpretation as area it is easier to think of f as positive, everything applies as well to functions allowed negative values. Of course if the function is negative, the
integral will be negative. Some students like to remember this as, "Area below the xaxis counts negative."
Normally we expect that a < b, but it is convenient to define the Riemann integral for a > b by
I
ra
b
f (x) dx = 
Jb
f (x) dx.
Finally, instead of fa f (x) dx, we sometimes just write fa f
.
15.5. Proposition. Suppose that f and g are integrable on the relevant intervals and that C is a constant. a.
faCf =Cfa f.
b. faf+g=f f+fag c. fa f = fa f + fbC f .
d. faf HfaIfI e. If f
about Riemann sums. For a, the Riemann sums for C f are just C times the Riemann sums for f. For b, the R.iemann sums for f + g are sums of Riemann sums for f and for g. For c, Riemann sums for the second and third terms yield Riemann sums for the first. For d, the inequality holds for Riemann sums because the absolute value of a sum is less than or equal to the sums of the absolute values. For e, the inequality holds for Riemann sums with the same subintervals and the same choice of places to evaluate f (x) and g(x).
15. The Riemann Integral
68
15.6. Corollary. Suppose that f is continuous on [a, b]. Then b
(b  a) min f (x) < f f (x) dx < (b  a) max f (x). a<x
a
a<x
Proof. By Proposition 15.5e, taking g to be the constant maxa<x
fbf(x)dx
fbcdx=C(b_a),
proving the second inequality. The proof of the first is similar.
_
Exercises 15
69
Exercises 15 1. In approximating ff x dx, suppose you divide [0, 4] into four unit subintervals. What are the possible values of Riemann sums?
2. Compute directly from the definition that b
cdx = c(b  a).
1
3. Compute directly from the definition that 1
x2 dx =
1
1/3
by the following steps. Since by Theorem 15.3 the integral exists independent of choice of subintervals or points to evaluate f (x), we may choose to divide [0, 1] into n subintervals of length Ox = 1/n and evaluate at the righthand endpoints. a. Show that the Riemann sums equal n
n
E f (x)Ox = E(k/n)2(1/n) k=1
b. Use the formula >_1 k2 =
n(n+1/32)(n+1)
n3
> k2. k=1
and take the limit as n + 00
to conclude that fo x2 dx = 1/3. 4. Prove that a nonnegative Riemann integrable function is bounded. 5. Prove that every Riemann integrable function is bounded. 6. Explain why the definition of the Riemann integral does not apply to unbounded intervals such as [0, oo). (Sometimes such an "improper" integral is defined as limR,m fR f (x) dx.)
7. Is the function f : [0, 1]  R defined by
f(x) _ integrable?
0
for 0 < x < 1/2,
1
forl/2<x<1
Chapter 16
The Fundamental Theorem of Calculus
The Fundamental Theorem of Calculus is most popular for its second part, which says that you can integrate just by antidifferentiating, instead of doing painful limits of Riemann sums. Both parts essentially say that integration and differentiation are opposites. It is quite remarkable that there is any relationship between integration and differentiation, between area and slope, between limits of Riemann sums and limits of ratios of change. For the first part, to be able to differentiate after integrating; we treat the upper limit of integration b as a variable, and think of how the Riemann integral changes as b changes.
16.1. The Fundamental Theorem of Calculus. Let f be a continuous function on [a, b]. I.
lbd
f
f(x) dx = f (b)
II. If f (x) = F'(x), then fa f (x) dx = F(x) Id = F(b)  F(a)Proof of I. By the definition of the derivative, d
b+Ob
b
L f (x) dx = bmo db
f (x) dx  f b f (x) dx Ob
f'
bf(x) dx Ob 71
16. The Fundamental Theorem of Calculus
72
If Ab > 0, by Corollary 15.6, rb b+tb f(x) Iy_
kob f (x)
dx
Ab
ix
b Obi f (x)
If Ab < 0, the sign of both the numerator and the denominator change, the As Ab p 0, the fraction remains unchanged, and the inequalities still lefthand side and the righthand approach f (b); hence so does the fraction. Therefore hold..
d db
Jb+Ob f(x) b
J f (x) dx = bmo
dx
Ob
 f (b)
as desired.
Proof of II. Note that by I,
db CF(b) d
ab
f (x) dx = F'(b)  f (b) = f (b)  f (b) = 0.
By Corollary 14.5 to the Mean Value Theorem, b
F(b)1. f(x)dx=C. Plugging in b = a yields
F(a) = C. Therefore b
Ja
f (x) dx = F(b)  F(a).
16.2. Remark. Why don't we just define fa f (x) dx as F(b)F(a)? First of all, we may not know of any antiderivative F. Second of all, how could we expect that to have anything to do with area or other applications? The only sound approach is to define area somehow (the Riemann integral) and then figure out an easy way to compute it.
16.3. Remark. There are amazing generalizations of the Fundamental Theorem to functions on domains in R' and more general domains, which go by names such as Green's Theorem, Gauss's Theorem or the Divergence Theorem, and Stokes's Theorem.
Exercises 16
73

Exercises 16 1. Use the Fundamental Theorem to compute that fo x2 dx = 1/3. Is this easier than direct computation from the definition? 2. Compute db fQ x2 dx two ways, first using 16.1(11), then using 16.1(1).
3. Let F(x) = fox
e_t2
dt. Compute F'(x) and F'(0).
4. What is da .1 a f (x) dx?
Chapter 17
Sequences of Functions
What does it mean for a sequence of functions to converge to some limit function? There is an easy definition, just looking at one point at a time.
,17.1. Definition (pointwise convergence). A sequence of functions fn converges to f pointwise on some domain E if for every x E E, the sequence of numbers ,,,(x) converges to f (x); i.e., for every x in E, given e > 0, there is an N, such that
n > N = I fn (x)  f (x) < E.
For example, if f, (x) = x/n, then fn > f , where f (x) = 0, on R. As a second example, if fn (x) = xn, as in Figure 17.1, then on [0, 1] fn  f, where
for0<x<1 1
forx=1.
It is somewhat disturbing that this limit of continuous functions is not itself continuous. The problem is that although f,,, p f pointwise, the closer the point x gets to 1, the longer it takes for fn(x) to converge to f (x). Indeed, how big you have to take n to make fn (x) close to f (x) goes to infinity as x approaches 1. We need a more uniform kind of convergence.
17.2. Definition (uniform convergence). A sequence of functions fn  f uniformly on some domain E if given e > 0, there is an N, such that
n>N=Ifn(x)f(x)I<E for all x in E.
75
17. Sequences of Functions
76
x Figure 17.1. The continuous functions to a discontinuous function.
x" converge pointwise
The only difference in the two definitions is that in the second, N appears
before x, and hence the same N must work for all x, whereas in the first definition, N is allowed to depend on x. It is amazing that such a seemingly small change can be so important. Uniform convergence is just what you need to get continuous limits: 17.3. Theorem. A uniform limit of continuous functions is continuous. Proof. The idea of the proof is that by uniform convergence, we can handle all points near any particular point p by looking at one fn, that is uniformly near f. Given e > 0, choose N such that for all x in the domain D,
Ifn(x)f(x)I <E. Since fN+l is continuous, given a point p in D, we can choose S > 0 such
that Ix  pi < S= IfN+1(x)fN+1(p)I <e.
17.5. Theorem
77
Then if Ix  pI < S, <_
If (x)  f (P) I
I f (x)  fN+1(x) I+ I fN+1(x)  fN+1(P) I+ I fN+1(P)  f (P) I
<E+6+E= 3e. Therefore f is continuous.
(It is important that by uniform convergence N does not depend on x because S depends on N and S must not depend on x.) 17.4. Question. Suppose a sequence of continuous functions fn converges pointwise to a function f on [0, 1]. Is the limit of the integrals equal to the integral of the limit: 1
lim/
/' 1
J limf?
0
o
In other words, can we switch the limit and the integral? Example. Consider our problematic fn(x) = xn, which converges pointwise but not uniformly to 0 on (0, 1). Then r1 fo
xn+111
r1
1 fn=limf xndx=lim,[n+1o=limn+l
0,
while 1
1
1 limf=J limo=0. Looks OK.
Example. On [0,1], let fn(x) be 0, except let fn(x) be n for 0 < x < 1/n, as in Figure 17.2, so that the integral is always 1, while fn(x) converges pointwise to 0. Then l
imliml=1, fo
while
I
1
1
limf=J limo=0. J0
So it does not always work. Fortunately, it does always work if the convergence is uniform:
17.5. Theorem. For a uniform limit of continuous functions on a bounded interval [a, b],
17. Sequences of Functions
78
3
f3
2 f2
1
fl
Figure 17.2. Functions
with integral 1 and limit 0.
Proof. Given e > 0, choose N such that if n > N, If,,  f I < E. Then
Jfnff
< f If..  fI < J E
Example. 1
lim f (x2 1 + eye /n) dx = in x2 dx = 1/3
n+oo 0
because x2 + eye/n
0
x2 uniformly. Indeed, (x2 + eye /n)  x21 = I ex2 /n I < e/n,
which gets small at a rate independent of x.
17.6. Remark. Even for uniform convergence, the derivative of the limit need not equal the limit of the derivatives (Exercise 9), but something is still true, as we'll see for example in Theorem 21.7.
Exercises 17
79
Exercises 17 1. Give an example of a sequence fn of functions on Z which converge pointwise but not uniformly.
2. Give an example of a pointwise convergent sequence fn of functions on [0, 1] for which r1
lim
J
f0
flimfm.
3. Consider the statement: If f,, > f uniformly, then f 2 p f 2 uniformly. First give a counterexample. Second add a simple hypothesis and prove the revised statement. Prove or give a counterexample: If nonvanishing (never 0) functions f,,, p f uniformly, then 1/fn > 11f uniformly.
4.
5. Consider continuous functions from [0, 1] to IR
0<
fl
converging pointwise to f. Must f be continuous? Give a proof or a counterexample.
6. Find lim,,, fo ' dx. Justify. 7. Find
fi x2(sinnx)/n dx. Justify.
8. A function is called Lipschitz with Lipschitz constant C if If (X)  f(y)I <_ CIx  yI for all x, y in the domain. Let fn be a pointwise convergent sequence of Lipschitz functions on [0, 1] with Lipschitz constant C. Prove that the sequence converges uniformly.
Show by counterexample that even if differentiable functions fn converge uniformly to a differentiable function f on R, it does not follow that the derivatives f' converge uniformly to f'. In particular, describe such a sequence of functions fn converging to 0 such that f,(0) = 1 for every n. 9.
Chapter 18
The Lebesgue Theory
The Riemann integral, however natural, has certain technical flaws and com
plications alleviated by the more general Lebesgue theory. Although the Lebesgue theory is properly the subject of a graduate course, we present some of the convenient results here without proof so that you can start taking advantage of them right away. The Lebesgue integral is a generalization of the Riemann integral. For any Riemann integrable function, it gives the same answer. However, there are more integrable functions. The Lebesgue integral can ignore a countable set (or any set of length or measure 0). For example, in the Lebesgue theory, fo XQ = 0, as it should, since the rationals are a negligible,
countable set. Similarly, for the Cantor set C, fo xc = 0. We also allow unbounded functions and unbounded intervals, so that for example 1
X1/2 = 2x1/211 = 2,
L and
00
1,
X2 = x1101° = 1.
For switching the limit and the integral, there is a stronger theorem with hypotheses that are easier to check:
18.1. Lebesgue's Dominated Convergence Theorem. Let fn be functions on a domain in I[8 converging pointwise to a limit f. If there is a function g with finite integral such that each 1 fn I < g, then
J
lim fn = lim
J
fn. 81
18. The Lebesgue Theory
82
18.2. Corollary (Uniformly bounded functions on a bounded interval). Let f,,, be functions on [a, b] converging pointwise to a limit f. Suppose that for some M > 0, every f,, I < M. Then
J
lim f," = lim j fn,.
Proof. Apply Lebesgue's Dominated Convergence Theorem, with g(x) _ . M. Since the domain is bounded, M has finite integral. For switching the order of integration in a double integral, the following theorem is very useful.
18.3. Fubini's Theorem. For a double integral, it is OK to switch the order of integration if either order yields a finite answer when the integrand is replaced by its absolute value.
18.4. Caveat on measurability. Technically, Theorems 18.118.3 have an additional hypothesis, that the integrands be "measurable." Measurable functions include continuous functions, piecewise continuous functions, perhaps altered on countable sets or sets of measure 0, and much more. They include all functions that you have ever heard of and all functions that can arise in the real world. Indeed, there is a theory of mathematics (without the Axiom of Choice) in which all functions are measurable. So this is not something to worry about. We give one more very useful theorem for switching integration with respect to one variable x with differentiation with respect to another variable t.
18.5. Leibniz's Rule. Suppose that J (t) f (x) t) dx exists, that a(t), b(t), and f (x, t) are all continuously differentiable with respect to t, and that there
is a function g(x) > at (x, t) with r J(t) g(x, t) dx bounded. Then d dt
(I
f
b(t)
Jab(t)
f (x, t) dx =
°Q(t)
C7 f
at
We allow a = oo or b = +oo.
(x,
t) dx + f (b(t), t) Y(t)
 f (a (t), t) d (t).
Exercises 18
83
Exercises 18 fi x2(S,nnx)/ndx. Justify.
1. Compute
z
2. Compute limn, f 0O '+(')'e 1"x dx. Justify. 3. Compute limn,,,,, hl z dx. Justify. 4. Compute fy, 0 fx l0 xy cos xy2 dx dy. Justify. Answer: 3/400.
5. Compute fy 0 f2 Y xey2/y dx dy. Justify. Answer: 1 1/e. 2t
6. Compute At fy 1 S'nx dx. Justify. Answer: 2t (sin 4t  sin t) for t 0 0, 2 for t = 0.
7. Compute d f1 i Answer:
e3_1
ti
eX2t
dx at t = 1. Justify. .17478.
8. Compute y f °OZ+y at y = 0. Justify. Answer: 1/4. 9. Give a counterexample to the following converse to Lebesgue's Dominated
Convergence Theorem: If f,,, > f and f f,,, + f f (all finite), then there exists g > If,, I .with f g < oo.
Chapter 19
Infinite Series E an
Infinite sums or series turn out to be very useful and important because in the limit you can actually attain an apparently unattainable value or function by adding on tiny corrections forever. In theory, they are no harder
than sequences, because to see if a series converges you just look at the sequence of subtotals or partial sums. For example, we say that the infinite series 1
1
1
1 24816+...
converges to 1 because the sequence of partial sums 1
3
7
15
2' 4' 8' 16' converges to 1.
19.1. Definition. The series
°_ a,.,, converges to L if given E > 0 there
is an No such that
N>No=* >anL <E. n=1
Otherwise the series diverges (perhaps to +oo, perhaps to oo, or otherwise "by oscillation"). Of course if a series converges, the terms must approach 0 (Exercise 12). The converse fails. Just because the terms approach 0, the series need not converge. For example, see the harmonic series below.
19.2. Proposition. Suppose that E°O_1 an converges to A and E°°_1 b,,, converges to B. Then EO°_1 can converges to cA and E°°_1
converges
to A+B. 85
19..Infinite Series E an
86
Proof. This proposition follows immediately from similar facts about sequences, as you'll show in Exercise 12. We now summarize some of the famous convergence tests from calculus.
19.3. Geometric series. A geometric series (obtained by repeatedly multiplying the initial term ao by a constant ratio r) (1)
E aorn = ao + aor + aor2
+ aor3 +...
,
converges to j if Irl < 1 and diverges if Irl > 1 (and ao 0). For example, the series at the beginning of Chapter 19, a geometric series with initial term ao = 1/2 and ratio r = 1/2, converges to 111/2 = 1.
Proof. If Irl > 1 (and ao # 0), the terms do not approach 0, so the series diverges. Suppose Irl < 1. Let Sn denote the subtotal Sn = ao + aor + aor2 + aor3 + ... + aorn;
rSn = (1  r)Sn = ao Sn =
+ aorn + aorn+1;
aor + aor2 + aor3 +
 aorn+l;
ao(1  rn+1)
1r
Asn oo,Sn > 1Or' 19.4. ptest. The pseries
converges if p > 1 and diverges if p < 1.
For example, taking p = 1, the harmonic series 1
1
1
1
1
n=1+2+3+4+...
diverges, despite the fact that the terms approach 0. As a second example, taking p = 2, 1
n2
1
1
1
1 22+22+32+42+...
converges, although we do not yet know what it converges to. We omit the proof of the ptest, which uses comparison with integrals.
19.5. Comparison test. If Ian < bn and E bn converges to /3, then E an converges, and its limit a < ,Q. For example, 1+n converges by comparison with verges by the ptest.
n , which con
19.6. Alternating series
87
Proof. It suffices to show that the sequence of subtotals, which is obviously bounded by,6, is Cauchy. For No < M < N, N
M
1: an
N
N
M
N
 E a, = E an : E Ian1 < E bn =
n=1
n=1
n=M+1
n=M+1
n=M+1
M bn  E bn
n=1
n=1
which is small because the sequence of subtotals of > bn is Cauchy.
Remark. The first million terms do not affect whether or not a series converges, although of course they do affect what it converges to. For example, 2 ( 1'0 n ) n converges by comparison with En=2 (2) n = 1 because for nOO=glo n large, 1 glo 10 n < 2. The limit, however, is huge; just the single term when I
)1010 = 1010000000000 n  1010 is (100 to
19.6. Alternating series. If the terms of a series E an alternate in sign and I an l decrease with limit 0,
jail
?1a21>la31...*0,
then the series converges.
For example, the alternating harmonic series (_1)n+l = 1 1 1 1
n
1
2+3
4
converges (to In 2).
Proof. We may assume that the first term is positive. The subtotals after an odd number of terms are decreasing and positive, and hence converge to a limit Ll. The subtotals after an even number of terms are increasing and bounded above by the first term, and hence converge to a limit L2. Since their differences approach 0, Ll = L2 is the limit of the sequence of subtotals.
19. Infinite Series E an
88
Exercises 19 For exercises 111, prove whether or not the series converges. If you can, give the limit.
1 10+loo+1000 2.
65+ 2512
25+
4. En=1 n 1/n 5.
6.
°°
1
Li°°
1
:n=1 nfnn=0
7. E00 n=1 51nn n
8. En'=2 In n . Why did we start the series with n = 2 instead of n = 1? (1)n
9. E°° n=2 nl/n
10. Fn3 (n2+ni)(Inn) . 11. EO° n=1
6n2 89n+73 n 4213n
12. Prove that if a series converges, the terms approach 0. 13. Prove Proposition 19.2.
Chapter 20
Absolute Convergence
20.1. Definitions. A series E a,,, converges absolutely if the series of absolute values > janI converges. Otherwise it converges conditionally (or diverges)
For example, the alternating harmonic series converges conditionally. It follows from the Comparison Test 19.4 that absolute convergence implies convergence.
A rearrangement of a series has exactly the same terms, but not necessarily in the same order. You might expect that order should not matter, and it does not if the series converges absolutely (Prop. 20.2), but it does matter if the series converges merely conditionally (Prop. 20.3). Here is an example:
2_2+2_2+33+33+33+44+44+44+44+... 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
with partial sums 1
1
1
1
1
1
1
1
1
0, 2 , 0, 3 , 0, 3 , 0, 3 , 0, 4 , 0, 4 , 0, 4 , 0, 4 , 0, .. .
2,
converges to 0, but the rearrangement
2+222+3+3+3333+4+4+4+4+4444+... 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
with partial sums 1
2' 1'
1
2,
0'
1
2
3, 3,
1'
2
1
3, 3,
0'
1
4'
1 3 2' 4' 1'
3
4,
1
1 2' 4' 0'
.
.
diverges by oscillation.
20.2. Proposition. If a series converges absolutely, then all rearrangements converge to the same limit. 89
20. Absolute Convergence
90
Proof. Let > an denote the original series, which converges absolutely to some limit L, and let E bn denote the rearrangement. Given E > 0, choose N1 such that if M, N > N1, then N
(1)
N
EanL <e/2.
E lanI,<E/2 and n=M
n=1
Choose N2 such that the first N2 terms of E bn include the first N1 terms
of T an. Let N > N2. Choose N3 such that the first N3 terms of E a, include the first N terms of E bn. Then N
N
EbnL n=1
N3
b, n=1
N3
a, + n=1
1: an  L n=1
Since N3 > N1, by (1) the last expression is at most e/2. Consider the middle expression. All of the terms of the first sum are included in the second sum, and the first N1 terms of the second sum are included in the first sum. Hence by (1) the middle expression is at most e/2. We conclude
that N
EbnL <E, n=1
which means that the rearrangement converges to the same limit L.
20.3. Proposition. Suppose that a series > an converges conditionally. Then its terms may be rearranged to converge to any given limit, or to diverge to ±oo, or to diverge by oscillation.
Proof sketch. First we claim that the amount of positive stuff, the sum of the positive terms, must diverge to +oo, and that the amount of negative stuff must diverge to oo. If both converged, the series would converge absolutely. If just one converged, the series would diverge. Hence both must diverge. Second, note that because the series converges, the terms approach 0. Our rearrangements will keep the positive terms in the same order and the negative terms in the same order. To get big (positive) limits, we'll front
load the positive terms. To get small (negative) limits, we'll front load the negative terms. To get a rearrangement with prescribed limit L, take positive terms until you first pass L heading right. Then take negative terms until you first pass L heading left. Then take positive terms until you pass L heading right. Then take negative terms until you pass L heading left. Since there is an infinite amount of positive stuff and of negative stuff, you can continue
20.5. Root test
91
forever. Since the terms go to 0, the amount by which you overshoot goes to 0. Hence the rearrangement converges to L. To get a rearrangement which diverges to +oo, take positive terms until you pass 1, then a negative term, then positive terms until you pass 2, then a negative term, then positive terms until you pass 3, and so on. To get a rearrangement which diverges to oo, take negative terms until you pass 1, then a positive term, then negative terms until you pass 2, then a positive term, then negative terms until you pass 3, and so on. To get a rearrangement which diverges by oscillation, take positive terms until you pass 1, then negative terms until you pass 1, then positive terms until you pass 2, then negative terms until you pass 2, and so on.
20.4. Ratio test. Given a series E an, let p = limIfI pQanl (Greek letter rho). If p < 1, then the series converges absolutely. > 1, then the series diverges. If p = 1 or the limit does not exist, the test fails; the series could converge absolutely, converge conditionally, or diverge. For example, consider the series 00
n=O
1
1
1
1
1
1
1
1
1
1
1
0!+1!+2!+3!+4!+...1+1+2+6+24+...
n!
To get to the nth term from the previous term, you multiply by 1/n, so the limiting ratio p = 0. Consequently the series converges absolutely (to e).
Proof of Ratio test. Exercise 10. Although I don't usually teach the following test in calculus, it turns out to be of theoretical importance in real analysis.
20.5. Root test. Given a series E an, let p = lim sup n a,, . If p < 1, then the series converges absolutely. If p > 1, then the series diverges. If p = 1, the test fails; the series could converge absolutely, converge conditionally, or diverge.
Proof. If p < 1, to give us some room to work, let p < a < 1 (v is the a, i.e., Ian1 < am, so that Greek letter sigma). Then for all large n, " the series converges absolutely by comparison with the geometric series. If p > 1, for all large n, IanI > 1, and the series diverges because the terms do not approach 0.
20. Absolute Convergence
92
Exercises 20 1. What are the possible values of rearrangements of the following series: a.
F°°
1 .
n=1 2n 1
b. 1:0 1 00
C. Ln=1
(an)n .
(1)n . rn
I
d. En= 1 ,' 1
Prove whether the following series 29 converge absolutely, converge conditionally, or diverge. Give the limit if you can.
i
2. E0n=0 5n 3.
00 n=0
4. E00 n=0
(1)n 5n 5n I,
5. E00 o (5 )n
i
6. E00 n=0 nn
00 (1)n . 7. En=0 771/5
(1)n 00 8. En=0 1+1/n'
9. V'00
n=0
nsinn en
10. Prove the Ratio test 20.4. Hint: Use the proof of the root test as a model.
Chapter 21
Power Series
Power series are an important kind of series of functions rather than just numbers. We begin with consideration of general series of functions.
21.1. Definitions. A series E fn of functions converges (pointwise or uniformly) if the sequence of partial sums converges (pointwise or uniformly). The series E fn converges absolutely if > IfnI converges absolutely. There is a nice test due to Weierstrass for uniform convergence, essentially by comparison with a series of constants.
21.2. Weierstrass Mtest. Suppose Ifn I < Mn where each Mn is a positive number and E Mn converges. Then E fn converges uniformly. Proof. For each x, E fn(x) converges by comparison with E Mn to some f (x) To prove the convergence uniform, note that 00 00 N N fn(x)
 > fn(x)
fn(x)  f(x)
?1m
n=1
n=1
n=N+1
E Mn,
n=N+1
which is small for N large, independent of x. For example, comparison with
Sly converges uniformly on R by Weierstrass Mtest . By Theorem 17.3, the limit is continuous.
21.3. Definition. A power series is a series E anxn of multiples of powers of x, such as 00 xn=1+x+x2+6x3+...
n! 93
21. Power Series
94
which we will identify as ex in Chapter 25. A function defined by a convergent power series is called real analytic.
Of course a power series is more likely to converge if x is small. You might expect a power series to converge absolutely for x small, converge conditionally for x medium, and diverge for x large. The truth is even a bit simpler.
21.4. Radius of convergence. A power series E anxn has a radius of convergence 0 < R < oo, such that (1) for IxI < R, the series converges absolutely;
(2) for IxI > R, the series diverges.
For x = ±R, the series might converge absolutely, converge conditionally, or diverge.
On every interval [Ro, Ro] C (R, R), the series converges uniformly and the series may be integrated term by term. Note that this result admits the possibilities that the series always converges (the case R = oo) or never converges unless x = 0 (the case R = 0).
Proof. To prove (1) and (2), it suffices to show that if the series converges at xo, then it converges absolutely for IxI < Ixol. Since it converges at xo, the terms anx0 converge to 0; in particular, I anx0 j < C. Therefore lanxnl < CIx/xoln,
and E anxn converges absolutely by comparison with the geometric series >CIx/xo1n. Next we prove uniform convergence on [Ro, Ro]. For some leeway, choose R1 between Ro and R. Since the series converges for x = Rl; the terms anRl converge to 0; in particular, I anRl I < C. Hence for all IxI < Ro,
Ianxn) < C(Ro/Rl)".
To apply the Weierstrass Mtest, let Mn = C(Ro/Rl)n; then E Mn is a convergent, geometric series. By Weierstrass, E anxn converges uniformly on [Ro, Ro]. In particular, for [a, b] C (R, R), by Theorem 17.5, the integral of the series equals the limit of the integrals of the partial sums, which of course equals the limit of the partial sums of the integrals of the terms, which equals the series of the integrals of the terms.
21.10 Taylor's formula
95
For example,
[x++++j
1/2'
x2
J
x3
x4
11/2 o
1
1 1 1 2+222+233+244+...
21.5. Hadamard formula. The radius of convergence R of a power series E anxn is given by the formula 1
lim sup I an I
1/n'
under the agreement that 1/0 = oo and 1/oo = 0.
Proof. Using the Root test (20.5), we have p = limsup IanxnI1/n = lxl R Hence by the Root test, the series converges absolutely if x1 < 1, i.e., if x < R, and diverges if x R > 1, i.e., if lx > R. Therefore, RRis the radius of convergence.
21.6. Corollary. Given a power series E anxn, the "derived series" E nanxn1 has the same radius of convergence.
Proof. Multiplication by x (which does not depend on n) of course yields a series with the same radius of convergence: > nanxn. Since lim n1/n = 1, by Hadamard's theorem the radius of convergence is the same as for anxn.
21.7. Differentiation of power series. Inside the radius of convergence, a power series may be differentiated term by term:
(ax7) = > nanxn,1
Proof. On an interval [Ro, Ro] C (R, R), E anxn converges uniformly to some f (x), and the derived series > nanxn1 converges .uniformly to some g(x). Since g can be integrated term by term, f xRo g = f (x)  f (Ro). By the Fundamental Theorem of Calculus, g(x) = f'(x), as desired.
21.8. Corollary. A realanalytic function is infinitely differentiable (C°°). 21.9. Corollary. Inside the radius of convergence, you can antidifferentiate a power series term by term.
21.10. Taylor's formula. If f (x) _ > anxn, then an denotes the.nth derivative.
where f (n)
21. Power Series
96
Proof. f(x) = ao + aix + a2x2 + a3x3 + , f(0) = ao; f'(0) = 1a1; f'(x) = a1 + 2a2x + 3a3x2+ , f"(x) = 2a2 + 3.2a3x + , f"(0) = 2a2; f'(0) 3!a3+ , f'11(x) = = 3! a3; and so on.
Caveat. Given a C°° function f , Taylor's formula yields an associated Taylor Series. Even if the domain of f is all of IR, the Taylor Series could have radius of convergence 0, and even if the series converges, it need not converge to the original function f. In a more advanced course, you will see examples of this strange behavior.
21.11. Power series about c
0. Power series j anx' are best when c, we could use E an (x  c)". There are only x is near 0 (x ti 0). For x minor changes to the theory. The interval of convergence now goes from c  R to c + R, and Taylor's formula becomes an =
(1)
f (n) (c) n1
For example, f (x) = 1/x has no power series about 0 because it is not even defined there. However, in terms of u = x  1, (2)
1 = X
1 1+u
= 1  u + u2  u3 + u4 ...
(for Jul < 1)
=1(x1)+(x1)2(x1)3+(x1)4...
(for Ix11 <1).
Exercises 21 1. a. Prove that x3 x5 x7 x9 x3!+5!7iI 9i...
has radius of convergence R = oo. (Hint: Use the Ratio test 20.4.) b. TRUE/FALSE. It follows that the series converges absolutely and uniformly on every bounded interval [Ro, Ro]. 2. Consider f (x) = >°°_1 . a. Use the Ratio test to show that the radius of convergence R = 1. b. Use the Hadamard formula to show that R = 1.
It follows that the series converges uniformly on every interval [Ro, Ro] C (1, 1). Use the Weierstrass Mtest to show that it actually
c.
converges uniformly on [1, 1].
Exercises 21
97
3. Continuing Exercise 2, consider g(x) = x f'(x).
E'
a. Compute that g(x) = 1 b. TRUE/FALSE. By Corollary 21.6, g(x) has the same radius of convergence R = 1. c. Use the Ratio test and Hadamard formula to show that R = 1. d. It follows that the series for g(x) converges absolutely for jxj < 1. At the endpoints of the interval of convergence 1 and 1, does the series converge absolutely, converge conditionally, or diverge?
4. Find the Taylor Series and its radius of convergence for
a. f(x) = eS; b. f(x) = x2.
5. Leibniz's formula for 7r.
a. Justify that for lx i < 1, 1 1
1+x2
x2+x4x6+x8...
b. Justify that for I xI < 1, x5 x3 tan lx=x3 +  7 } 5
x7
x9
...
9
(Note that it does not suffice to show.that this is the Taylor series for tan 1 x; see the Caveat after 21.10.) c. Assuming that part b also holds for x = 1 (as it does), deduce Leibniz's famous formula for 7r: 4
4
4
4
4 13+57+9..
6. Check Taylor's formula 21.11(1) for the power series 21.11(2).
7. Find a series for 1/x in powers of u = x  2 by noting that
1' x
1
2+u
_
1
1
2 1+u/2
and using the formula for a geometric series. Check Taylor's formula 21.11(1).
Chapter ,22
Fourier Series
22.1. Sines and cosines. The functions sinnx and cosnx on [7r, 7r] are beautiful oscillations representing pure tones. A majestic orchestral chord, represented by a much more complicated function, is made up of many such pure tones. The remarkable underlying mathematical fact is that every smooth function on [7r, 7r] can be decomposed as an infinite series in terms of sins and cosines, called its Fourier series. This is in strong contrast to the fact that only realanalytic functions are given by Taylor series in powers of x. Apparently, for decomposition, sines and cosines work much better than powers of x. There is good reason for studying sines and cosines so much, starting in high school. 22.2. Theorem (Fourier series). Every continuous, piecewise differentiable function f (x) on [ir, 7r] is given by a Fourier series 00 (1)
f(x) = Ao + E (An cos nx + Bn sinnx),
where 1
Ao = 1(2)
An = Bn
1
ff
J
f (x) dx, cos nx dx,
fsinnxdx,
except that at the endpoints the series converges to the average of f (ir) and f(70 99
22. Fourier Series
100
Outside [ir, 7r], the Fourier series just keeps repeating every 27r, so it doesn't always equal f, unless f is also 21r periodic. The proof of Theorem 22.2 is just beyond the scope of this text, although Theorem 25.1 at least proves that the series converges if f is smooth; it takes more work to prove that it converges to f.
22.3. The coefficients. The above formulas 22.2(2) for the Fourier coefficients An, and Bn, due to Euler, deserve comment. First note that A0 is just the average value of f (x), about which f varies or oscillates. The other formulas are best understood by comparison with formulas for the coefficients of a vector
v = vlel + v2e2 + ... +. vNeN
(1)
in RN, expressed as a linear combination of standard basis vectors en. Such basis vectors are orthonormal, that is, em en = 0, except that em em = 1. It follows immediately that the coefficients vn satisfy (2)
by just taking the dot product of each side of (1) with en. Analogously, on. the space of continuous functions on [7r, 7r], one can define a dot product by 1
fg=
(3)
7r
f
7r
f (x) g(x) dx, 7r
integrating all products of values instead of just summing products of components. We want to write everything in terms of the functions cos nx and sin nx, which turn out to be orthonormal functions for this dot product (see Exercise 1). The formulas for the Fourier coefficients 22.2(2) just say that each Fourier coefficient is obtained by dotting the function f (x) with the associated orthonormal function, just like the corresponding formula (2) for vectors.
22.4. Example. For example, consider the piecewise smooth function 0
ifir<x<0,
f(X)= x(7rx). if0<x<7r
of Figure 22.1. Exercise 3 uses 22.2(2) to compute the Fourier series: 2
(1)
f (x) _
12
4
E 2 cos nx + 2
n even n
3
sin nx.
n odd
(See Figure 22.2.)
Fourier series have many serious realworld applications, as in the upcoming Chapter 24. Meanwhile, here is a more amusing application. The
22.5. Proposition
101
Figure 22.1. The piecewise smooth function f (x) = x(ir  x) for 0 < x < 7r.
Figure 22.2. Sum of the first few terms of the Fourier series for the function of Figure 22.1.
following Proposition 22.5 has many proofs; in ours, Fourier series make an
unexpected appearance. The proposition gives the exact sum of the previously mysterious series E(1/n2). By the ptest 19.4, we knew that this series converged, and now we finally find out the surprising answer to what it converges to (how did that 7r get in there?).
22.5. Proposition. The series >(1/n2) converges to 7r2/6. Proof. Plugging x = 0 into the Fourier series 22.4(1) yields: 0
/2
2 2 12f 22+42+62+...
7r2
Multiplying by 2 yields
0612+22+32+... 7r2
so that > (1/n2) = 7r2/6.
1
1
1
22. Fourier Series
102
22.6. Perspective. Since a Fourier series is determined by the coefficients, Fourier series provide a way to encode a function by two sequences A, B,, of numbers with physical significance corresponding to "frequencies." For a violin string, the predominant frequencies are nice multiples of each other, called harmonics, and produce a rich, harmonious sound. In many applications, it is often the case that certain frequencies. dominate, and the function can be well approximated by finitely many terms. Such mathematics can provide a way to encode or compress complicated data, sounds, or images. JPEG is exactly such a method for efficient storage of images. Dolby stereo filters out hissing noise by avoiding the frequencies responsible for such noise. The next chapter (23) will show how Fourier series can be used to solve important differential equations.
22.7. The sine series. If f (x) is an odd function, which means that f (x) = f (x), it follows immediately (Exercise 5) from the formulas 22.2(2) for the coefficients that every A,, vanishes (is 0), so that the Fourier series consists entirely of sines.
Every function f (x) on (0, 7r) can be extended to an odd function on (7r, ir), whose sine series holds for the original function f (x) on (0, 7r): 00 (1)
f (x) _
B,, sin nx, ti.=1
where (2)
Bn = 2 7r
Jo
' f (x) sin nx dx.
The new factor of 2 comes because we are integrating only from 0 to 7r; we wouldn't need it if we integrated the extension from ir to it.
22.8. General intervals. Fourier series (22.2) immediately generalize from [7r, 7r] to [L, L], just by replacing x with irx/L: 00
(1)
f (x) = Ao +
(A,, cos n=1
nix L
+ B,, sin
n7rx) L
,
22.8. General intervals
103
where 1
Ao = 2L (2)
A, = 2L Bn
1
= L L2
L
ff(x)dx,
f
L L
f
L
f (x) Cos nLx dx, L
nirx f (x) sin L dx ,
104
22. Fourier Series
Exercises 22 1. Verify that the functions cos x and sin x are orthonormal on [7r, Tr] for the dot product 22.3(3). 2. What is the Fourier series for f (x) = sin x on [7r, 7r] ?
3. Compute the Fourier series for Example 22.4 using 22.2(2).
Hint: Use integration by parts and notice that cos n7r + 1 is 0 if n is odd and 2 if n is even.
4. Show that the Fourier series for f (x) = x (ir < x < 7r) is given by
x=2
(isinx l2sin2x+3sin3x
Taking x = 7r/2, obtain Leibniz's amazing formula for 7r: 4
4
4
4
1
3
5
7
5. Show that if f (x) is an odd function, which means that f (x) = f (x), then the coefficients A,, vanish (are 0), and you get a Fourier series of sines. Similarly if f (x) is an even function, which means that f (x) = f (x), then the coefficients B,,, vanish, and you get a Fourier series of cosines.
6. Show that the Fourier series for the function
for 7r < x <0,
10
f(x)=
x
for 0<x
7rx
for 7r/2 < x < 7r,
is given by
f (x) =
4 8 it
rr
1
22
cos 2x +
+
1
62
1
cos 6x + 102 cos 10x +
2 (1 7r
12
sin x 
1
32
J
1
sin 3x + 5x2 sin 5x  .. .
Chapter 23
Strings and Springs
Chapter 23 provides classic applications of Fourier series to vibrations of a string and to oscillations of a spring.
23.1. The vibrating string. In 1755 Daniel Bernoulli found a general solution y(x, t) to the differential equation for the small vertical displacement y of avibrating string as a function of 0 < x < 7r and time t. We'll assume
that the string has unit density and tension and is fixed at its endpoints. The simplest solution was
y(x, t) = sin x cost, the curve y = sin x oscillating in time, as in Figure 23.1. Similarly there were simple higher frequency solutions y(x, t) = sin nx cos nt,
oscillating at multiples of the fundamental frequency, as in Figure 23.2.
Figure 23.1. The simplest vibration of a string. 105
23. Strings and Springs
106
01
Figure 23.2. The second simplest vibration of a string.
Finite linear combinations of solutions are solutions. For the general solution, Bernoulli proposed infinite linear combinations: CO
(1)
y(x, t) = E B, sin nx cos nt. n=1
At time t = 0, the initial shape is given by 00
(2)
y(x, 0) _ E B.,, sin nx. n=1
Many mathematicians asked, "What about other initial shapes?" The surprising answer was that every nice function is given as such a Fourier series 22.7(1). This Fourier series for the initial shape (2) determines the contribution of the various frequencies of oscillation in the solution (1). To think about such questions in any detail as we began in Chapter 22 requires a basic understanding of real analysis. Bernoulli had no idea, and it took mathematicians such as Weierstrass over a hundred years to develop what you already know. Questions about the generality and convergence of Fourier series were a major impetus in this development.
23.2. Forced spring oscillations. The displacement x(t) of a unit mass on a spring with spring constant w2 and force w2x satisfies Newton's
famous law F = ma. The acceleration a is the second derivative d2x/dt2, which Newton wrote as , using a dot for differentiation with respect to time t. Thus F = ma becomes (1)
x+w2x=0,
with wellknown general solution (2)
x = c1 cos wt + c2 sin wt.
If a driving force f (t) is applied, the differential equation becomes the much harder (3)
+ w 2 x = f (t)
23.2. Forced spring oscillations
107
We suppose that the driving force f (t) is periodic with period 27r and seek a nice periodic solution. For example, suppose that a pulse as in Example 22.4 is applied every 27r seconds. Assume that x is given by a Fourier series 00
x=Ap+E(Ancosnt+Bnsinnt). n=1
Hoping to be able to use our knowledge of real analysis to justify our actions later, we differentiate the series term by term, 00
En 2 (An cos nt + Bn sin nt),
(4)
n=1
and plug the result into equation (3) along with the Fourier series for f from Example 22.4. Equating coefficients of like terms yields the following equations for the coefficients: AO = 7r2/12w2, (5)
 n2)An = 2/n2,
n even:
(w2
n odd:
An = 0,
Bn = 0, (w2
 n2)Bn = 4/7rn3.
Hence, 2
(6)
x(t)
12w2
4
+
n even
n2
w2_ n2 cos nt + E 7rn3 w2  n2 sin nt, ( ) n odd ( )
a Fourier series for our answer. Resonance. Notice that the largest terms correspond to n closest to w, the natural frequency of the spring. Forced vibrations close to the natural frequency cause huge oscillations, in a phenomenon called resonance. In one notorious case in 1940, the Tacoma Narrows suspension bridge, excited by
winds at its natural frequency, oscillated ever more wildly until it tore itself apart. (Check it out on the web.) According to legend, soldiers break formation before crossing a bridge lest their cadence produce hazardous resonance.
Justification. The justification will use some of. our strongest tools, the Weierstrass Mtest (20.2) and Theorem 16.5 on integrating series term by term (moving the integral inside the summation sign). Start by defining as what you get if you differentiate (6) twice term by term: (7)
1=E n even
2
cos nt  E n2
n odd
n(w24
sin nt. n2)
Note that for n large, the absolute value of the nth term is bounded by Mn = 2/n2. Hence by the Weierstrass Mtest (21.2), this Fourier series converges uniformly. Therefore by Theorem 17.5, it can be integrated term by term,
23. Strings and Springs
108
yielding (6) up to a linear term Cl + C2t, thus justifying the original termbyterm differentiation. Moreover, any solution x whose Fourier series when so twice differentiated is uniformly convergent must by the above process be our solution (6). The equating of like terms will be justified by Exercise 24.2.
Exercises 23 1. Find the Fourier series 22.7(1) in terms of sines for the function
f(x)

x 7r  x
for 0 < x < 7r/2, for 7r/2.< x < 7r.
2. A plucked string has initial shape E f (x) from Exercise 1. Give its solution 23.1(1) as a function of x and t.
3. Check that 23.2(2) satisfies 23.2(1). 4. Derive equations 23.2(5).
5. Show that a periodic solution to 23.2(3), for f (t) a unit pulse from t = 0 to t = 7r/2 repeated with period 27r, is given by
() 
xt
1
4W2 +
°° sin 2 cos nt + (1  cos 2) sin nt
E
n7r(w2  n2)
6. Check that y(x, t) = sin nx cos nt is a solution of the wave equation a2y
a2y
at2  ax2
Chapter 24
Convergence of Fourier Series
Theorem 24.1 provides the promised sample of Fourier theory, relatively easy for you, utterly beyond Bernoulli and 18th Century mathematics. 24.1. Theorem. Let f be a C2 function on [ir, 7r] with f (7r) = f (7r) and f'(7r) = f'(ir). Then the Fourier series for f converges uniformly.
Proof. Let C = max{ f"(x)}. By integration by parts,
rr
1 An=J f(x)cosnxdx 7r
= n f (x) sinnxI",  f"_7rf'(x) sinnx dx
r f"(x) cosnx dx
7r n
= 0 + n2 f'(x) cosnxI,r =0+0
11
" f"
7r n2
a
W2
Ti
(x) cos nx dx.
Hence, IAn cos nx1 <
1irn2 (27r)C =
2C
n Similarly, IBnsinnxl < 2C/n2. Therefore by the Weierstrass Mtest (21.2), the Fourier series converges uniformly.
24.2. Remarks. It takes a bit more work than we are prepared to do to show that the limit is actually f. 109
110
24. Convergence of Fourier Series
Figure 24.1. The Fourier approximations to f (x) = x overshoot by about 9% at the endpoints, the socalled Gibbs phenomenon.
If f (7r) f (Tr), the Fourier series, which according to Theorem 22.2 converges to (f (7r) + f (ir))/2 at the endpoints, thus has a limit discontinuous at the endpoints. Hence, it cannot converge uniformly because a
uniform limit of continuous functions is continuous (Theorem 17.3). Worse, it actually overshoots as it approaches the endpoints by about a mysterious 9% of the difference f (7r)  f (7r), in what is called the Gibbs phenomenon. Figure 24.1 shows the sum of the first ten sine terms of the Fourier series for
f (x) = x, which before coming back to 0 at the right endpoint overshoots the value of 7r by about 9% of 2ir or about .57.
Exercises 24 1. In the proof of 24.1, verify that I Bn sin nx I < 2C/n2.
2. Prove that if a series of the form 22.2(1) converges uniformly to f (x), then it must be the Fourier series for f (x). Hint: cos nx times the series converges uniformly to f (x) cos nx, and hence may be integrated term by term. 3. Use Exercise 2 to solve Exercise 22.2 effortlessly.
Chapter 25
The Exponential Function
It is no small feat to define a new function. There are several ways to define the exponential function exp(x) or ex and derive its properties. The most obvious definition is just as powers of the constant e. For that approach, first you need to define e, perhaps as lim(1 + 1/n)n. Then e2 = e x e, en = e x e x . . . x e (n times), en = 1len, a rational power eP/q is the qth root of eP, but real powers are more complicated, and the various properties of ex do not. follow easily. Rigorous calculus books define the natural logarithm first as an integral, and then define the exponential function as the inverse. Here we follow more sophisticated texts by defining the exponential function by a power series. You may be surprised at how easily all the desired properties follow.
25.1. Definition. Define the exponential function
0 xn exp(x) _ m1 =1+x+ n=O
Define e = exp(1) = E ,
2 1
3
±1 +... .
2.718281828.
25.2. Proposition. The series defining exp(x) converges absolutely on all of 1[8, uniformly on every bounded interval. The function is C°° and may be integrated and differentiated term by term. It is its own derivative. exp(O) = 1 and exp(x) is positive for x > 0. 111
25. The Exponential Function
112
Proof. For the Ratio test (20.4), p = lim xI/n = 0; so the radius of.convergence is oo and by Theorem 21.4 the series converges uniformly on bounded
intervals. By 21.721.9, exp(x) is C°° and may be integrated and differen= exp(x). tiated term by term, to yield exp'(x) = 0 + 1! x + x2/2! + It follows immediately from the definition that exp(0) = 1 and exp(x) is positive for x > 0.
25.3. Proposition. exp(b) =
ex(b)
In particular, exp(1) = 1/e, and
exp(x) is positive for all x.
Proof. This is the part of the development where you might think you would have trouble. Dividing 1 by an infinite series is quite a long division
problem. But it turns out that there is a slick proof. Notice that by the product rule dx
(exp(x) exp(x)) = exp(x) exp(x)  exp(x) exp(x) = 0.
Hence exp(x) exp(x) is a constant function: exp(x) exp(x) = C. Plugging in x = 0, we see that C = 1. Hence exp(x) = 1/ exp(x), as desired.
25.4. Proposition. exp(a + b) = exp(a) exp(b). Proof. Since by the quotient rule d exp(a + x) exp(a + x) exp(x)  exp(a + x) exp(x) dx
exp(x)

exp2(x)
 0,
exp(a+x) = Cexp(x). Plugging in x = 0 yields C = exp(a), as desired.
25.5. Corollary. exp(n) = en; exp(p/q) = 9 eP. Proof. By Proposition 25.4, exp(n) = exp(1) exp(1) ... exp(1) = e'. Likewise, (exp(p/q))q = exp(p) = eP, which implies that exp(p/q) = eP/q. If we now define e' as exp(r) for all real numbers, this definition will agree with any others by continuity.
25.6. Corollary. (1) exp(x) is strictly increasing. (2) For every n, there is an en, > 0, such that for x > 0, exp(x) > en,x". (3) Given C > 0 and n, for x large, exp(x) > Cx".
Proof. Conclusion (1) follows because the derivative exp(x) is positive. Conclusion (2) follows from the defining series, with e,, = 1/n!. In particular, given C > 0, for x > 0, exp(x) > (1/(n + 1)!)xn+1, which is greater than Cxt once x > C(n + 1)!.
Exercises 25
113
25.7. The natural logarithm. It follows from Corollary 25.6(1) that exp(x) is as bijective map from R onto the positive reals. The inverse function from the positive reals onto R is called the natural logarithm function, written In x in calculus books and log x in more advanced mathematics. Its properties, such as (log x)' = 11x, follow from the properties of exp(x). See Exercise 4.
25.8. Complex exponentials. Although we have dealt only with real series, all of our results hold for series of complex numbers z = x + iy, including the definition and properties of exp(x). Here i2 = 1, i3 = i,
i4 = 1.....
Exercises 25 1. Development of the sine and cosine functions. Define x2
cosx=
2
+
x4
x6
4! x5
6!
sinx=x  x33 + 5 
x7 
+
x8 8!
,
+x99  .
a. Check that the radii of convergence are oo, so that these functions are defined for all x.
b. Show that cos(x) = cosx and that sin(x) sin(x). c. Show that (sin x)' = cosx and that (cosx)' sin x. 2 d. Prove that sin x + cost x = 1. Hint: First show the derivative 0, so that sin 2 x + cost x = C. Then use
x=0tofind C. Note that this implies that I sin x < 1 and I cos x < 1. 2. By plugging into the series for ex, verify Euler's identity ez0
= cos 0 + i sin 0.
3. Use Euler's identity and the fact that ei(a+b) = eiaeib to deduce that sin(d + b) = sin a cos b + cos a sin b,
cos(a + b) = cos a cos b  sin a sin b.
25. The Exponential Function
114
4. Since the exponential function has a nonvanishing (never 0) continuous derivative, it follows from the Inverse Function Theorem (which did not quite make it into this book) that its inverse, log x, is continuously differentiable.
a. If y = log x, then x = ey. Differentiate implicitly to deduce that (log x)' = 1/x. b. Prove that log cx = log c + log x. 5. Obtain a power series for logx in powers of x  1 by integrating 21.11(2). Check Taylor's formula (21.11(1)) for this series. 6.
Prove that e = limn. + (1 + 1/n)'. (This is sometimes used as the
definition of e.)
Hint: It suffices to show that
log(1 + 1/n)n = n log(1 + 1/n) p 1. By the definition of the derivative, log(1 + Ox) log' lim g( 1) = Ix>O Ox Therefore, taking Ox = 1/n, nlog(1 + 1/n) * log'(1) = 1.
Chapter 26
Volumes of nBalls and the Gamma Function
There is a wonderful formula (26.5) for the volume of the ball B(0, r) in I[8": IT/2
vol B (0, R) =
(n/2)
Rn.
For example, the "volume" or area of a ball in R2 is (222), r2 = 'irr2. The volume of a ball in R4 is 2ir2r4. However, according to this formula, the "volume" or length of a ball in R1, which should be 2r, is (%2), r. What is (1/2)! ? For our formula to work, we would need (1/2)! = vfir/2.
Fortunately, there is a nice extension of (x1)! from integers to real numbers greater than 1, called the Gamma Function r(x).
26.1. Definition. For x > 1, define the Gamma Function r(x) by
r (x) =
f
et1 dt.
This integral converges because et grows faster than any power of t.
26.2. Proposition. r(D; + 1) = xr(x).
Proof. Using integration by parts, f u dv = uv  f v du, with u = t', dv = etdt, du f= xtx1, v = et, 00
00
r(x + 1) =
J0
ettX dt = ettx1o 00 +
J0
xettx1 dt = 0 + xr(x).
a
115
26. Volumes of nBalls and the Gamma Function
116
26.3. Proposition. For every nonnegative integer n, F(n + 1) = n!.

We can use this relationship to extend the definition of the factorial function to every nonnegative real number by x! = F(x + 1).
Proof by induction. First we note that for n = 0,
I'0+1 =I'1 =
etdt=et°° 0 (1) =1=0!.
Second, assuming the result for smaller values of n, we see by Proposition 26.2 that F(n + 1) = n r (n) = n(n  1)! = n!.
26.4. Proposition. F(1/2) _ V'7r. Proof. By making the substitution t = s2, dt = 2s ds, we see that
F(1/2) =
f
ett1/2 dt =
es2s ds = J 00 eds. J z
z
0
Now comes the famous trickmultiplying r(1/2) by itself and switching to polar coordinates with dA = r dr dB:
r(1/2) I'(1/2) = 00
jO27r
=
:;;:
:1::
=
oo
=oJr=o
1
z
eT r dr dO = 21r eT 2
°°
z
= 7r. Jn
Therefore 1'(1/2) = V?r.
In particular, (1/2)! = 1'(3/2) = (1/2)1'(1/2) = //2, as we hoped. Note too that our formula gives for the volume of a ball in R3: X3/2
x.3/2
4
vo1B(0,r) =
(3/2)!r3 the correct, familiar formula.
26.5. Proposition. The volume of a ball in I18' is given by rn/2
volB(0,R) = (n/2)[Rn Proof. We haven't defined volume; we will assume here that it can be computed as in calculus, by integrating over slices. We've already checked this formula for n = 1 and n = 2. We'll prove it by induction, assuming the result for n  2. (By jumping two dimensions at a time, we can use a much
26.7. Stirling's Approximation
117
simpler polar coordinates proof.) We view the nD ball {x2 + x2 + x2 +
+
x2 < R2} as a 2D ball {r2 = xi + x2 < R2} of (n  2)D balls of radius s satisfying s2 x3 + + xn = R2  r2 and volume (by induction) ?r(n,2)/2
n2 = ((n/2)  1)!' n2 7r(n/2)1
((n  2)/2)!
s
Hence,
(n/2)1 vol B (0, R) =
Ifsn2 dA
((n/2)  1)t 7r(n/2)1
((n/2)  1)! ((n/2)  1)!
j 27r
R
(R2
 r2)(n.2)/2r dr dO
=0 r=0 1 (R2  r2)f/2
2
R
n/2
1 Rn
, (n/2)1
_ ((/2) n
2r
 1) 2/2 n = (n/2) Rn
0
7rn/2
27r
.
26.6. Corollary. The volume of the (n  1)D sphere in 1R is given by vol S(0, R) = n
7r
n/2
(n/2)
Rn
For example, the circumference of a circle in R2 is given by 2R = 27rR.
Proof. The volume of the sphere is just the derivative of the volume of the ball (the greater the surface area, the faster the volume of the ball increases).
26.7. Stirling's Approximation. The Gamma function may be used to derive an excellent asymptotic approximation to n! n!
27rn(n/e)n.
(Technically this asymptotic symbol  means that as n > oo, 1.) It follows that e n << n! << nn .
(For the definition of rates of growth, see 3.7.)
2rn'(In./e)n
118
26. Volumes of nBalls and the Gamma Function
Exercises 26 1. a. Use Propositions 26.2 and 26.4 to find a numerical value for (3/2)! _
r(5/2). b. Check the formula for the volume of the ball B(0, r) in R3. 2. What is the volume of the ball B(0, r) in IE85? in ]R6?
3. What is the area or volume of the sphere (surface of the ball) S(0, r) in ][83? in R4? in R5?
4. Use Stirling's Approximation and your calculator to estimate that loglo 1000! Try to estimate 1000! by any other 2567, so that roughly 1000! ^s means. 102567.
5. Use Stirling's Approximation to prove that en << n! <<
n'.
Part IV
Metric Spaces
Chapter 27
Metric Spaces
To do analysis, you don't need ', just a space with a way to measure distance, called a "metric." In R, the distance p(x, y) between two points x and y is just AX, Y) = x  yI
(we're using the Greek letter rho for distance). This distance has three nice properties:
(1) It is always positive, except that the distance from a point to itself is zero.
(2) The distance from x to y is the same as the distance from y to x. (3) The triangle inequality holds: the distance between two points is less than or equal to the total distance via a third point. Any function that satisfies these three properties is called a metric.
27.1. Definition. A metric space is a set X with a distance or metric p(x, y) defined between every two points of X satisfying the following three properties:
(1) Positivity: p(x, y) > 0, with equality if and only if y,= x. (2) Symmetry: P(y, x) = P(x, y) (3) Triangle inequality:, p(x, z) < p(x, y) + p(y, z).
27.2. The taxicab metric on 1R2. As our first new example, we define a new metric between every two points (xl, x2) and (yi, y2) in R2 as the sum of the horizontal and vertical distances: P(x, y) = Jxl Y1 I+ 1x2 Y21121
122
27. Metric Spaces
Figure 27.1. The unit ball for the taxicab metric is a diamond.
This is called the taxicab metric because it is the distance that a taxicab, confined to horizontal and vertical streets, has to travel to get from one point
to the other. Notice that the unit ball in this metric, the set of all points within distance 1 of the origin, is a diamond, as pictured in Figure 27.1. The point (2 , 2) for example is at distance 1 from the origin. It is easy to check that the taxicab metric does indeed satisfy properties (1)(3) above.
27.3. The space C [0, 1] of continuous functions on [0, 1] with the sup metric. Our second new example is the huge space C[0,1] of continuous functions on [0, 1], with the sup metric defined as the maximum or supremum of the absolute value of their difference: p(f, g) = sup{ f (x)  9(x) I : x E [0, 1]j.
Notice that the elements or "points" of this space are functions. Under the sup metric, two functions are within e of each other if their values at all points are within E of each other. Again it is easy to check that this metric satisfies properties (1)(3). (For continuous functions, the maximum is attained, so we do not really need the more general notion of supremum from Exercise 9.13.)
27.4. The space W of words. Let W be the space of all words or gibberish of any finite number of letters, such as "cucumber" or "rqxiibt". There are lots of different metrics you could define on this space. We will define the distance between two elements of W as the fewest number of changes it takes to get from one to the other, where in each change you can:
Exercises 27
123
(1) delete any letter, such as "apple" to "aple," (2) insert any letter, such as "sand" to "stand," (3) replace any letter with another letter, such as "rocket" to "gocket," or
(4) switch any two adjacent letters, such as "slat" to "salt."
It's fun to think about examples. Some of the words in B("pat", 1) are "at," "spat," and "apt." How many others are there? Of course, B("pat", 1) contains lots of gibberish too, such as "jat" and "pxt." The distance between the words "math" and "money"
p("math", "money") = 4,
because it takes four changes to get from "math" to "money" (math i moth > monh + mone ' money).
Exercises 27 Is each of the following a metric on the space of continuous functions from [0, 1] to R? If not, explain why not. 1.
a. p(f, g) = If (1/2)  g(1/2) I b. p(f, g) = sup{If'(x)  g'(x)I}.
c. p(f, 9) = fo I f (x)  9(x) I dx.
d. P(f 9) = f o I f (x)  9(x) I2 dx. e. p(f, g) _
How many words can you find in B ("pat" ,1)? How many elements (counting words and gibberish) are there in B ("pat", 1)? 2.
Chapter 28
Analysis on Metric Spaces
Analysis on metric spaces is very similar to analysis in R. Just replace the distance Ix  yj with the more general p(x, y).
28.1. Definition. A sequence an in a metric space X converges to a limit
L (an  L) if, given e > 0, there is some N such that whenever n > N, p(an,L) < E.
In C[0,1], fn f f under the sup metric therefore means that fn p f uniformly. So fn(x) = x/n converges to f (x).= 0, but fn(x) = xn does not converge (uniformly) to f (x) = 0. Most of the results on sequences of Chapter 3 remain true in metric spaces. The exception is Proposition 3.6 because in a general metric space there is no addition, multiplication, or division. 28.2. Definition. A sequence an in a metric space X is bounded if all the terms lie in some ball. A sequence an in a metric space X is Cauchy if, given e > 0, there is some N such that whenever m, n > N, p(a,n, an) < E. Every convergent sequence is Cauchy (Exercise 3), but whether every Cauchy sequence converges depends on the metric space. It is true in the reals. It fails in the space of rationals, since 1, 1.4, 1.41, 1.414, ..., which converges to
in IR, does not converge in Q, even though it is still Cauchy.
The problem is that
is missingthe space is somehow not "complete."
28.3. Definition. A metric space X is complete if every Cauchy sequence converges (to a point of X). 125
28. Analysis on Metric Spaces
126
is complete, but Q is not complete (Exercises 16 and 17). C [0, 1] is complete (Exercise 18), essentially because a uniform limit of continuous functions is continuous and therefore is not missing from the space. Our word space W is complete because every point is isolated (no other points within distance 1/2) and hence all Cauchy sequences are eventually constantthe only way'for words to be very close together is for them to be identical. If a metric space X is not complete, one can form the "completion" by adding limits of all Cauchy sequences. Instead of defining the reals via decimals, some texts define the reals as the completion of the rationals. You have to be careful because different Cauchy sequences correspond to the same real number. 11
Topology on a metric space X is very similar to topology in R.
28.4. Definitions. A point p in a metric space X is a boundary point of a set S if every ball
B(p,r) = {x E X : p(x,p) < r} about p meets both S and So. The set of boundary points of S is called the boundary of S and written 8S. A set S is open if it contains none of its boundary points. A set S in Rn is closed if it contains all of its boundary points. For example, a ball B(p, r) is closed; if you remove the boundary, the resulting set is open and is called an open ball. The interior of a set S, denoted int S or S, is S  S. The closure of S, denoted cl S or S, is S U 8S. An isolated point of S is the only point of S in some ball about it. Every ball about an accumulation point of S contains infinitely many points of S. All of the results of Chapters 57 continue to hold in metric spaces.
Exercises 28
127
Exercises 28 1. In the space C[O, 1], does the sequence f, converge or diverge (under the sup metric)? If it converges, what is the limit? a. f,,(x) = x2 /n; b. fn(x) = x2n
2. Suppose that a sequence a,, converges in a metric space. Prove that the limit is unique and that the sequence is bounded. 3. Prove that a convergent sequence in a metric space is Cauchy. 4. Prove that a set S in a metric space is open if and only if the complement So is closed.
5. Prove that a set S in a metric space is open if and only if about every point of S there is a ball completely contained in S. 6. Prove that a set S in a metric space is closed if and only if it contains all of its accumulation points. 7. Say whether the set is open, closed, neither, or both in the'space C[O, 1].
a. If (1/2) < 6}; b. {f(1/2) < 6};
c. B(0,1).
8. Prove the following statements in a metric space. Any union of open sets is open. A finite intersection of open sets is open. Any intersection of closed sets is closed. A finite union of closed sets is closed.
9. Prove that in the word space W every singleton is open, and hence every set is open and closed.
10. If S = {0 < f (1/2) < 1} C C[0,1], what are 8S, S, and S? 11. Prove that the interior of S is the largest open set contained in S. 12. Prove that the closure of S is the smallest closed set containing S.
128
28. Analysis on Metric Spaces
13. Prove that a is an accumulation point of S if and only if a is the limit of a sequence of other points in S. 14. Prove that a boundary point of S is either an isolated point or an accumulation point.
15. Prove that every point of S is either an isolated point or an accumulation point. (Why does this not imply Exercise 14?) 16. Show that Q is not complete.
17. Prove that R is complete. 18. Prove that C[O, 1] is complete.
19. Do Proposition 6.1 and proof generalize to realvalued functions on a metric space?
Chapter 29
Compactness in Metric Spaces
This is the moment when metric space topology takes a nasty turn. In a general metric space, the three characterizations of compactness of Theorem 9.2 are no longer equivalent: a closed and bounded set need not satisfy the other two. First we will give two natural examples of this phenomenon. Then Theorem 29.3 explains that the other equivalences continue to hold.
29.1. Example. Let ]R°° denote the space of all real vectors (X1, x2, X3.... ),
with infinitely many components, within finite distance of the origin:
R' _{(mil, x2, X3, ...) : X1
X2
X 3+'' < oo}
with metric
1/2
P(x, y)
y'')2)
This space is a lot like R'. The unit ball B(0,1) is closed and bounded, but unlike R", the unit ball B(0,1) admits sequences with no convergence subsequences. For example, let
el = (1,0,0,0,...), e2 = (0,1,0,0,...), e3 = (0, 0,1, 0, ... )
and so on. This sequence has no convergent subsequence because it has no apart. The problem Cauchy subsequence because all terms are distance is that R°° is infinite dimensional. 129
29. Compactness in Metric Spaces
130
29.2. Example. Similarly, consider the unit ball B(0, 1) in C[0,1]. It is closed and bounded, but admits sequences (of functions) with no (uniformly) convergent subsequences. (Recall that convergence under the sup metric of
C[0,1] means uniform convergence.) For example, let fn (x) = x7L, as in Figure 17.1. Then any subsequence converges pointwise to
f(X)
] 0 for0<x<1, 1
forx=1,
which is therefore the only possible limit; but no subsequence can converge
uniformly because a uniform limit would have to be continuous, and f is not continuous. Fortunately, although in metric spaces closed and bounded does not yield convergent subsequences, the stronger two characterizations of compactness remain equivalent:
29.3. Theorem. For a set K in a metric space X, the first two conditions are equivalent and imply the third. (1) Every sequence in K has a subsequence converging to a point of K. (2) K is compact: every open cover has a finite subcover. (3) K is closed and bounded.
In Exercise 1 you will prove that (1) = (3). We will prove first that (2) = (1) and second that (1) = (2), which is a bit harder (and false in still more general topological spaces than metric spaces). Our earlier proof of (1) = (2) in Rn (Theorem 9.2) no longer works because an open cover of a general set need not have a countable subcover because there need not be a dense countable set like the rationals.
Proof that (2) = (1). Assume that some sequence an in K has no subsequence converging to a point of K. Then every point x of K has a little open ball Uy around it containing only finitely many an (counting multiplicity, i.e., containing an for only finitely many values of n, even if lots of the an happen to be equal). By hypothesis (2), finitely many such U,; cover all of K. Hence, there are only finitely many an, a contradiction, since an is an infinite sequence.
Proof that (1) (2). Let {Ua} be an open cover of K. First we claim that for some e > 0, for every x E K, B(x, e) is contained in some U. Otherwise, let xn be a sequence of points in K such that B(xn,1/n) is contained in no Ua. By hypothesis (1), some subsequence converges to a point a in K. Some B(a, r) is contained in some U. Hence, once p(xn, a) < r/2, B(xn, r/2) is contained in Ua, a contradiction once 1/n < r/2.
Exercises 29
131
Now as long as possible choose disjoint balls of radius e/2 centered at points yn in K. This cannot go on forever to produce an infinite sequence because such a sequence yn could not have a convergent subsequence because it is not Cauchy. Hence, after choosing some yN, for every y in K, B(y, e/2)
intersects some B(yn, s/2). Hence, the finite collection {B(yn, e)} of balls twice as large covers K. Choose Uan containing B(y,,, E). Then {Uan} is the desired finite subcover of K.
Remark. All of the results of Chapters 1012 continue to hold in metric spaces. See for example Exercise 29.3.
Exercises 29 1. Prove that 29.3(1) = 29.3(3). 2. Here is a trivial "artificial" example of a closed and bounded set which is not compact. Let X be the integers with metric p(m, n) = 1, except that p(n, n) = 0. Check that p is a metric. Show that X is closed and bounded, but not compact. 3.
Prove that in a metric space, a continuous realvalued function on a
nonempty compact set attains a maximum. (Cf. Corollary 10.2.) . 4. Do Theorem 11.2 and its proof generalize to a metric space?
Chapter 30
Ascoli's Theorem
To solve problems, one needs compactness in order to extract from a sequence of approximate solutions an exact solution in the limit. For sophisticated problems, the desired solution is not just a number, but rather a function, perhaps describing an economically ideal schedule of production or the most efficient shape of an airplane wing. Unfortunately, as we have seen, even the closed unit ball in the space C[O, 1] of realvalued continuous functions on the unit interval under the sup metric is not compact. Fortunately, Ascoli's Theorem provides useful compact spaces of functions. The main hypothesis is a uniform kind of continuity called equicontinuity. See if you can spot the difference from uniform continuity:
30.1. Definition. A set of realvalued functions f on a domain D C R is equicontinuous if, given e > 0, there is a 5 > 0 such that
y  xI < b= If(y)f(x)I
<E.
The difference from uniform continuity is that b is independent not only of x but also of f : the same b works for all f. Note how equicontinuity fails for our previous Example 29.2 (fn (x) _ x"'). As n approaches infinity, xn increases rapidly near 1, and for given e > 0, S approaches 0; S is not independent of which In we consider.
30.2. Ascoli's Theorem. Let .F be a closed, bounded, equicontinuous subset of C[0,1]. Then .T is compact. 133
30. Ascoli's Theorem
134
Proof. Let f,,, be a sequence of functions in F. Note that for any fixed point p, f,,,(p) is a bounded sequence of real numbers and hence has a convergent subsequence. Similarly, if q is another point, we can take a subsubsequence converging at q as well as at p. Indeed, given any finite number of points, it is easy to find a subsequence converging at those points. Begin by taking a subsequence Si that converges at 0, 1/2, and 1, i.e., at all multiples of 1/2, to some limit values h(0), h(1/2), h(1). By throwing away the beginning of the subsequence, we may assume that all values are within 1/2 of the limit values at those three points. Next take a subsequence S2 of Sl that converges at all multiples x of 1/4 to some limit values h(x), such that all values are within 1/4 of the limit values at those five points. In general, take a subsequence SN of SN_1 that converges at all multiples x of 1/2N to some limit values h(x), such that all values are within 1/2N of the limit values at those 2N + 1 points. Now we are ready to construct the desired subsequence of f,,,. As the first term, gl, choose the first term of S1. For 92, choose a later term of S2. In general, for gN, choose a still later term of SN. We claim that the sequence g,, is uniformly Cauchy. Given e > 0, by equicontinuity choose b > 0 such that
Iy  xI < s = Ign.(y)  g.(x)I < E/3.
(1)
Choose N such that 1/2N < b and 2/2N < e/3.
(2)
Suppose m, n > N and let x be any point. Choose k/2N such that ix  k/2NI < 1/2N < b.
(3)
Then I gm.(x)  gn(x) I
I gm(x)  gm.(k/2N)I + I gm(k/2N)  gn(k/2N) I + I gn(k/2N)  gn (x)I
< e/3 + 2/2N + e/3 < e/3 + e/3 + e/3 = E.
(The estimates on the first and third terms follow from (1) and (3). The estimate on the second term follows from the construction of the gn and We have shown that the sequence gn is uniformly Cauchy. In particular, the gn converge pointwise to some limit h. Since the sequence is uniformly Cauchy, the convergence is uniform, and the limit h is continuous. Thus the sequence gn, a subsequence of the original sequence f, converges in the
Exercises 30
135
space C[O, 1] (under the sup metric). Since .F is closed, the limit h lies in T. Therefore F is compact.
30.3. The AscoliArzela Theorem. Arzela generalized Ascoli's Theorem from a bounded interval to any compact metric space. Much work in analysis has centered on finding nice spaces of functions with good compactness properties.
Exercises 30 Give an example. of an equicontinuous sequence of functions in C[0,1] which has no convergent subsequence. 1.
2. Give an example of a bounded sequence of functions in C[O, 1] which has no convergent subsequence. 3.
(Saroj Bhattarai and Brian Simanek). Prove the converse of Ascoli's
Theorem.
Hint: For the hard part, equicontinuity, use proof by contradiction: assume that for some e > 0 there are points in [0, 1] and functions in f such that xn  yn I < 1/n but I f (xn)  f (ym) I > E. 4. Prove that the set of "Lipschitz" functions in C[O,1] satisfying
If(x)f(y)I
5. Existence of shortest paths. Let p, q be two points on a smooth compact connected surface S in JR3 (such as a curvy sphere or torus). A path from p to q in S of length L parameterized by arclength is in particular a function f : [0,1] * S C lR3 for which I f (x)  f (y) I <_ L I x y l.
a. Prove that given a sequence of such paths with lengths converging to the infimum length Lo, there is a convergent subsequence (in the sup metric). b. Assuming (as is true) that length is "lowersemicontinuous," i.e., that length lim f,, < lim inf length
conclude that there is a shortest path from p to q.
Partial Solutions to Exercises
Chapter 1. 1.1. F, T, T, T. 1.2. Hint: It's easiest to answer, "For all x except... "
1.3. a, c. 1.9a. bijective.
Chapter 2. 2.1a. S is uncountable; otherwise IR, as the union of two countable sets, S and Q, would be countable.
Chapter 3. 3.1. Converges to 0.
137
Partial Solutions to Exercises
138
3.11. Given e > 0, choose N > 1/s. Then if n > N,
Ian,01=11/n01=1/n< 1/N<s. 3.19a. R. 3.21. False.
Chapter 4. 4.1. There are lots of examples, such as the greatest integer less than or equal to x or the characteristic function Xz of the integers. (Note that the exercise asks for a function defined on all of R.)
4.7. Suppose that f and g are continuous. By definition, given a point p, lim f x*p
(x) = f (p)
and
lim g(x) = g(p)
x>p
Hence, by Proposition 4.6(2), lim (f + g)(x) = f(p) + g(p) = (f + g)(p)
Therefore f + g is continuous.
Chapter 5. 5.1. Neither, closed, open, open.
5.5. {0,1}, (0,1), [0,1]. 5.10. Since "or" is always inclusive, it suffices to show that if p in S is not a boundary point, then p is an interior point. But if p in S is not a boundary
point, then p E S  8S = int S.
5.11. First note that the interior of S is an open subset of S. Indeed, if p E int S, then by definition p V 3S, and hence some small ball B1 about p is contained in S. A smaller ball B2 about p is contained in S  8S because if a boundary point of S were contained in B2, a point of So would lie in B1. Hence, by definition int S = S  8S is open. Now let T be any open subset of S. T cannot contain any points of 8S because a ball about such
Partial Solutions to Exercises
139
a point contains points not in S and hence not in T. Hence, T is contained in S  9,S = int S. Therefore, int S is the largest open set contained in S.
5.13. Suppose that p E 8S is not an isolated point of S. Then a ball of radius 1/n about p contains another point an of S, and p is the limit of the sequence an. Therefore p is an accumulation point of S.
Chapter 6. 6.1. Suppose that f and g are continuous. Let xn be a sequence of points converging to a point p. By 6.1(2), f (xn) > f (p) Hence, by Proposition 3.6(2),
.
and 9(xn) a 9(p)
(f + 9)(xn)  f(xn) + 9(xn)  f(p) + 9(p) _ (f + 9)(p)
Therefore, by 6.1(2), f + g is continuous.
6.3. The idea is that nearby integers have nearby values of f because there aren't any nearby integers! Consider an integer p. To check definition (1), note that given any e,
you can take 6 = 1, and then Ix  pI < S implies that x = p, so that  f (p) I = o < E. To check definition (2), note that any sequence of integers approaching p is eventually just p, p, p, .... Hence, the corresponding sequence of values is eventually just f (p), f (p), f (p), ... , which of course converges to f (p). To check definition (3), just note that f lU contains {p}, which is the intersection of a small ball about p with the domain Z. If (X)
Chapter 7. 7.1. f o g(x) is x for part b, but not for part a.
Chapter 8. 8.3. Let an be an increasing sequence in IR which is bounded above. Since it is increasing, it is bounded below by al. By Theorem 8.3, it has a convergent subsequence. Since the original sequence is increasing, its terms lie between
Partial Solutions to Exercises
140
terms of the subsequence and, therefore, it also converges to the same)imit as the subsequence.
8.6. Let an be a Cauchy sequence. By Exercise 3.18, an is bounded. By Theorem 8.3, an has a subsequence converging to a limit L. We claim that an converges to L. Given e > 0, choose N so that for some m > N, lam  L I < s/2 and for all m, n > N, Ian  an I < s/2. Then for all n > N,
Ian  LI < Ian  aml + Iam  LI < e/2+e/2=e. 8.7. 1, +oo, oo, 1, 2, 1.
Chapter 9. 9.1. Let S and T be compact subsets of ][8n. Since S and T are both closed, S fl T is closed. Since S and T are both bounded, S fl T is bounded. Therefore S fl T is compact.
9.14. Immediately, from the definition, sup S > s for all sin S. If a < sup S, then there is a point of S larger than a, and hence a point of S larger than a, so that a fails to satisfy a > s for all s in S.
Chapter 10. 10.5. Since g is continuous, g(K) is compact by Theorem 10.1. Likewise since f is continuous, f (g (K)) = (fog) (K) is compact. Of course, you need to assume that g(K) is contained in the domain of f.
Chapter 11. 11.3. Suppose that f and g are uniformly continuous. Since f is uniformly continuous, given e > 0, we can choose Si > 0 such that (*)
Iyi  x1 I < S1
I f (yi)  f (xi) I < e.
Since g is uniformly continuous, we can now choose 5 > 0 such that whenever
I y  xI < S, then I g(y)  g(x) I < Si, which in turn implies that I f (g (y)) f (g(x)) I < e, by (*) with yi = g(y) and xl = g(x). Thus Iy  XI < S =
I(f 0 g) (Y) .(f 0 g)(x)I < s+
Partial Solutions to Exercises
141
and f o g is uniformly continuous.
Chapter 12. 12.1. The disjoint open sets U1 = (oo, 1/2) and U2 = (1/2, oo) separate the integers into two nonempty pieces.
12.7. Suppose that f takes on two different values, yl and y2. Choose an irrational number y3 between yl and y2. Then the open sets U1 = (oo, y3) and U2 = (y3i oo) separate f (118) into two nonempty pieces. This contradicts
Theorem 12.4, which says that the continuous image of a connected set is connected.
12.8. By Proposition 12.2, Theorem 12.4, and Proposition 12.3, it must be an interval. By Theorems 10.1 and 9.2, it must be a closed interval.
12.11. First suppose that S is totally disconnected. By definition, S has at least two points. If S contained an interval, a separation of two points of the interval. would prove the interval disconnected, a contradiction. Conversely, suppose that S has two points but no interval. Let p1i p2 be distinct points of S. Since S does not contain an interval, there is a point p3 between pl and p2 not in S. Then the open sets U1 = (oo,p3) and U2 = (p3i oo) provide the required separation to show that S is totally disconnected.
Chapter 13. 13.1. Let a be a point of the Cantor set. Let a,,, be one of the endpoints of the interval of S,, containing a. (If one of the endpoints is a, choose the other one.) Then a,, is in C and a is the limit of the sequence a,, because the length of the intervals goes to 0.
Chapter 14. 14.3. Since [a, b] is compact (Theorem 9.2), every continuous image is compact (Theorem 10.1), and hence every continuous function has a maximum (Corollary 10.2). This fact is used in the proof of Rolle's Theorem (14.3), to find a place where the derivative vanishes. Rolle's Theorem leads immediately to the Mean Value Theorem (14.4) and finally to Corollary 14.5,
Partial Solutions to Exercises
142
which says that on an interval where f' is always 0, f is constant. This final result will be a key ingredient in the proof of the Fundamental Theorem of Calculus (16.1).
Chapter 15. 15.1. [6, 10].
15.4. Let f be a nonnegative function with Riemann integral equal to A. Chop the interval up into identical subintervals with Ax small enough to guarantee that every Riemann sum is less than A + 1. Since every contribution is nonnegative, each subinterval contributes at most A + 1 to the Riemann sum. Therefore, on every subinterval f is bounded above by (A + 1)/Ax. 15.6. An unbounded interval cannot be chopped up into finitely many small intervals.
15.7. Yes. There will always be just one subinterval on which the chosen f (x) could be 0 or 1, and as the subinterval width shrinks, the effect becomes negligible. Similarly, finitely many discontinuities are OK.
Chapter 16. 16.4. f (a).
Chapter 17. 17.3. A simple hypothesis is that f be bounded. 17.8. Given E > 0, choose S such that
Ix  yl < S=> If(x)f(y)l <E/3. Second, choose M such that 1/M < S and C/M < E/3. Third, choose N such that
n>N
fn(k/M)  f (k/M) I < E/3 (k=0,1,2,.,M)
Partial Solutions to Exercises
143
Now suppose that n > N. Given x, choose k such that Ix  k/MI < 1/M, and, hence, by the Lipschitz condition
I fn(x)  fn(k/M)I < C/M < e/3. Now
Ifn(x) .f(x)I < fn(x) .f.(klM)I +Ifn(k/M) .f(k/M)I +If(k/M) .f(x)I < C/M + e/3 +,/3 < e/3 + e/3 + s/3 = E.
Chapter 18. 18.4. Compute by switching the order of integration. Justify by Fubini's Theorem because the integral of the absolute value is at most the integral of (ir/3)(10)(1) = 10ir/3, which integral is (10)(7r/3)(107r/3) < oo. 18.8. In justifying the use of Leibniz's Rule, note that for y near 0, 8
1
ay x2 +Y2
2y (x2 + y2)2
whose integral even from 1 to oo is finite.
Chapter 19. 19.1. Converges to 1/9.
Chapter 20. 20.1. 1, 1/3, [oo, +oo] ,+00.
Chapter 21. 21.1b. TRUE.
<
1 4
= 9(x),
Partial Solutions to Exercises
144
Chapter 22. 22.2. sin x + 0 + 0 + , as you would guess. (If you graph the functions sin x and cos nx or sin nx, you might see how things cancel to make the integral of the product vanish; or you could just believe the statement in 22.3 that "cos nx and sin nx ... turn out to be orthonormal functions," see also Section 22.7; or later you could just use Exercise 24.2.
22.3. By integration by parts,
i
7r
x cos(nx) = n2 [cos(n7r)  1], 7r
x sin(nx)
cos(nir),
Jo n f" X cos(nx) = 27r cos(n7rf), 2
n
Jo
x2 sin(nx) _  2 cos(n7r) +
23
[cos(n7r)  1].
Now use formulae 22.2(2).
Chapter 23. 23.1.
7r
(1 sin x

37
sin 3x + 5 sin 5x 
)
23.2. a (i sin xcos t   sin 3x cos 3t + 5 sin 5x cos 5t  . 23.5. First compute the Fourier series for f (t):
+ 1
4
Chapter 24. No solutions.
00
sin 2 cos nt + (1 cos !Mr) sin nt
n_1
n7r
)
Partial Solutions to Exercises
145
Chapter 25. 25.1a. Easiest to use ratio test.
25.5. E°° (1)n+1 (x)" = (x 1) 
x
21)2 + (x 31)s
Chapter 26. 26.1a. F(5/2) = (3/2)r(3/2) = (3/2)(1/2)r(1/2) _ (3/4)v. 26.2. (8/15)7r2r5, (1/6)7r3r6. 26.3. 47rr2, 27r2r3, (8/3)7r2r4.
Chapter 27. 27.1. Two are metrics.
27.2. Alexandra Constantine found 67. Here are a few. First "pat." Then by rule (1) "at." By rule (2) "spat," "phat," "pate," and "path." By rule (3)
bat, cat, fat, hat, mat, rat, sat, tat, vat, pet, pit, pot, put, pad, pal, pan, par; paw, pax, pay. By rule (4) "apt." Including gibberish, there are 1(pat) + 3 + (4 x 26  3) + 3 x 25 + 2 = 182. (The 3 is from double counting ppat, paat, and patt.)
Chapter 28. 28.1. One converges and one diverges.
28.2. Suppose that there are two different limits L1 and L2, and let e = p(Li, L2). Choose N such that n > N = p(an, Ll) < e/2 and p(an, L2) < e/2. Then p(Li, L2)
p(Li, an) + p(an, L2) < e/2 + e/2 = s = p(L1, L2),
Partial Solutions to Exercises
146
a contradiction. To show that the sequence is bounded, choose N such that
n>N=p(an,L) <1. Let M = max{1, p(an, L) : n < N}. Then all of the terms lie inside B(L, M). 28.7. open, closed, closed.
28.16. 1, 1.4, 1.414,
...
(converging to vr2 in IR) does not converge in Q.
28.17. A Cauchy sequence is contained in a ball, which is compact. Hence, some subsequence converges to a limit L. Since the original sequence is Cauchy, it must converge to L.
28.18. Let fn be a Cauchy sequence of functions in C[0,1]. For each point x in [0, 1], fn(x) is a Cauchy sequence of real numbers, which converges to a limit f (x) because ]R is complete. In other words, fn converges to f pointwise. To prove uniform convergence, given e > 0, choose N such that m, n > N implies that I f. (x)  fn (x) I < e/2 for all x. Now given any x, choose m > N (depending on x) such that Ifm(x)  f (x) I < e/2. It follows that for n > N, I fn (x)  f (x) I < e, uniform convergence. Finally, as a uniform limit of continuous functions, f is continuous. 28.19. yes.
Chapter 29. 29.3. The proofs of Theorem 10.1 and Corollary 10.2 hold in metric spaces.
Chapter 30. No solutions.
Greek Letters a
A alpha
Q B beta ry
r gamma
b A delta
v
N nu
E xi
o 0 omicron H pi
7r
e
E
epsilon
p P rho
S
Z
zeta
o
B
H eta O theta
t
I
77
iota
n K kappa A A lambda
µ M mu
E sigma
r T tau
v T upsilon cp
D
phi
X X chi
V) ' psi w
S2
omega
147
Index composition of function,. 3a
L1 correspondence, 7
abbreviatiotu. G absolute convergence. 89 accumulation point. 1& 126 AlSabah, Nasser. viii alternating series. t32 Armstrong, Zan. 411
Ascoli's Theorem. 133. 1.3
ball B(n, r), 27 Bernoulli, Daniel, 10.i. 109 Bhattarai, Saroj, 135 bijectivu, L
Bohnhorst. Kristin, 13 13olzanoN'eierstrass. 3K, IL 4 K 1:311 boundary. ')9 126 bounded, 15. 38. 41 66. 12 i
Burger. Ed. iv. viii ('[0. 1 122. 11Et.. 121. 128, 1311 133. L3a calculus. 511
22. at
closed sets, 28. 29 1211
closed sets, unions and intersections, 3Q closure, 30, 126 comparison test. 81i complement. 3. 1i. 22 complete. 125
converge absolutely. tom1, 13
converge conditionally. 81 converge polmwrrx:, Z5 converge uniformly, 75 125 converse, ti Corvetti. Candice. dfi Costa. Tom. viii countable. 9 countable subcover, 12 countable union. 111 dense. 32 derivative. 61
differentiable. lil
Cartesian pro..luct. 111 Cauchy sequence. 20. 39 48 66_6 125. 131
compact. 9.1.. 45. 1291
Constantine, Alexandra. 145 contains, ti continuous. 21 continuous functions. 33 cuntrap ositive, 5 converge, l_t. 85. 43. 125
difference. G
Cantor function. 63 Cantor set, 53 at Cantor, G(org. U
characteristic function circle, 22
conditional convergence. ts9 connected. .19
differentiation of power series, 915 dimension, a5 disc. 27L disconnected, totally, 50 distance. 3. L21
diverge. L4. gel it)
domain. Z Dominated Convergence Theorem. at
Dunne, Ed. viii email address, viii English. 5
149
Index
150
equicontinuous, 133 Euler's identity. 113 exponential function, 111
logarithm, 113 logic, 5 lowersemicontinuous, 135
Fourier coefficients, 100 Fourier series, 99. 102, 109 fractals, 53 Fubini's Theorem, 82 functions, 1 Fundamental Theorem of Calculus. 71
Mandelbrot, Benoit, 56
Gamma Function r(x). U.S Garrity, Tom. viii
metric, Euclidean, 4 metric, sup, 122, 125 metric, taxicab, 121 minimum, 42. 46, fil Murphy, Erin, iv
geometric series, 8fi Gibbs phenomenon, LID greatest lower bound, 44 Greek letters. L47
Hadamard formula, 95 harmonic series. 86. 87 Heine Borel, 41, 45, 134 image, 2 implication, 5 infimum, 44 infinite sets, 9 injective, Z integers, 3 integrable, 65, 61 interior, 30. 126 Intermediate Value Theorem, 5Q
maximum, 42, 4446, 111 Mean Value Theorem, 62. 63, 72 measurability, 82 measure, 54 Menger sponge, 5Si metric space, 119, 121, 125 129.
natural numbers, 3 Newton, vii, 60. 106 nonintegrable functions. fib onetoone, 7 onto, 7 open cover, iv, 41, 134 open sets, vii, 28. 29, 126
open sets, unions and intersections, 3Q "or". 5
ptest, 86 power series, 93
intersect, 6
radius of convergence, 94
intersections, 30, 43
range, 7 rates of growth, 1H ratio test, 91 rationals, 3. 22 real analytic, 94. 95 real numbers, 1, 3 rearrangement, 89 relatively open, 34 resonance, 111 Riemann integral, 65 Riemann sum, 65 root test, 95
interval, 27. 49 intervals, 3
Inverse Function Theorem, 114 inverse image, 7, 8
irrationals, 3 4. 8 isolated point, 311, 126 JPEG. 1112
least upper bound, 44 Lebesgue integral. 81 I.ebesgue's Dominated Convergence Theorem, 81 Leibniz, vii, &fl Leibniz's formula for ^.r, 97, 144
selfsimilar, 55 sequence, 13, 125 sequence of functions, 75, 125
Ieibniz's Rule, 82 length, 8 lunit. 1 13, 14, 18. 125
series, 85
limit of function, 2.1 limit, unique, 15
shortest paths, 135 Sierpinski's carpet, 56 Sil a, Cesar, iv Simanek, Brian, 135 sine and cosine functions, 113
liminf, 39 lim sup, 39
Lipschitz constant. 79 Lipschitz function, 79, 1.35
series Y(1/n2). 101 sets, 6
sphere, 2,7
Index
springs. 106
Stirling's Approximation to n!, Lli Stokes's 'T'heorem, 12 strings. 105 subsequence, 32 subset. b
supremum, 3:3 surjective. 1 switch limit and integral, 77, f1.1
switch order of integration. 82 Tacoma Narrows suspension bridge, LU Tapp, Kris. viii Taylor's formula, 95, 911
topolo y. 25, 3! 126 triangle inequality, 4, 121
uncountable, I1 51 uniform continuity, 3i unions, .30, 13 volumes of 71balls. 11
Voss, It. F., wave equation. 1116
webpage. iv. viii Weicrstrays Altest. 9,1 words W, 122. 126, 121
151