MATH10242 Sequences and Series
M. Coleman1
1Based on the notes of Profs A. J. Wilkie, J. T. Stafford and M. Prest
1
Contents
0.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1 Before We Begin 6
1.1 Some Reminders about Mathematical Notation . . . . . . . . . . . . . . 6
1.1.1 Special sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Set theory notation . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Logical notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.4 Greek letters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.5 Where we’re headed and some things we’ll see on the way . . . . 7
1.1.6 Basic properties of the real numbers . . . . . . . . . . . . . . . . . 9
1.1.7 The Integer Part (or ‘Floor’) Function . . . . . . . . . . . . . . . 14
I Sequences 16
2 Convergence 17
2.1 What is a Sequence? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 The Triangle Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 The Definition of Convergence . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 The Completeness Property for R . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Some General Theorems about Convergence . . . . . . . . . . . . . . . . 30
2.6 Exponentiation - a digression . . . . . . . . . . . . . . . . . . . . . . . . 32
3 The Calculation of Limits 35
3.1 The Sandwich Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 The Algebra of Limits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 Some Special Sequences 45
2
4.1 Basic Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 New Sequences from Old . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Newton’s Method for Finding Roots of Equations - optional . . . . . . . 58
5 Divergence 61
5.1 Sequences that Tend to Infinity . . . . . . . . . . . . . . . . . . . . . . . 61
6 Subsequences 65
6.1 The Subsequence Test for Non-Convergence . . . . . . . . . . . . . . . . 65
6.2 Cauchy Sequences and the Bolzano-Weierstrass Theorem . . . . . . . . . 69
6.2.1 Proofs for the section - optional . . . . . . . . . . . . . . . . . . . 70
7 L’Hoˆpital’s Rule 75
7.1 L’Hoˆpital’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II Series 79
8 Introduction to Series 80
8.1 The Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9 Series with Non-Negative Terms 86
9.1 The Basic Theory of Series with Non-Negative Terms . . . . . . . . . . . 86
9.2 The Integral Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
10 Series with Positive and Negative Terms 99
10.1 Alternating Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
10.2 Absolute Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
11 Power Series 107
11.1 The Radius of Convergence of a Power Series . . . . . . . . . . . . . . . . 108
12 Further Results on Power Series - further reading 113
12.1 More General Taylor Series. . . . . . . . . . . . . . . . . . . . . . . . . . 113
12.2 Rearranging Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
12.3 Analytic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3
0.1 Introduction
Maybe you can see that
1 +
1
2
+
1
4
+
1
8
+ · · ·+ 1
2n
+ · · · = 2
and even that
1 +
1
3
+
1
9
+
1
27
+ · · ·+ 1
3n
+ · · · = 3
2
.
But what exactly do these formulas mean? What does it mean to add infinitely many
numbers together? Is that even meaningful?
You might recognize the numbers above as being terms of geometric progressions and
know the relevant general formula, for |x| < 1,
1 + x+ x2 + x3 + · · ·+ xn + · · · = 1
1− x.
But how do we prove this? And what if |x| ≥ 1?
In this course we shall answer these, and related, questions. In particular, we shall
give a rigorous definition of what it means to add up infinitely many numbers and then
we shall find rules and procedures for finding the sum in a wide range of particular cases.
Here are some more, rather remarkable, such formulas:
1 +
1
4
+
1
9
+
1
16
+ · · ·+ 1
n2
+ · · · = pi
2
6
,
1− 1
2
+
1
3
− 1
4
+ · · ·+ (−1)
n+1
n
+ · · · = ln 2,
1 +
1
2
+
1
3
+
1
4
+ · · ·+ 1
n
+ · · · =∞.
We shall prove the second and third of these formulas in this course unit, but the
first one is too difficult and will be done in your lectures on real and complex analysis in
the second year. Here, “real analysis” means the study of functions from real numbers
to real numbers, from the point of view of developing a rigorous foundation for calculus
(differentiation and integration) and for other infinite processes.2 The study of sequences
2and “complex analysis” refers to the complex numbers, not (necessarily) complexity in the sense of
“complicated”!
4
and series is the first step in this programme.
This also means there are two contrasting aspects to this course. On the one hand we
will develop the machinery to produce formulas like the ones above. On the other hand
it is also crucial to understand the theory that lies behind that machinery. This rigorous
approach forms the second aspect of the course—and is in turn the first step in providing
a solid foundation for real analysis.
5
Chapter 1
Before We Begin
1.1 Some Reminders about Mathematical Notation
1.1.1 Special sets
We use the following notation throughout the course.
R - the set of real numbers;
R+ - the set of strictly positive real numbers, i.e. R+ = {x ∈ R : x > 0};
Q - the set of rational numbers;
Z - the set of integers (positive, negative and 0);
N (or Z+) - the set of natural numbers, or positive integers {x ∈ Z : x > 0}. (In this
course, we do not count 0 as a natural number. We can use some other notation like Z≥0
for the set of integers greater than or equal to 0.)
∅ - the empty set.
1.1.2 Set theory notation
The expression “x ∈ X” means x is an element (or member) of the set X. For sets A,
B, we write A ⊆ B to mean that A is a subset of B (i.e. every element of A is also an
element of B). Thus ∅ ⊆ N ⊆ Z ⊆ Q ⊆ R.
Standard intervals in R: if a, b ∈ R with a ≤ b, then
• (a, b) ={x ∈ R : a < x < b}; • [a, b) ={x ∈ R : a ≤ x < b};
• (a, b] ={x ∈ R : a < x ≤ b}; • [a, b] ={x ∈ R : a ≤ x ≤ b};
6
• (a,∞) ={x ∈ R : a < x}; • [a,∞) ={x ∈ R : a ≤ x};
• (−∞, b) ={x ∈ R : x < b}; • (−∞, b] ={x ∈ R : x ≤ b};
• (−∞,∞) = R.
1.1.3 Logical notation
The expression “∀x ...” means “for all x ...” and “∃x ...” means “there exists at least one
x such that ...”. These are usually used in the context “∀x ∈ A ...” meaning “for all
elements x of the set A ...”, and “∃x ∈ A ...” meaning “there exists at least one element
x in the set A such that ...”.
Thus, for example, “∀x ∈ R x > 1” means “for all real numbers x, x is greater than
1” (which happens to be false) and “∃x ∈ R x > 1” means “there exists a real number x
such that x is greater than 1” (which happens to be true).
1.1.4 Greek letters
The two most commonly used Greek letters in this course are δ (delta) and ε (epsilon).
They are reserved exclusively for (usually small) positive real numbers.
Others are α (alpha), β (beta), γ (gamma), λ (lambda), θ (theta-usually an angle),
η (eta) and Σ (capital sigma - the summation sign which will be used when we come to
study series in Part II).
1.1.5 Where we’re headed and some things we’ll see on the way
In Part I we aim to understand the behaviour of infinite sequences of real numbers,
meaning what happens to the terms as we go further and further on in the sequence. Do
the terms all gradually get as close as we like to a limiting value (then the sequence is said
to converge to that value) or not? The “conceptual” aim here is to really understand what
this means. To do that, we have to be precise and avoid some plausible but misleading
ideas. It’s worthwhile trying to develop, and refine, your own “pictures” of what’s going
on. We also have to understand the precise definition well enough to be able to use it
when we calculate examples, though we will gradually build up a stock of general results
(the “Algebra of Limits”), general techniques and particular cases, so that we don’t have
to think so hard when faced with the next example.
Part II is about “infinite sums” of real numbers: how we can make a sensible definition
of that vague idea and then how we can calculate the value of an infinite sum - if it exists.
7
We also need to be able to tell whether a particular “infinite sum” does or doesn’t make
sense/exist. Sequences appear here in two ways: first as the sequence of numbers to be
“added up” (and the order of adding up does matter, as we shall see); second as a crucial
ingredient in the actual definition of an “infinite sum” (“infinite series” is the official
term). What we actually do is add up just the first n terms of such an infinite series -
call this value the n-th partial sum - and then see what happens to this sequence (note)
of partial sums as n gets bigger and bigger. If that sequence of partial sums converges to
a limit then that limit is what we define to be the sum of the infinite series. Hopefully
that makes sense to you and seems like it should be the right definition to use. Anyway,
it works and, again, we have the conceptual aspect to get to grips with as well as various
techniques that we can (try to) use in computations of examples.
Here are some of the things we prove about our concept of limit: a sequence can have
at most one limit; if a sequence is increasing but never gets beyond a certain value, then
it has a limit; if a sequence is squeezed between two other sequences which have the same
limit l, then it has limit l. These properties help clarify the concept and are frequently
used in arguments and calculations. We also show arithmetic properties like: if we have
two sequences, each with a limit, and produce a new sequence by adding corresponding
terms, then this new sequence has a limit which is, as you might expect, the sum of the
limits of the two sequences we started with.
Then we turn to methods of calculating limits. We compare standard functions (poly-
nomials, logs, exponentials, factorials, ...) according to how quickly they grow, but ac-
cording to a very coarse measure - their “order” of growth, rather than rate of growth
(i.e. derivative). That lets us see which functions in a complicated expression for the n-th
term of a sequence are most important in calculating the limit of the sequence. There
will be lots of examples, so that you can gain some facility in computing limits, and there
are various helpful results, L’Hoˆpital’s Rule being particularly useful.
While the properties of sequences are, at least once you’ve absorbed the concept,
quite natural, infinite series hold quite a few surprises and really illustrate the need
to be careful about definitions in mathematics (many mathematicians made errors by
mishandling infinite series, especially before the concepts were properly worked out in
the 1800s). Given an infinite series, there are two questions: does it have a sum? (then
we say that it “converges”, meaning that the sequence of partial sums has a limit - the
value of that infinite sum) and, if so, what is the value of the sum? There are a few series
(e.g. a geometric series with ratio < 1) where we can quite easily compute the value but,
in general this is hard. It is considerably easier to determine whether a series has a sum
or not by comparing it with a series we already know about. Indeed, the main test for
convergence that we will use, the Ratio Test, is basically comparison with a geometric
8
series.
Many infinite series that turn up naturally are “alternating”, meaning that the terms
are alternately positive and negative. So, in contrast with the corresponding series where
all the terms are made positive, there’s more chance of an alternating sequence converging,
because the terms partly cancel each other out. Indeed, remarkably, it’s certain provided
the absolute values of the individual terms shrink monotonically to 0!
We’ll finish with power series: infinite series where each term involves some variable
x - you could think of these as “infinite polynomials in x”. Whether or not a power
series converges (i.e. has a sum), depends very much on the value of x, convergence being
more likely for smaller values of x. In fact, the picture is as good as it could be: there’s
a certain “radius of convergence” R (which could be 0 or ∞ or anything in between,
depending on the series) such that, within that radius we have convergence, outside we
have divergence, and on the boundary (x = ±R) it could go either way for each boundary
point (so we have to do some more work there).
1.1.6 Basic properties of the real numbers
It will be assumed that you are familiar with the elementary properties of N, Z and Q
that were covered last semester in MATH10101/10111. These include, in particular, the
basic facts about the arithmetic of the integers and a familiarity with the Principle of
Mathematical Induction. One may then proceed to construct the set R of real numbers.
There are many ways of doing this which, remarkably, all turn out to be equivalent in a
sense that can be made mathematically precise. One method with which you should be
familiar is to use infinite decimal expansions as described in Section 13.3 of [PJE].
Here we extract some of the basic arithmetic and order properties of the real numbers.
First, just as for the set of rational numbers, R is a field. That means that it satisfies
the following conditions.
(A0) ∀a, b ∈ R one can form the sum a+ b and the product a · b (also written as just ab).
We have that a+ b ∈ R and a · b ∈ R; (existence of two binary operations.)
Properties of addition.
(A1) ∀a, b, c ∈ R, a+ (b+ c) = (a+ b) + c (associativity of +);
(A2) ∀a, b ∈ R, a+ b = b+ a (commutativity of +);
9
(A3) ∃0 ∈ R,∀a ∈ R, a+ 0 = 0 + a = a (additive identity);
(A4) ∀a ∈ R, there exists an element in R (denoted −a) such
that a+ (−a) = 0 = (−a) + a; (additive inverse);
Properties of multiplication.
(A5) ∀a, b, c ∈ R, a · (b · c) = (a · b) · c (associativity of ·);
(A6) ∀a, b ∈ R, a · b = b · a (commutativity of ·);
(A7) ∃1 ∈ R,∀a ∈ R, a · 1 = 1 · a = a (multiplicative identity);
(A8) ∀a ∈ R, if a 6= 0 then there exists an element in R (denoted a−1
or 1/a) such that a · a−1 = 1 = a−1 · a (multiplicative inverse);
Combining the two operations.
(A9) ∀a, b, c ∈ R, a · (b+ c) = a · b+ a · c (the distributive law).
These axioms (A0)-(A9) list the basic arithmetic/algebraic properties that hold in
R and from which all the other such properties may be deduced.
Importantly,
Example A The identities and inverses, both additive and multiplicative, are unique.
Solution If 0 and 0′ are two additive identities then
0 = 0 + 0′ since 0′ is an additive identity
= 0′ since 0 is an additive identity.
Thus 0 = 0′, the identity is unique.
If a has two additive inverses, b and c then 0 = a+ b since b is the additive inverse of
a. Adding c to both sides gives
c+ 0 = c+ (a+ b).
On the left use that 0 is the additive identity and on the right use associativity, so
c = (c+ a) + b.
10
Then c is the additive inverse of a so
c = 0 + b.
Finally, 0 is the additive identity so c = b, and the inverse is unique.
I leave the proofs for the multiplicative identities and inverses to the students.
This uniqueness of identities and inverses is important. It will used in some of the
following proofs. Consider 0, the additive identity; what can be said of the multiplication
0 · x for x ∈ R? Similarly, −1 is the additive inverse of 1, so what can be said of the
multiplication (−1) ·x? The only axiom that combines addition and multiplication is the
distributive law and so it should be no surprise it is used within the proof of
Example B For all x ∈ R, 0 · x = 0 and (−1) · x = −x.
Solution Given x ∈ R,
0 · x = x · 0 (A6)
= x · (0 + 0) (A3)
= x · 0 + x · 0 (A9)
= 0 · x+ 0 · x (A6).
Add −(0 · x) to both sides.
0 = 0 · x+ (−(0 · x))
= (0 · x+ 0 · x) + (−(0 · x)) (A1)
= 0 · x+ (0 · x+ (−(0 · x))) (A4)
= 0 · x+ 0 (A3)
= 0 · x.
Next
x+ (−1) · x = 1 · x+ (−1) · x (A7)
= x · 1 + x · (−1) (A6)
= x · (1 +−1) (A9)
= x · 0 (A4)
= 0 · x (A6)
= 0,
11
by the first result of this example. This shows that (−1) · x is the additive inverse of x.
Yet, by Example A, the additive inverse of an element is unique. Thus (−1) ·x = −x.
The second result here can be generalised, for all x, y ∈ R,
(−x) · y = −(x · y) = x · (−y).
What about inverses of inverses?
Example C For all x ∈ R, −(−x) = x and, provided x 6= 0, (x−1)−1 = x.
Solution Left to student.
Or sums and products of additive inverses?
Example D For all x, y ∈ R, (−x) + (−y) = −(x+ y) and (−x) · (−y) = x · y.
Solution Left to student.
And a couple of often used results are
Theorem (Cancellation Law for Addition) If a, b and c ∈ R and a+ c = b+ c, then
a = b.
Theorem (Cancellation Law for Multiplication) If a, b and c ∈ R, c 6= 0 and ac = bc
then a = b.
Proofs Left to student.
For repeated multiplication we use the usual notation: for a ∈ R, a2 is an abbreviation
for a · a (similarly a3 is an abbreviation for a · (a · a), etc.).
Example 1.1.1. Prove the identity (x+ y)2 = x2 + 2xy + y2 above.
Solution We have
(x+ y)2 = (x+ y)(x+ y) (by definition),
= (x+ y) · x+ (x+ y) · y (by A9),
= x · (x+ y) + y · (x+ y) (by A6),
= x · x+ x · y + y · x+ y · y (by A9),
= x · x+ x · y + x · y + y · y (by A6),
= x · x+ 1 · (x · y) + 1 · (x · y) + y · y (by A7),
= x · x+ (1 + 1) · (x · y) + y · y (by A9 and A6),
= x · x+ 2 · (x · y) + y · y (by definition),
= x2 + 2xy + y2 (by definition).
12
Actually we have also used A1 many times here. This allowed us to ignore brackets
in expressions involving many + symbols.
Finally, for now, we can define two further binary operations on R:
Subtraction For all x, y ∈ R, x− y = x+ (−y),
Division For all x, y ∈ R, y 6= 0,
x÷ y
(
=
x
y
= x/y
)
= x · y−1.
Example For all s, t, x, y ∈ R with x, y 6= 0 we have
• (s− t)2 = s2 − 2st+ t2,
• (s− t)(s+ t) = s2 − t2,
• (s/x)(t/y) = (st)/(xy),
• (s/x) + (t/y) = (sy + tx)/(xy).
Solution Left to student.
Note that if we replace R in these axioms by Q then they still hold; that is, Q is also
a field (but Z is not since it fails (A8)). The point of giving a name (“field”) to an “arith-
metic system” where these hold is that many more examples appear in mathematics, so it
proved to be worth isolating these properties and investigating their general implications.
Other fields that you will have encountered by now are the complex numbers and the
integers modulo 5 (more generally, modulo any prime).
The real and rational numbers have some further properties not shared by, for exam-
ple, the complex numbers or integers modulo 5.
Namely, the real numbers form an ordered field. This means that we have a total
order relation < on R. All the properties of this relation and how it interacts with the
arithmetic operations follow from the following axioms:
(Ord 1) ∀a, b ∈ R, exactly one of the following is true: a < b or b < a or a = b;
(trichotomy)
(Ord 2) ∀a, b, c ∈ R, if a < b and b < c, then a < c; (transitivity)
(Ord 3) ∀a, b ∈ R, if a < b then ∀c ∈ R, a+ c < b+ c;
(Ord 4) ∀a, b ∈ R, if a < b then ∀d ∈ R+, a · d < b · d.
13
As usual, we write a ≤ b to mean either a = b or a < b.
You do not need to remember exactly which rules have been written down here. The
important point is just that this short list of properties is all that one needs in order to
be able to prove all the other standard facts about <. For example, we have:
Example 1.1.2. Let us prove that if x is positive (i.e. 0 < x) then −x is negative
(i.e. −x < 0). So suppose that 0 < x. Then by (Ord 3), 0 + (−x) < x + (−x).
Simplifying we get −x = 0 + (−x) < x+ (−x) = 0, as required.
Other facts that follow from these properties include:
∀x ∈ R x2 ≥ 0,
∀x, y ∈ R x ≤ y ⇔ −x ≥ −y, et cetera.
It left as an exercise to prove these facts using just the axioms (Ord 1–4). Also see
the first exercise sheet.
However, there are more subtle facts about the real numbers that cannot be deduced
from the axioms discussed so far. For example, consider the theorem that
√
2 is irrational.
This really contains two statements: first that
√
2 6∈ Q (that is, no rational number
squares to 2; this was proved in MATH10101/10111); second that there really is such a
number in R - there is a (positive) solution to the equation X2 − 2 = 0 in R. And this
definitely is an extra property of the real numbers—simply because it not true for the
rational numbers (which satisfies all the algebraic and order axioms that we listed above).
So, we need to formulate a property of R that expresses that there are no “missing
numbers” (like the “missing number” in Q where
√
2 should be). Of course, we have
to say what “numbers” should be there, in order to make sense of saying that some of
there are “missing”. The example of
√
2 might suggest that we should have “enough”
numbers so as to be able to take n-th roots of positive numbers and perhaps to solve
other polynomial equations and following that idea does lead to another field - the field
of real algebraic numbers - but we have a much stronger condition (“completeness”) in
mind here. We will introduce it in Chapter 2, just before we need it.
1.1.7 The Integer Part (or ‘Floor’) Function
From any of the standard constructions of the real numbers one has the fact that any
real number is sandwiched between two successive integers in the following precise sense:
∀x ∈ R, ∃n ∈ Z such that n ≤ x < n+ 1.
(The proof of the existence of n requires the Completeness axiom, discussed later.) The
14
integer n that appears here, the greatest integer less than or equal to x, is unique and
is denoted [x]; it is called the integer part of x. The function x 7→ [x] is called the
integer part function. Note that 0 ≤ x− [x] < 1.
Example 1.1.3. [1.47] = 1, [pi] = 3, [−1.47] = [−2].
Note Many people denote the greatest integer less than or equal to x by bxc, the floor
function. In a similar manner, we can talk of the least integer, greater than or equal to
x, denoted by dxe, the ceiling function.
We will often want to choose an integer larger than a given real number x. Instead
of using the ceiling function we will choose [x] + 1; this is not always the least integer
greater than or equal to x (consider when x is an integer) but it suffices for our needs.
15
Part I
Sequences
16
Chapter 2
Convergence
2.1 What is a Sequence?
Definition 2.1.1. A sequence is a list a1, a2, a3, . . . , an, . . . of real numbers labelled (or
indexed) by natural numbers. We usually write such a sequence as (an)n∈N, or as (an)n≥1
or just as (an). We say that an is the nth term of the sequence.
The word “sequence” suggests time, with the numbers occurring in temporal sequence:
first a1, then a2, et cetera. Indeed, some sequences arise this way, for instance as successive
approximations to some quantity we want to compute. Formally, a sequence is simply a
function f : N→ R, where we write an for f(n).
We shall be interested in the long term behaviour of sequences, i.e. the behaviour of
the numbers an when n is very large; in particular, do the approximations converge on
some value?
Example 2.1.2. Consider the sequence 1, 4, 9, 16, . . . n2, . . .. Here, the nth term is n2.
So we write the sequence as (n2)n≥1 or (n2)n≥1 or just (n2). What is the nth term of the
sequence 4, 9, 16, 25, . . .? What are the first few terms of the sequence
(
(n− 1)2)
n≥1?
Example 2.1.3. Consider the sequence 2, 3/2, 4/3, 5/4, . . . . Here, an = (n+ 1)/n. The
sequence is ((n+ 1)/n)n≥1.
Example 2.1.4. Consider the sequence −1, 1,−1, 1,−1, . . .. A precise and succinct way
of writing it is
(
(−1)n)
n≥1. The nth term is 1 if n is even and −1 if n is odd.
Example 2.1.5. Consider the sequence ((−1)n/3n)n≥1. The 5th term, for example, is
−1/243.
17
Example 2.1.6. Sometimes we might not have a precise formula for the nth term but
rather a rule for generating the sequence, E.g. consider the sequence 1, 1, 2, 3, 5, 8, 13, . . .,
which is specified by the rule a1 = a2 = 1 and, for n ≥ 3, an = an−1 + an−2. (This is the
Fibonacci sequence.)
Long term behaviour: In Examples 2.1.2 and 2.1.6 the terms get huge, with no bound
on their size (we shall say that they tend to ∞).
However, for 2.1.3, the 100th term is
101
100
= 1 +
1
100
,
the 1000th term is
1001
1000
= 1 +
1
1000
.
It looks as though the terms are getting closer and closer to 1. (Later we shall express
this by saying that ((n+ 1)/n)n≥1 converges to 1.)
In Example 2.1.4 , the terms alternate between −1 and 1 so don’t converge to a single
value.
In Example 2.1.5, the terms alternate between being positive and negative, but they
are also getting very small in absolute value (i.e. in their size when we ignore the minus
sign): so ((−1)n/3n)n≥1 converges to 0.
Before giving the precise definition of “convergence” of a sequence, we require some
technical properties of the modulus (i.e. absolute value) function.
We now make the convention that unless otherwise stated, all variables (x, y,
l, ε, δ ...) range over the set R of real numbers.
2.2 The Triangle Inequality
We define the modulus, |x| of x, also called the absolute value of x.
|x| =
x if x ≥ 0,−x if x < 0.
Note that |x| = max{x,−x}, so x ≤ |x| and −x ≤ |x|.
18
Theorem 2.2.1 (The Triangle Inequality). For all x, y, we have
|x+ y| ≤ |x|+ |y|.
Proof. We have x ≤ |x| and y ≤ |y|. Adding, we get x+ y ≤ |x|+ |y|.
Also, −x ≤ |x| and −y ≤ |y|, so −(x+ y) = (−x) + (−y) ≤ |x|+ |y|.
It follows that max{x+ y,−(x+ y)} ≤ |x|+ |y|, i.e. |x+ y| ≤ |x|+ |y|, as required.
Remark: For x, y ∈ R, |x−y| is the distance from x to y along the “line” R. The triangle
inequality is saying that the sum of the lengths of any two sides of a triangle is at least
as big as the length of the third side, as is made explicit in the following corollary. (Of
course we are dealing here with rather degenerate triangles: the name really comes from
the fact that in this form, the triangle inequality is also true for points in the plane.)
Corollary 2.2.2 (Also called the Triangle Inequality). For all a, b, c, we have
|a− c| ≤ |a− b|+ |b− c|.
Proof.
|a− c| = |(a− b) + (b− c)| ≤ |a− b|+ |b− c|
by Theorem 2.2.1 with x = (a− b) and y = (b− c)).
Lemma 2.2.3. Some further properties of the modulus function:
(a) ∀x, y |x · y| = |x| · |y| and, if y 6= 0,∣∣∣∣xy
∣∣∣∣ = |x||y| ;
(b) ∀x, y |x− y| ≥ ∣∣|x| − |y|∣∣;
(c) ∀x, l and ∀ε > 0, |x− l| < ε ⇐⇒ l − ε < x < l + ε.
Proof. Exercises: (a) - consider the cases; (b), (c) - see the Exercise Sheet for Week 3.

Now we come to the definition of what it means for a sequence (an)n≥1 to converge
to a real number l. We want a precise mathematical way of saying that “as n gets bigger
and bigger, an gets closer and closer to l” (in the sense the distance between an and l
tends towards 0).
19
2.3 The Definition of Convergence
Definition 2.3.1. We say that a sequence (an)n≥1 converges to the real number l if
the following holds:
∀ε > 0 ∃N ∈ N such that for all n ∈ N with n ≥ N we have |an − l| < ε.
Equivalently,
∀ε > 0,∃N ∈ N : ∀n ≥ 1, n ≥ N =⇒ |an − l| < ε.
We use various expressions and notations for when this holds:
• an tends to l as n tends to infinity, written an → l as n→∞.
• the limit of (an)n≥1 as n tends to infinity equals l, written limn→∞ an = l.
Example 2.3.2. Consider the sequence(
n+ 1
n
)
n≥1
of 2.1.3.
Claim: (n+ 1)/n→ 1 as n→∞.
Proof Let ε > 0 be given. The definition requires us to show that there is a natural
number N such that for all n ≥ N , ∣∣∣∣n+ 1n − 1
∣∣∣∣ < ε.
So we look for N so that ∀n ≥ N , |(1 + 1/n)− 1| < ε, which is equivalent to requiring
that ∀n ≥ N , |1/n| < ε.
The N here will depend on ε (in fact in this example, as in most, no choice of N will
work for all ε, so any choice of value for N will be in terms of ε). Since the last inequality
is equivalent to ∀n ≥ N , 1/ε < n we take N to be any natural number greater than 1/ε,
say for definiteness [ε−1] + 1.
Note i. Any N > 1/ε would have sufficed but, when you are required to show something
exists, I would recommend you exhibit an explicit example, such as [ε−1] + 1.
ii. The N depends inversely on ε; as ε gets smaller, the N gets larger. This is what we
would expect, if we want to terms of the sequence to be closer to the limit value then we
will have to look further along the sequence. Use this as a sanity check on your answers.
20
Example 2.3.3. Now consider the sequence(
(−1)n
3n
)
n≥1
of 2.1.5. The claim is that (−1)n/3n → 0 as n→∞.
Proof: Let ε > 0 be given. To prove the claim we must find N ∈ N so that ∀n ≥ N ,∣∣∣∣(−1)n3n − 0
∣∣∣∣ < ε.
In fact N = [ε−1] + 1 (which implies 1/N < ε) works here. For suppose that n ≥ N .
Then ∣∣∣∣(−1)n3n − 0
∣∣∣∣ = ∣∣∣∣(−1)n3n
∣∣∣∣ = |(−1)n||3n|
by Lemma 2.2.3(a)
=
1
3n
≤ 1
n
since it is easy to show (by induction) that ∀n ∈ N, 3n ≥ n. But 1/n ≤ 1/N < ε, and we
are done.
Note You could finish this example differently;∣∣∣∣(−1)n3n − 0
∣∣∣∣ = 13n ≤ 13N < ε
as long as 3N > 1/ε, i.e. N > log3 (1/ε). This choose N = [log3 (1/ε)]+1. Though we will
use the logarithm function in this course it will not be defined properly until next year,
thus I recommend keeping away from it if at all possible. Also, I would claim [ε−1] + 1
is ‘simpler’ than [log3 (1/ε)] + 1 thus I would further recommend continuing and giving
‘simple’ upper bounds for |an − l|, e.g. here I consider 1/N to be simpler than 1/3N ; that
it is larger is immaterial, all we require is that the final bound can be made smaller than
ε by taking N sufficiently large.
The definition of convergence is notoriously difficult for students to take in, and rather
few grasp it straight away, especially to the extent of being able to apply it. So here’s
a different, but equivalent, way of saying the same thing. Maybe one of the definitions
might make more sense to you than the other - it can be useful to look at something from
different angles to understand it. And, of course, the more examples you do, the more
quickly you will get the picture.
By Lemma 2.2.3(c) the condition |an − l| < ε is equivalent to saying that l − ε <
21
an < l + ε. This in turn is equivalent to saying that an ∈ (l − ε, l + ε). So, to say that
an → l as n → ∞ is saying that no matter how small an interval we take around l, the
terms of the sequence (an)n≥1 will eventually lie in it, meaning that, from some point on,
every term lies in that interval.
You might like to look at the formula for N (in terms of ε) in Example 2.3.2 and
check that (taking ε = 1/10),
n+ 1
n
∈
(
1− 1
10
, 1 +
1
10
)
for all n ≥ 11, and that (taking ε = 3/500)
n+ 1
n
∈
(
1− 3
500
, 1 +
3
500
)
for all n ≥ 167 (so, for ε = 3/500 we can take N = 167 or any integer ≥ 167 - the
definition of convergence doesn’t require us to choose the least N that will work).
Example 2.3.4. This is more of a non-example really. Consider the sequence ((−1)n)n≥1
(of 2.1.4). Then there is no l such that the terms will eventually all lie in the interval
(l− 1
2
, l+ 1
2
). This is because if l ≤ 1
2
then the interval does not contain the number 1, yet
infinitely many of the terms of the sequence are equal to 1, and if l ≥ 1
2
then the same
argument applies to the number −1. Hence there is no number l such that (−1)n → l as
n→∞.
In general, if there is no l such that an → l as n→∞ then we say that the sequence
(an)n≥1 does not converge or is divergent.
Example 2.3.5. Another non-example. Consider the sequence (n2)n≥1 of Example 2.1.2.
This does not converge either. Here is a rigorous proof of this fact directly using the
definition of convergence.
Proof Suppose, for a contradiction, that there is some l such that an → l as n → ∞.
Choose ε = 1 in Definition 2.3.1. So there must exist some N ∈ N such that |n2 − l| < 1
for all n ≥ N . In particular |N2 − l| < 1 and |(N + 1)2 − l| < 1. Therefore
|(N + 1)2 −N2| = |(N + 1)2 − l + l −N2| ≤ |(N + 1)2 − l|+ |l −N2|,
by the Triangle Inequality. But each of the terms in the last expression here is less than
1, so we get that |(N + 1)2 − N2| < 1 + 1 = 2. However, |(N + 1)2 −N2| = 2N + 1, so
2N + 1 < 2, which is absurd since N ≥ 1.
22
This last example is a particular case of a general theorem. Namely, if the set of terms
of a sequence is not bounded (as is certainly the case for the sequence (n2)n≥1) then it
cannot converge. We develop this remark precisely now.
Definition 2.3.6. Let S be any non-empty subset of R.
• We say that S is bounded above if there is a real number M such that ∀x ∈ S,
x ≤M . Such an M is an upper bound for S.
• Similarly, S is bounded below if there is a real number m such that ∀x ∈ S,
x ≥ m. Such an m is a lower bound for S.
• If S is both bounded above and bounded below, then S is bounded.
Example 2.3.7. (1) Let S = {17,−6,−25, 25, 0}. Then S is bounded: an upper bound is
25 (or any larger number) and a lower bound is −25 (or any smaller number). In fact
one can show easily by induction on the size of X that if X is a non-empty, finite subset
of R then X is bounded.
(2) Intervals like (a, b] or [a, b], etc, for a < b are bounded above, and below, by a,
respectively b. However an interval like (a,∞) is only bounded below.
(3) Let S = {x ∈ R : x2 < 2}. Since 1.52 > 2 it follows that if x2 < 2 then−1.5 < x < 1.5.
Of course there are better bounds, but this is certainly sufficient to show that S is
bounded.
Applying this to the set {an : n ∈ N} of terms of a sequence we make the following
definition.
Definition 2.3.8. A sequence (an)n≥1 is bounded if there exists M ∈ R+ such that for
all n ∈ N, |an| ≤M .
Theorem 2.3.9 (Convergent implies Bounded). Suppose that (an)n≥1 is a convergent
sequence (i.e. for some l, an → l as n→∞). Then (an)n≥1 is a bounded sequence.
Proof. Choose l so that an → l as n → ∞. Now take ε = 1 in the definition of
convergence. Then there is some N ∈ N such that for all n ≥ N , |an − l| < 1.
But
|an| = |(an − l) + l| ≤ |an − l|+ |l|
by the triangle inequality. Thus for all n ≥ N , |an| ≤ 1 + |l|. So if we take
M = max{|a1|, |a2|, . . . , |aN−1|, 1 + |l|}
23
we have that |an| ≤M for all n ∈ N, as required.
We give one last example before we prove some more general theorems about conver-
gence.
Example 2.3.10. Let
an =
8n1/3
n3 +
√
n
.
Then an → 0 as n→∞.
Proof: Let ε > 0 be given. We must find N (which will depend on the given ε) such that
for all n ≥ N , ∣∣∣∣ 8n1/3n3 +√n − 0
∣∣∣∣ < ε,
i.e. so that
8n1/3
n3 +
√
n
< ε
since the terms are positive, we may remove the modulus signs.
So the game is to find a decent looking upper bound for 8n1/3/(n3 +
√
n) so that one
can easily read off what N must be. Well, we certainly have n3 ≥ √n (for all n), so
8n1/3
n3 +
√
n
≤ 8n
1/3
√
n+
√
n
=
4n1/3√
n
.
You must get used to tricks like this: replacing an expression in the denominator by a
smaller expression and/or replacing the numerator by a larger term always increases the
size of the fraction, provided everything is positive.
Now
4 · n1/3√
n
=
4 · n1/3
n1/2
=
4
n1/2−1/3
=
4
n1/6
.
So we have that
8n1/3
n3 +
√
n
≤ 4
n1/6
.
So we will have the desired inequality, namely∣∣∣∣ 8n1/3n3 +√n − 0
∣∣∣∣ < ε,
provided that
4
n1/6
< ε
24
which, after rearrangement, is provided that (4/ε)6 < n. So to complete the argument
we just take N to be any natural number greater than (4/ε)6, say N =
[
(4/ε)6
]
+ 1.
2.4 The Completeness Property for R
Definition 2.4.1. Let S be a non-empty subset of R and assume that S is bounded above.
Then a real number M is a supremum or least upper bound of S if the following two
conditions hold:
(i) M is an upper bound for S, and
(ii) if M ′ ∈ R satisfies M ′ < M then M ′ is not an upper bound for S.
It is easy to see that a set S cannot have more than one supremum. For if M1 and M2
were both suprema and M1 6= M2, then either M1 < M2 or M2 < M1 (this is the sort of
situation where one automatically uses rule (Ord 1)). But, in either case, this contradicts
condition 2.4.1(ii) above.
Thus we have proved:
Lemma 2.4.2. The supremum of a set S, if it exists, is unique and we then denote it by
sup(S).
Lemma 2.4.3. Let S be a non-empty subset of R and assume that M = sup(S) exists.
Then ∀ε > 0, ∃x ∈ S such that M − ε < x ≤M .
Proof. Let ε > 0 be given. Let M ′ = M −ε. Then M ′ < M , so by 2.4.1(ii), M ′ is not an
upper bound for S. So there must be some x ∈ S such that x > M ′. Since M is an upper
bound for S (by 2.4.1(i) ), we also have x ≤ M . So M ′ < x ≤ M , i.e. M − ε < x ≤ M ,
as required.
Example 2.4.4. For S = {17,−6,−25, 25, 0} we clearly have that sup(S) = 25. Indeed, if
S is any non-empty, finite subset of R then it contains a greatest element and this element
is necessarily its supremum.
Example 2.4.5. However, it need not be the case that a set contains its supremum as a
member. Indeed, if a < b then we claim that sup(a, b) = b despite the fact that b /∈ (a, b).
Proof. Let us prove this. Certainly b is an upper bound for (a, b). To see that 2.4.1(ii)
is also satisfied, suppose that M ′ < b. Let c = max{a,M ′}. Then certainly c < b and
so the average, d = (c + b)/2 of c and b satisfies M ′ ≤ c < d < b. Similarly, a < d < b.
25
So d is an element of the set (a, b) which is strictly greater than M ′. Hence M ′ is not an
upper bound for (a, b), as required.
Does a supremum always exist?
Example The set
SQ =
{
x ∈ Q : x2 < 2}
does not have a rational supremum.
Solution This is a non-empty set, bounded above, by 2 for example. Assume it has a
least upper bound in Q. Call this r. The rational numbers obey the axiom of trichotomy
so either r2 = 2, r2 < 2 or r2 > 2.
Case 1 It is a simple proof by contradiction that r2 = 2 implies r is irrational. Contra-
dicting the assumption that r ∈ Q.
Case 2 If r2 < 2 it is possible to find ∆1 ∈ Q : (r + ∆1)2 < 2. This means r + ∆1 ∈ SQ,
contradicting the assumption that r is an upper bound for SQ.
To find ∆1: with ∆1 yet to be chosen consider
(r + ∆1)
2 = r2 + 2r∆1 + ∆
2
1 = r
2 + ∆1 (2r + ∆1) .
Demand ∆1 < 1 (strict), so (r + ∆1)
2 < r2 + ∆1 (2r + 1). Write ∆1 = m/ (2r + 1), then
(r + ∆1)
2 < r2 +m. Finally choose m = 2− r2 to get r2 < 2 as required.
To make this argument work we have to check that
∆1 =
2− r2
2r + 1
< 1.
This holds, iff, 2 − r2 < 2r + 1 (and this requires 2r + 1 > 0 to multiply up), which
rearranges as r2 + 2r− 1 > 0. Note that 1 ∈ SQ and so r ≥ 1, since r is, by definition, an
upper bound for SQ. And, for r ≥ 1, we have r2 + 2r− 1 ≥ 1 + 2− 1 = 2 > 0 as required.
Case 3 If r2 > 2 it is possible to find ∆2 ∈ Q : (r −∆2)2 > 2. If x ∈ SQ then
x2 < 2 < (r −∆2)2 ,
i.e. x < r − ∆2. This means that r − ∆2 ∈ Q would be an upper bound for SQ,
contradicting the assumption that r is the least of all upper bounds for SQ.
26
To find ∆2: with ∆2 yet to be chosen consider
(r −∆2)2 = r2 − 2r∆2 + ∆22 > r2 − 2r∆2.
Write ∆2 = t/2r so (r −∆2)2 > r2 − t. Finally, choose t to be half the distance from r2
to 2, i.e. t = (r2 − 2) /2. Then ∆2 = (r2 − 2) /4r ∈ Q and
(r −∆2)2 > r2 − r
2 − 2
2
=
r2 + 2
2
> 2
since r2 > 2.
So in all three cases we are led to a contradiction. Thus our last assumption must be
false, namely that SQ has a least upper bound in Q.
Note that the supremum of SQ satisfies x2 = 2. Just as we adding (or adjoined)
the solution of x2 = −1 to R in constructing the complex numbers C, we could add in
the positive solution of x2 = 2, i.e. the supremum of SQ, into Q. We could continue,
adding into the set of Rational numbers the least upper bounds of subsets of Q. In
reality, a real number is associated with a subset of rational numbers itself with no talk
of supremum. Or rather associated with the set and it’s compliment, a so-called Dedekind
cut of the Rational numbers. A definition of Dedekind cuts can be found on p.12 of Real
Mathematical Analysis, C.C. Pugh, Undergraduate Texts in Mathematics, Springer, 2017.
If you think of this construction of R as adding in the supremum of subsets of rational
numbers what happens when we look at the supremum of subsets of real numbers? Will
we have to add additional elements into R or will R suffice? The answer is that R is
complete, we will not have to add in extra elements.
Property 2.4.6. (The Completeness property of R) (A14) Any non-empty subset of
R which is bounded above has a supremum in R.
So we now have a difference between R and Q; R is complete while Q is not complete.
Let us list some consequences of the completeness property.
Example 2.4.7. Consider now the set
S = {x ∈ R : x2 < 2}
of Example 2.3.7, (though note it differs from the SQ of the last example which contained
only rational numbers). Then s2 = 2 and so s =
√
2. (Clearly s is the positive square
root of 2 since 1 ∈ S, so 1 ≤ s).
27
Solution The same ideas as in the solution of the previous example work here. By the
Trichotomy of the Real Numbers we have one of s2 = 2, s2 < 2 or s2 > 2.
If s2 < 2 then, with ∆1 = (2− s2)/(2s+ 1), we have (s+ ∆1)2 < 2. This means that
s+ ∆1 ∈ S, contradicting the fact that s is an upper bound for S.
If s2 > 2 then, with ∆2 = (s
2− 2)/4s, we have (s−∆1)2 > 2. This means that s−∆
is an upper bound for S, contradicting the fact that s was the least of all upper bounds.
This means the third case must hold, i.e. s2 = 2.
Note that we had to work harder in the solution to the Example on SQ. In the earlier
example we assumed the supremum, there called r, was rational, and we had to observe
that the ∆1 and ∆2 were also rational so that we stayed within the Universe of Rational
Numbers.
In fact, by using a similar method (though the details are rather more complicated),
one can also show that
• for any x ∈ R with x > 0, and any natural number n, there exists y ∈ R, with
y > 0, such that yn = x. Such a y is unique and is denoted x1/n or n
√
x (the positive
real nth root of x). Furthermore,
• for any x ∈ R, and any odd natural number n, there exists a unique y ∈ R (of the
same sign as x) such that yn = x. Again, we write this y as x1/n.
Finally, here is a property of the real numbers that you probably took for granted.
However let’s prove it using the completeness property.
Theorem 2.4.8. The Archimedean Property N is not bounded above.
Proof. To see this suppose, for a contradiction, that N is bounded above. Then the
completeness property says that N has a supremum, say s = supN. Apply Lemma 2.4.3
with ε = 1/2. Then the lemma guarantees that there is some n ∈ N such that s−1/2 < n.
Adding 1 to both sides we get s+ 1/2 < n+ 1 (Ord 3). But then we have n+ 1 ∈ N and
s < n + 1 which contradicts our assumption that s was the supremum of, and hence an
upper bound for, S.
Corollary For all ε > 0 there exists n ∈ N such that 0 < 1/n < ε.
Proof Assume for contradiction that there is no n ∈ N such that 0 < 1/n < ε. Then
for every n ∈ N it follows that 1/n ≥ ε and hence n ≤ 1/ε. This means that 1/ε is an
upper bound for N, contradicting the previous Theorem. Hence there is a n ∈ N such
that 0 < 1/n < ε.
28
One can use this result to prove:
Lemma 2.4.9. ∀x, y ∈ R, if x < y then ∃q ∈ Q such that x < q < y.
Proof Given x, y ∈ R with x < y consider y − x > 0. By the Archimidean Property
there exists N ∈ N such that 1/N < y − x.
Claim There exists R ∈ Z with x < R/N < y.
Proof of claim Assume, for contradiction, that no such integer exists. By Completeness
of R,
sup
{ r
N
≤ x : r ∈ Z
}
exists. Completeness only says this supremum is a real number. In fact, it is of the
form j/N for some j ∈ Z. By definition of upper bound (j + 1)/N > x and so, by the
assumption that there are no ration numbers between x and y, we must have (j+1)/N ≥
y. This means that
j + 1
N
− j
N
≥ y − x
i.e. 1/N ≥ y − x. This contradicts our choice of N . Thus the claim is proved and the
main result follows.
Example For all x, y ∈ R, if x < y then there exists an irrational γ such that x < γ < y.
Solution Left to student.
We should also make the obvious corresponding definition for lower bounds for sets
of real numbers.
Definition 2.4.10. Suppose that S is a non-empty subset of R and that S is bounded
below. Then a real number m is an infimum (or greatest lower bound) of S if
(i) m is a lower bound for S, and
(ii) if m′ ∈ R and m < m′, then m′ is not a lower bound for S.
Again, one can show that the infimum of a set S is unique if it exists, and we write
inf(S) for it when it does exist. One might think that we need a result like Property 2.4.6
to postulate the existence of infima. But we can directly prove from that proposition.
Theorem 2.4.11 (Existence of infima). Every non-empty subset T of R which is bounded
below has an infimum.
Proof. See the Problem Sheet for Week 1. As a hint, define T− = {−x : x ∈ T}. Then
you should prove that T− has a supremum, M say. Now show that −M is the infimum
of the original set T .
29
So, to summarise, we are not going to define the real numbers from first principles
- you can find their construction in various sources and, in any case, you are used to
dealing with them - but it is the case that everything we need about the real numbers
follows from the axioms that we listed above for an ordered field, together with the
completeness property. Indeed, these axioms completely characterise the real numbers.
That is, and this is a rather remarkable fact: although there are many different fields, and
even many different ordered fields, if we add the completeness axiom then there is just
one mathematical structure which satisfies all these conditions - namely the real numbers
R.
2.5 Some General Theorems about Convergence
Theorem 2.5.1 (Uniqueness of Limits). A sequence can converge to at most one limit.
Proof. What we have to show is that if an → l1 as n→∞ and an → l2 as n→∞, then
l1 = l2.
So suppose that l1 6= l2. Say, wlog (“without loss of generality”), that l1 < l2. Let
ε =
l2 − l1
2
,
so ε > 0.
Since an → l1 as n→∞, there exists N1 ≥ 1 such that for all n ≥ N , |an − l1| < ε.
Also, since an → l2 as n → ∞, there exists N2 ≥ 1 such that for all n ≥ N ′,
|an − l2| < ε.
Now, let m = max{N1, N2}. Then |am − l1| < ε and |am − l2| < ε.
But
l2 − l1 = |l2 − l1| = |(l2 − am) + (am − l1)| ≤ |l2 − am|+ |am − l1|
by the triangle inequality. But the right hand side here is strictly less than ε + ε. That
is, substituting in our value ε = (l2 − l1)/2, we obtain l2 − l1 < l2 − l1, a contradiction!

30
So a sequence can have at most one limit. But when does it actually have a limit?
The next piece of theory provides us with a criterion that covers many particular cases.
Definition 2.5.2. A sequence (an)n≥1 is said to be
(i) increasing if for all n ∈ N, an ≤ an+1;
(ii) decreasing if for all n ∈ N, an+1 ≤ an;
(iii) strictly increasing if for all n ∈ N, an < an+1;
(iv) strictly decreasing if for all n ∈ N, an+1 < an.
A sequence satisfying any of these four conditions is called monotone or monotonic.
If it satisfies (iii) or (iv) it is called strictly monotonic.
Theorem 2.5.3 (Monotone Convergence Theorem). Let (an)n≥1 be a sequence that is
both increasing and bounded. Then (an)n≥1 converges.
Proof. Since the set {an : n ∈ N} is bounded, it has a supremum, l say. We show that
an → l as n→∞.
So let ε > 0 be given. We now use Lemma 2.4.3 which tells us that there is some
x ∈ {an : n ∈ N} such that l − ε < x ≤ l.
Obviously x = aN for some N ∈ N. So l − ε < aN ≤ l.
Now for any n ≥ N we have that an ≥ aN (since the sequence (an)n≥1 is increasing)
and of course we also have that an ≤ l (since l is certainly an upper bound for the set
{an : n ∈ N}, being its supremum).
So, for all n ≥ N , we have l − ε < an ≤ l, and hence l − ε < an ≤ l + ε. But (by
2.2.3(c)) this is equivalent to saying that for all n ≥ N , we have |l − an| < ε. Thus
an → l as n→∞ as required.
Example 2.5.4. Let
an =
n2 − 1
n2
.
Then (an)n≥1 is an increasing sequence since
an = 1− 1
n2
≤ 1− 1
(n+ 1)2
= an+1.
Further, 0 ≤ an < 1 for all n, so (an)n≥1 is also a bounded sequence. Hence (an)n≥1
converges.
31
In fact it is fairly easy to show directly from the definition of convergence that, with
an as in the example above, an → 1 as n → ∞. However, Theorem 2.5.3 comes into its
own in situations where it is far from easy to guess what the limit is:
Example 2.5.5. Let
an =
(
n+ 1
n
)n
=
(
1 +
1
n
)n
.
Then one can show (though it’s not particularly easy) that (an)n≥1 is an increasing,
bounded sequence. So it converges. But what is its limit? It turns out to be e (the base
for natural logarithms).
2.6 Exponentiation - a digression
This subsection is really a digression, so you do not need to remember the details but it
uses the ideas we have developed in an interesting way.
There are also some theoretical applications of Theorem 2.5.3 which allow one to give
rigorous definitions of some classical functions of analysis. For example, if x and y are
positive real numbers what does xy, or “x to the power y”, exactly mean? The answer “x
multiplied by itself y times” doesn’t really make sense if y is not a natural number! Here
we see the idea of how to define this rigorously using Monotone Convergence although,
since this is a bit of a digression, some steps will be skipped.
Let x, y be positive real numbers. We aim to give a rigorous definition of the real
number xy. If y ∈ Q, say y = n/m with n,m ∈ N, then we may use the existence of roots
(see Section 2.4) to define xy to be m
√
xn. But if y /∈ Q how should we proceed? We shall
use Question 5 of the Exercise sheet for Week 2, which tells us that we can approximate
y arbitrarily closely by rational numbers q. We then show that the xq converge and we
call the limit xy. The precise details are as follows.
Lemma 2.6.1. (a) Let y ∈ R. Then there exists a sequence (qn)n≥1 which (i) is strictly
increasing, (ii) has rational terms (i.e. qn ∈ Q for each n ∈ N) and (iii) converges to y.
(b) If q and s are positive rational numbers such that q < s, and if x ≥ 1, then
xq < xs.
Proof. (a) Firstly, let q1 be any rational number strictly less than y (e.g. q1 = [y]− 1.)
Let q2 be any rational number satisfying
max
{
q1, y − 1
2
}
< q2 < y,
32
using the result from the problem sheet. Now let q3 be any rational number satisfying
max
{
q2, y − 1
3
}
< q3 < y
as above.
We continue: once q1 < q2 < · · · < qn < y have been constructed, we choose a rational
number qn+1 satisfying
max
{
qn, y − 1
n+ 1
}
< qn+1 < y.
Clearly our construction has ensured that the sequence (qn)n≥1 is (strictly) increasing
and is bounded above (by y). It therefore converges by the Monotone Convergence
Theorem. However, we have also guaranteed that for all n ∈ N, y − 1
n
< qn < y, from
which it follows that the limit is, in fact, y.1
(b) This is left as an exercise; see the solution to Question 4 from the Exercise sheet
for Week 3.
Construction of xy (outline).
We first use the lemma to construct an increasing sequence (qn)n≥1 of rational numbers
that converges to y. Part (b) of the lemma implies that (xqn)n≥1 is a strictly increasing
sequence which is bounded above by xN where N is any natural number greater than y
(e.g. [y] + 1). Hence, by the Monotone Convergence Theorem, there is some l such that
xqn → l as n→∞. We define xy to be this l.
We can extend this definition to negative y by the formula
x−y =
1
xy
,
and we also set x0 = 1. Finally, if 0 < x < 1, so x−1 ≥ 1, then we define xy to be (x−1)−y.
We do not give any value to xy for negative x.
With these definitions all the usual laws for exponentiation can now be established.
One first proves them for rational exponents and then shows that the laws carry over to
arbitrary real exponents upon taking the limit described above. This latter process is
made easier by developing an “algebra of limits” which we shall do in the next chapter.
The laws of exponentiation being referred to above are as follows (where x is assumed
positive throughout).
1Can you see this final step? As a hint, note that for any ε > 0 there exists n ∈ N with 0 < 1
n + 1
< ε.
Now use Lemma 2.2.3(c) as usual.
33
(E1) xy+z = xy · xz;
(E2) (x · y)z = xz · yz when x, y > 0;
(E3) (xy)z = xy·z;
(E4) if 0 < x < y and 0 < z, then xz < yz.
Similarly, if x ≥ 1 and 0 < z < t, then xz < xt.
Since E1-E4 encapsulate all we will need to know about exponentiation, we don’t need
to refer back to our particular construction. In particular, we will use (E4) a number of
times, without particular comment.
34
Chapter 3
The Calculation of Limits
We now develop a variety of methods and general results that will allow us to calculate
limits of particular sequences without always having to go back to the original definition.
3.1 The Sandwich Rule
Roughly stated, this rule states that if a sequence is sandwiched between two sequences
each of which converges to the same limit, then the sandwiched sequence converges to
that limit as well. More precisely:
Theorem 3.1.1 (The Sandwich Rule). Let (an)n≥1 and (bn)n≥1 be two sequences and
suppose that they converge to the same real number l. Let (cn)n≥1 be another sequence
such that for all sufficiently large n, an ≤ cn ≤ bn. Then cn → l as n→∞.
Proof. The hypotheses state that for some N0 ≥ 1 we have
an ≤ cn ≤ bn for all n ≥ N .
Now we write down what it means for limn→∞ an = ` = limn→∞ bn. So, let ε > 0 be given.
Then there exists N1 ≥ 1 such that if n ≥ N1 then |`− an| < ε. Equivalently
`− ε < an < `+ ε for all n ≥ N1.
Similarly, there exists N2 ≥ 1 such that if n > N2 then
`− ε < bn < `+ ε for all n ≥ N2.
35
Now, let M = max{N,N1, N2}. Then the displayed inequalities combine to show that:
for all n ≥M we have `− ε < an ≤ cn ≤ bn < `+ ε.
In particular, ` − ε < cn < ` + ε, which is what we needed to prove to show that
limn→∞ cn = `.
Remark 3.1.2. The Sandwich Rule is often applied when either (an)n≥1 or (bn)n≥1 is a
constant sequence: if a ≤ cn ≤ bn for sufficiently large n and bn → a as n → ∞, then
cn → a as n→∞. (Just take an = a for all n ∈ N in 3.1.1.)
Similarly, if an ≤ cn ≤ b for sufficiently large n and an → b as n → ∞, then cn → b
as n→∞.
Definition 3.1.3. A sequence (an)n≥1 is a null sequence if an → 0 as n→∞.
Theorem 3.1.4. (i) (an)n≥1 is a null sequence iff (|an|)n≥1 is a null sequence.
If (an)n≥1 is a null sequence then (− |an|)n≥1 is a null sequence.
(ii) (Sandwich rule for null sequences.) Suppose that (an)n≥1 is a null sequence. Let
(bn)n≥1 be any sequence such that for all sufficiently large n, |bn| ≤ |an|. Then (bn)n≥1 is
also a null sequence.
Proof. (i)
|an − 0| = |an| = ||an|| = ||an| − 0| ,
and so
|an − 0| < ε iff ||an| − 0| < ε,
which gives the required result.
The result on (− |an|)n≥1 follows from |an − 0| = ||an|| = |− |an| − 0|.
(ii) We are given that for some N ∈ N we have |bn| ≤ |an| for all n ≥ N . It follows
that for all n ≥ N ,
−|an| ≤ bn ≤ |an|.
But by (i) both (|an|)n≥1 and (−|an|)n≥1 are null sequences. Hence by the Sandwich
Rule 3.1.1 (with l = 0) it follows that (bn)n≥1 is null.

Of course, this is really what we were doing in explicit cases like Question 2 of the
Week 3 Exercise Sheet.
36
Example 3.1.5. (i) (
1
n
)
n≥1
is null.
(ii) (
1
n2 + n3/2
)
n≥1
is null.
Proof (i) We did this as part of Example 2.3.2. Choose N = [1/ε] + 1 in the definition of
limit.
(ii) For all n ∈ N, ∣∣∣∣ 1n2 + n3/2
∣∣∣∣ = 1n2 + n3/2 ≤ 1n2 =
∣∣∣∣ 1n2
∣∣∣∣ ≤ ∣∣∣∣ 1n
∣∣∣∣ .
So the result follows from Theorem 3.1.4 and Part (i) (Or you could use Question 2(a) of
the Week 3 Exercise Sheet.)
Lemma 3.1.6. (a) For all m ≥ 5 we have 2m > m2.
(b) In particular, if an = 2
−n, then limn→∞ an = 0.
Proof. (a) You may have seen this in the Foundations of Pure Mathematics course.
Base case: For m = 5 we have 25 = 32 > 25 = 52.
So, suppose for some k ≥ 5 we have 2k > k2. Then in trying to relate 2k+1 and (k+1)2
one gets
2k+1 = 2 · 2k > 2 · k2 = (k + 1)2 + k2 − 2k − 1.
Now the key point is that, as k ≥ 5 we have (k2 − 2k − 1) = (k − 1)2 − 2 > 2. So from
the displayed equation we get
2k+1 > (k + 1)2 +
(
k2 − 2k − 1) > (k + 1)2 + 2.
Thus, by induction 2m > m2 for all m ≥ 5.
(b) Of course, you can prove this more directly, but part (a) implies that 0 < an = 2
−n ≤
n−2. Thus, by Theorem 3.1.4 and Question 2(a) (of Problem Sheet 2) limn→∞(an) = 0.

37
Example 3.1.7. (
1
2n + 3n
)
n≥1
is null.
Proof: For all n ∈ N, we have ∣∣∣∣ 12n + 3n
∣∣∣∣ = 12n + 3n ≤ 12n .
So the result follows from Theorem 3.1.4 and Lemma 3.1.6.
Example 3.1.8. (
n3
4n
)
n≥1
is null.
Proof: By the lemma, ∀n ≥ 5,∣∣∣∣n34n
∣∣∣∣ = n34n = n32n · 2n ≤ n3n2 · n2 = 1n.
So the result follows from 3.1.4 (and the fact that (1/n)n≥1 is null).
3.2 The Algebra of Limits.
Hopefully you now have a feel for testing whether a given sequence is convergent or not.
What should also be apparent is that we tend to repeat the same sorts of tricks. When
that happens, one should suspect that there are general rules in play. This is the case
here and we can convert the sorts of manipulations we have been doing into theorems
telling us when certain types of functions converge (or not). The next theorem can be
paraphrased as saying that: Limits of convergent series satisfy the same rules of addition
and multiplication as numbers.
Theorem 3.2.1. [The Algebra of Limits Theorem] Let (an)n≥1, (bn)n≥1 be sequences and
let a, b be real numbers. Suppose that limn→∞ an = a and that limn→∞ bn = b. Then:
(i) limn→∞ |an| = |a|;
(ii) for any k ∈ R, limn→∞ kan = ka;
(iii) limn→∞(an + bn) = a+ b;
38
(iv) limn→∞(an · bn) = a · b;
(v) if b 6= 0, then limn→∞ an
bn
=
a
b
.
Important Remark: When we are assuming a limit exists, i.e. limn→∞ an = a, and we
are given an ε > 0 along with a constant C > 0 we can feed ε′ = Cε into the definition
of limit to find M > 0 : m > M =⇒ |am − a| < Cε.
Conversely, to prove that a limit exists, i.e. limn→∞ an = a, it suffices to prove that
for all ε > 0 there exists N > 0 such that for all n > N we have |an − a| < κε for some
constant κ > 0. I tend not to use this; when proving a limit exists I aspire to deduce
|an − a| < ε, i.e. with κ = 1. This requires using the first half of this remark; applying
any assumptions on limits with constant C 6= 1.
Proof. (i) Let ε > 0 be given. Choose N so that for all n ≥ N , |an − a| < ε. Now by
Lemma 2.2.3(b), ∣∣|an| − |a|∣∣ ≤ |an − a|.
Hence, for all n ≥ N , ∣∣|an| − |a|∣∣ < ε, as required.
(ii) Firstly, if k = 0 the result is obvious since limn→∞ 0 = 0. So suppose that k 6= 0.
Let ε > 0 be given. Apply the Remark to obtain M ∈ N such that for all m ≥M , we
have |am − a| < ε/|k|. Therefore, for n ≥M , we have
|kan − ka| = |k||(an − a)| < |k| · ε/|k| = ε.
This shows that kan → ka as n→∞, as required.
(iii) Let ε > 0 be given. Apply the Remark to the two sequences. Thus we can find M1
such that |an − a| < ε/2, i.e.
a− ε/2 < an < a+ ε/2 for all n ≥M1
and M2 such that |bn − b| < ε/2, i.e.
b− ε/2 < bn < b+ ε/2 for all n ≥M2.
Adding these equations we find that
(a+ b)− ε < (an + bn) < (a+ b) + ε
i.e. |(an + bn)− (a+ b)| < ε for all n ≥ N = max(M1,M2).
39
So an + bn → a+ b as n→∞, as required.
(iv) This is harder. Start by considering |anbn − ab| which we hope we can make small,
i.e. < ε. But all we know is we can make an − a and bn − b small, so we manipulate our
problem to feed in what we know.
|anbn − ab| = |(an − a) bn + abn − ab|
= |(an − a) bn + a (bn − b)|
≤ |(an − a) bn|+ |a (bn − b)| by the triangle inequality
= |an − a| |bn|+ |a| |bn − b| since |xy| = |x| |y| .
Now convergent sequences are bounded (Theorem 2.3.9) so there exists B > 0 : |bn| ≤
B for all n ≥ 1.
Let ε > 0 be given.
Using this ε in the definition of limn→∞ an = a gives an N1 ≥ 1 such that
|an − a| < ε
2B
.
Using the same ε is the definition of limn→∞ bn = b gives an N2 ≥ 1 such that
|bn − b| < ε
2 (|a|+ 1) .
Note the +1 in the denominator; this is in case a = 0.
Let N = max (N1, N2). Assume n ≥ N . For such n all the above results hold and
combine as
|anbn − ab| ≤ |an − a| |bn|+ |a| |bn − b|
<
ε
2B
B + |a| ε
2 (|a|+ 1)
=
ε
2
+
|a|
(|a|+ 1)
ε
2
<
ε
2
+
ε
2
since |a| /(|a|+ 1) < 1
= ε.
Thus we have verified the definition that limn→∞ anbn = ab.
40
(v) We start by proving that under the conditions in the Theorem,
lim
n→∞
1
bn
=
1
b
.
We are assuming b 6= 0 so 1/b is well-defined, but what of the 1/bn?
Claim: If limn→∞ bn = b, bn 6= 0 (for all n) and b 6= 0 then there exists N1 ∈ N such that
∀n ≥ N1, one has |bn| > |b|/2 > 0.
In particular, for such n, bn 6= 0 and so the 1/bn are well-defined.
Proof of Claim: Since limn→∞ bn = b we have, by Theorem 3.2.1, that limn→∞ |bn| = |b|.
Choose ε = |b|/2 > 0 in the definition of limn→∞ |bn| = |b| to find N1 ∈ N such that
∀n ≥ N1, we have ||bn| − |b|| < |b|/2. Expand this as
|b| − 1
2
|b| < |bn| < |b|+ 1
2
|b|,
i.e.
1
2
|b| < |bn| < 3
2
|b|,
and the first inequality is what we wanted.
For n ≥ N1 we have ∣∣∣∣ 1bn − 1b
∣∣∣∣ = ∣∣∣∣b− bnbnb
∣∣∣∣ = |b− bn||bn||b|
However, |bn| > |b|/2 (because n ≥ N1) and hence |bn| · |b| > |b|2/2. Therefore
|b− bn|
|bn||b| <
2
|b|2 |b− bn|.
Let ε > 0 be given. By the Remark there exists N2 ∈ N such that, for all n ≥ N2, we
have
|bn − b| < |b|
2ε
2
.
Combine, so for n ≥ max(N1, N2) we get∣∣∣∣ 1bn − 1b
∣∣∣∣ < 2|b|2 |b− bn| < 2|b|2 |b|2ε2 = ε.
Thus we have verified the definition of
lim
n→∞
1
bn
=
1
b
.
Finally, for the general case
41
lim
n→∞
an
bn
= lim
n→∞
an
1
bn
= lim
n→∞
an lim
n→∞
1
bn
,
by the Product Rules for limits (part iv of this theorem), allowable since both limits on
the right hand side exist. Thus
lim
n→∞
an
bn
= a
1
b
=
a
b
.

42
Theorem 3.2.2. (i) Let (an)n≥1 be a null sequence and let (bn)n≥1 be a bounded sequence
(not necessarily convergent). Then (an · bn)n≥1 is a null sequence.
(ii) If (|an|)n≥1 is a null sequence then (an)n≥1 is null.
Proof. (i) Exercise.
(ii) Define the sequence (bn)n≥1 by bn = 1 if an ≥ 0 and bn = −1 if an < 0. Then
an = |an|bn. Since the sequence (bn)n≥1 is bounded, we may apply the first part to the
sequences (|an|)n≥1 and (bn)n≥1, deducing that the sequence (an)n≥1 is null if (|an|)n≥1 is
null.
Example 3.2.3. For any fixed positive real number p,
1
np
→ 0
as n→∞.
Proof: Let ε > 0 be given. We want to show that 1/np < ε for all large n. But
1
np
< ε ⇐⇒ np > 1
ε
⇐⇒ n >
(
1
ε
)1/p
,
where the final equivalence uses E4 of Section 2.6. So, we take N to be [ε−1/p] + 1. Thus,
if n ≥ N then n > ε−1/p and so the above computation shows that 1/np < ε. Therefore∣∣∣∣ 1np − 0
∣∣∣∣ < ε
and hence limn→0 1/np = 0.
Example 3.2.4.
n2 + n+ 1
n2 − n+ 1 → 1
as n→∞
Proof: Divide top and bottom of the nth term by n2. (This trick, and variations of it, is
the main idea in all examples like this.) Thus
n2 + n+ 1
n2 − n+ 1 =
1 + 1
n
+ 1
n2
1− 1
n
+ 1
n2
.
We now apply the above example with p = 1 and p = 2 to deduce that 1/n→ 0 and
that 1/n2 → 0 as n→∞. (Of course, these are also examples we have done several times
before!)
43
So by the Algebra of Limits Theorem 3.2.1(ii, iii)
1 +
1
n
+
1
n2
−→ 1 + 0 + 0 = 1 as n→∞
and
1− 1
n
+
1
n2
−→ 1 + (−1) · 0 + 0 = 1 as n→∞.
So by using Algebra of Limits Theorem 3.2.1(vi)) again we obtain that
1 + 1
n
+ 1
n2
1− 1
n
+ 1
n2
→ 1
1
= 1,
that is,
n2 + n+ 1
n2 − n+ 1 → 1
as n→∞.
For many functions given as polynomials or fractions of polynomials we can apply
methods as in the above example. It is however very important to use this result (and
earlier results) only for convergent sequences.
For example, we have seen that (an)n≥1 is not convergent when an = (−1)n. This is an
example of a bounded sequence that is not convergent (so the converse of Theorem 2.5.3
fails).
There are however cases where we can deduce negative statements.
Example 3.2.5. If p > 0 then (np)n≥1 is an unbounded sequence (and hence is not con-
vergent by Theorem 2.3.9).
Proof. Given any ` > 0 we can certainly find a natural number n > (`)1/p since the
natural numbers are unbounded. However, using (E4) of Section 2.6 we have np > `
⇐⇒ n > (`)1/p. Thus this also proves that (np)n≥1 is unbounded.
It is worth emphasising that in proving unboundedness (or any counterexample) it’s
not necessary that every value of n is “bad”, just that we can always find a larger “bad”
value of n.
Example 3.2.6. (i) If (an)n≥1 is unbounded and (bn)n≥1 is convergent, then (an + bn)n≥1
is unbounded. Similarly, (kan)n≥1 is unbounded whenever k 6= 0.
Proof. Since (bn) is convergent, it is bounded, say |bn| < B for all n. But now given any
` there exists some an with |an| > B + `. Hence by the triangle inequality, |an + bn| > `,
as required. The proof for products is similar.
44
Chapter 4
Some Special Sequences
In the previous chapter we saw how to establish the convergence of certain sequences that
were built out of ones that we already knew about. In this chapter we build up a stock
of basic convergent sequences that will recur throughout your study of analysis.
4.1 Basic Sequences
Lemma 4.1.1. For any c > 0, c1/n → 1 as n→∞.
Proof. This proof has several steps, as follows:
Step I Prove that (1 + x)n ≥ 1 + nx for all x ≥ 0 and n ∈ N.
Step II By taking x = y/n in Step I, deduce that for all y > 0 and n ∈ N,
(1 + y)1/n ≤ 1 + y
n
.
Step III Hence show that for fixed c > 1, one has c1/n → 1 as n→∞.
Step IV Complete the proof.
Proofs of Steps:
Step I: Just use the binomial theorem—which says that
(1 + x)n = 1 + nx+ (lots of positive terms).
45
Step II: Take nth roots in Part I and use (E4) of Section 2.6 to get
1 + x ≥ (1 + nx)1/n.
Substituting x = y/n gives
1 +
y
n
≥ (1 + y)1/n,
which is what we want.
Step III: Fix ε > 0. For any c > 1 we can write c = 1 + y for y > 0. Now we choose
N = [yε] + 1, so that y/N < ε. Then for any n ≥ N we have:∣∣c1/n − 1∣∣ = c1/n − 1 since clearly c1/n > 1 (or use E4 of Section 2.6)
= (1 + y)1/n − 1
≤
(
1 +
y
n
)
− 1 by part II
=
y
n
≤ y
N
< ε.
Step IV: So it remains to consider the case when 0 < c < 1. But then d = 1/c > 1 so
by Part III, d1/n → 1 as n→∞. By the Algebra of Limits Theorem 3.2.1(vi),
1
d1/n
→ 1
1
= 1
as n→∞. Finally, since
1
d1/n
= c1/n,
we have shown that c1/n → 1 as n→∞.
For completeness, recall Question 4 from the Week 4 Example Sheet:
Lemma 4.1.2. For 0 < c < 1 we have cn → 0 as n→∞.
Proof. Here is a different (and much simpler) proof. Let d = 1/c > 1 and write d = 1+x,
so x = 1/c− 1 > 0. Then dn = (1 + x)n = 1 + nx + · · ·xn by the binomial theorem. As
all the terms are positive, dn > nx. Thus for any number E, we have dn > E whenever
n ≥ E/x.
Assume ε > 0 is given. Then
cn < ε ⇐⇒ dn = 1
cn
>
1
ε
.
46
So, using the computations of the last paragraph, take N = 1+[1/xε], where x = 1/c−1.
Then, for n ≥ N we have n > 1/xε and so dn > 1/ε by the last paragraph (with E = 1/ε).
In other words, cn < ε, as required.
We now consider several sequences where it is harder to see what is going on; typically
they are of the form an = bn/cn where both bn and cn get large (or small) as n gets large.
What matters, for the limit, is how quickly bn grows (or shrinks to 0) in comparison with
cn. Roughly, if (bn)n≥1 has a higher “order of growth”1 than cn then the modulus of the
ratio will tend to infinity and there will be no limit; if (bn)n≥1 and (cn)n≥1 have roughly
the same order of growth, then we might get a limiting value for (an)n≥1; if (cn)n≥1 has
the higher order of growth, then an → 0 as n→∞.
Lemma 4.1.3. Suppose that (an)n≥1 is a convergent sequence with limit `. For any
integer M , let bn = an+M (if M happens to be negative, we just take bn = 0 or any other
number for 1 ≤ n ≤ −M). Then limn→∞ bn = `.
Proof. The point is that (apart from starting at different places) the two sequences
are really the same, so ought to have the same limit. More formally, assume ε > 0
is given. Then we can find N ∈ N such that |` − an| < ε for all n ≥ N . Hence
|` − bn| = |` − an+M | < ε for all for all n ≥ max{1, N −M}. So the sequence (bn)n≥1
converges.
1By “order of growth” we mean something coarser than “rate of growth”, that is, derivative. (The
rate of growth = derivative is, however, relevant to computing limits, see L’Hoˆpital’s Rule which we
discuss later - it says that we can compute limits by replacing functions by their derivatives.
47
If 0 < c < 1 we have seen that cn → 0 as n → ∞ and so the next result is not
surprising. But if c ≥ 1 then cn → +∞ as n→∞ and so the next result may not appear
so obvious.
Lemma 4.1.4. For any c,
cn
n!
→ 0
as n→∞.
Proof. Set an = c
n/n!. Since it suffices to prove that |an| → 0 (see Theorem 3.1.4), we
can replace c by |c| and assume that c > 0. In particular, an > 0 for all n.
Now,
an+1 = an · c
n+ 1
.
For all n ≥ 2c, we have
c
n+ 1
<
1
2
and hence
an+1 = an · c
n+ 1
<
an
2
.
So, fix an integer N ≥ c. Then for all m > 0 a simple induction says that
0 < am+N < aN2
−m.
Lemma 4.1.2 implies limm→0 (2−m) = 0.
The Algebra of Limits, Theorem 3.2.1, implies limm→0 aN(2−m) = 0.
The Sandwich Theorem then gives limm→0(am+N) = 0.
Finally, Lemma 4.1.3 gives limn→0(an) = 0.

An interpretation of this is that when c ≥ 1, n! tends to infinity at a faster rate than cn.
Next, two special sequences where the proofs are harder.
Lemma 4.1.5. The sequence (n1/n)n≥1 converges to 1 as n→∞.
Proof. This is not so obvious.
Throughout the argument we consider only n ≥ 2.
Let kn = n
1/n− 1. Then E4 of Section 2.6 says that kn > 0 and clearly n = (1 + kn)n.
48
By the binomial theorem
n = (1 + kn)
n = 1 + nkn +
n(n− 1)
2
k2n + · · ·+ knn.
Since all the terms are positive, we can discard all but the third term, so
n >
n(n− 1)
2
k2n,
and hence
k2n <
2n
n(n− 1) =
2
n− 1 .
So, for all n ≥ 2 we have that
0 < kn <
√
2√
n− 1 .
Now
√
2/
√
n− 1 → 0 as n → ∞ (exercise), so by the Sandwich Rule, kn → 0 as
n→∞. But n1/n = 1 + kn, so by the Algebra of Limits Theorem, n1/n → 1 as n→∞.

We have seen that when 0 < c < 1 and r > 0 we have nr → +∞ and cn → 0 as
n→∞. But what happens to the product nrcn, does it tend to +∞, 0 or something in
between?
Lemma 4.1.6. Fix c with 0 < c < 1 and fix r. Then limn→∞ nr · cn = 0.
Remark. This proof is quite subtle, and it is included for completeness. Once we have
L’Hoˆpital’s Theorem, we can give a very quick proof.
Proof. If r = 0 then the result is Lemma 4.1.5. Hence the result is also true for r ≤ 0
by the Sandwich Rule (as 0 < nr · cn ≤ cn if r ≤ 0).
So we may assume that r > 0.
Let us first assume that r ∈ N.
Let x = (1/c)− 1, then x > 0 since 0 < c < 1. By the binomial theorem,
(1
c
)n
= (1 + x)n =
n∑
i=0
(
n
i
)
xi.
Assume n ≥ 2r. Then the sum includes the term
(
n
r + 1
)
xr+1 and all the others are
49
positive, therefore(1
c
)n
>
(
n
r + 1
)
xr+1 =
n(n− 1) · . . . · (n− r)
(r + 1)!
xr+1.
1
nrcn
> n
(
n− 1
n
)(
n− 2
n
)
· · ·
(
n− r
n
)
xr+1
(k + 1)!
.
Since n ≥ 2r we have, for j ≤ r, n ≥ 2j and so 2n ≥ 2j + n, i.e. 2n− 2j ≥ n and so
n− j
n
≥ 1
2
.
Thus
1
nrcn
> n
(
1
2
)k
xr+1
(k + 1)!
= An,
say, where A = xr+1/2k(k + 1)! is a constant not depending on n. Then
0 < nrcn <
1
An
.
Therefore limn→∞ nkcn = 0 by the Sandwich Theorem.
Now in the case that r is (positive and) not an integer we simply observe that 0 <
nr · cn ≤ n[r]+1 · cn and, since [r] + 1 is an integer we have that n[r]+1 · cn → 0 as n→∞
by what we’ve just shown.
Hence nr · cn → 0 as n→∞ by the Sandwich Rule.
Example 4.1.7. Find:
(1) lim
n→∞
n√
3n.
(2) lim
n→∞
(−1
2
)n.
(3) lim
n→∞
n!
nn
.
Proofs: (1) Here we can break it up to get
n√
3n = 31/nn1/n. Now Lemmas 4.1.1 and
4.1.5 show that
lim
n→∞
31/n = 1 = lim
n→∞
n1/n.
Thus by the Algebra of Limits Theorem, limn→∞
n√
3n = 1.
50
(2) We know from Lemma 4.1.2 that limn→∞(1/2)n = 0, and so Theorem 3.1.4 (or 3.2.2
implies that limn→∞(−1/2)n = 0.
(3) This does not follow directly from our results, but think about individual terms:
n!
nn
=
1 · 2 · 3 · · ·n
n · n · n · · ·n =
1
n
2
n
· · · n
n
≤ 1
n
.
Since all the terms are positive and limn→∞ 1/n = 0, we can use the Sandwich Theorem
to get limn→∞ n!/nn = 0.
51
4.2 New Sequences from Old
Relative orders of growth
The fastest growing function of n seen in our examples was nn. From Example 4.1.7
(3) we find that
n!
nn
→ 0 as n→∞.
Both n! and nn get arbitrarily large as n tends to infinity, but we read this result as
saying that nn has a greater order of growth than n!. Perhaps we could say that the
growth of nn beats factorial growth.
If c > 1 then cn will grow arbitrarily large as n tends to infinity and we say it grows
exponentially quickly. But Lemma 4.1.4 says that for all c ∈ R,
cn
n!
→ 0 as n→∞.
When |c| > 1 this shows that n! grows quicker than exponentially. Perhaps we could say
that factorial growth beats exponential growth.
If r > 0 then nr will grow arbitrarily large as n tends to infinity and we say it grows
polynomially quickly. Lemma 4.1.6 says that for all r ∈ R and all 0 < c < 1,
nrcn → 0 as n→∞.
Rewriting this in terms of d = 1/c > 1 gives
nr
dn
→ 0 as n→∞.
This says that the growth of dn, however close d is to 1, beats the growth of nr, however
large r is. Thus exponential growth beats polynomial growth.
We will not define the logarithm function, lnx, in this course but it is useful to have
it for examples. In MATH20101 it will be defined as the inverse of ex. We will not define
differentiation in this course but again it is a useful tool to have. In MATH20101 we
will show that ex is differentiable and, by the Inverse Function Theorem, lnx is then
differentiable with
d
dx
lnx =
1
x
,
for x > 0. Similarly, we do not define integration in this course but we will do so next
52
year and prove the Fundamental Theorem of Calculus which justifies
lnx =
∫ x
1
dt
t
,
for x > 0. Given these facts we now apply the idea that∣∣∣∣∫ b
a
f (t) dt
∣∣∣∣ ≤ ∫ b
a
|f (t)| dt ≤ sup
[a,b]
|f (t) | (b− a) .
This gives
lnx ≤ sup
[1,x]
1
t
(x− 1) = (x− 1) < x,
for x ≥ 1. This can immediately be strengthened. Let ε > 0, so think of this as small.
Then, this inequality with x replaced by xε gives lnxε < xε, i.e.
lnx < xε/ε.
This shows that the logarithm has an order of growth slower than polynomial, however
small the power of the polynomial. That is, polynomial growth beats logarithmic
growth.
For an explicit comparison of the logarithm with a power we have
Example 4.2.1. For any c > 0, we have
lim
n→∞
lnn
nc
= 0.
Proof: Choose ε = c/2 above to get lnn < 2nc/2/c for any integer n ≥ 1. Thus
lnn
nc
<
2
cnc/2
.
The result then follows from the Sandwich Rule.
Finally we had results about functions that didn’t grow arbitrarily large but converged
to a finite limit. Lemma 4.1.4 gives
∀c > 0, c1/n → 1 as n→∞.
In fact we can replace the constant c by the increasing n as still get the same limit,
n1/n → 1 as n→∞,
53
see Lemma 4.1.5.
We can list these results in a table.
Fastest-growing (top to bottom) comments
nn See 4.1.7
n! See 4.1.4
dn for 1 < d See 4.1.6 and think of en
np for p > 0 See 3.2.3; you can also take any polynomial here
lnn see below
c1/n and n1/n for c > 0 These come last as they tend to 1; see 4.1.1 and 4.1.5.
Alternatively, we can say that an goes to zero faster than bn if limn→∞ an/bn = 0. We
can invert the table, showing the functions ordered by how quickly they slip or plunge to
zero.
Goes to zero fastest (top to bottom) comments
1
nn
See 4.1.7
1
n!
See 4.1.4
cn for 0 < c < 1 See 4.1.6 and think of e−n =
1
en
1
np
= n−p for p > 0 you can put any polynomial in the denominator
1
lnn
see below
c1/n and n1/n for c > 0 These come last as they tend to 1; see 4.1.1 and 4.1.5.
Example 4.2.2.
n100 + 2n
2n + n2
→ 1 as n→∞.
The general method with sequences like this is to find the fastest growing term,
and then divide top and bottom by it. In this example 2n is the fastest-growing term.
54
Therefore we divide top and bottom by it:
n100 + 2n
2n + n2
=
n100
2n
+ 1
1 + n
2
2n
Now n100/2n = n100 · (1/2)n → 0 by Lemma 4.1.6 (with k = 100 and c = 1/2), and
n2/2n = n2 · (1/2)n → 0 by 4.1.6 (with k = 2 and c = 1/2).
Hence, by AoL,
n100 + 2n
2n + n2
→ 0 + 1
1 + 0
= 1 as n→∞.

Example 4.2.3.
106n + n!
3 · n!− 2n →
1
3
as n→∞.
The fastest-growing term is n! so we divide top and bottom by it:
106n + n!
3 · n!− 2n =
106n
n!
+ 1
3− 2n
n!
→ 0 + 1
3− 0 =
1
3
as n→∞.
Here we applied Lemma 4.1.4 with c = 106 to deduce that 106n/n! → 0, and again
with c = 2 to deduce that 2n/n!→ 0, and finally we applied AoL.
Examples 4.2.4. Find the limits of the sequences (an) where:
(a) an =
n3
3n
(b) an =
3n
n3
(c) an =
3n + n!
n!
(d) an =
3!
n3
(e)
n28 + 5n7 + 1
2n
.
Answers (a) By the table, exponentials grow faster than polynomials (or use 4.1.6), so
this tends to zero.
(b) This is really something we deal with in the next chapter, but notice it is the reciprocal
of (a). So, whereas in part (a) the terms of the sequence get arbitrarily small, in this
part they will get arbitrarily large. We will say the sequence tends to infinity.
(c)
3n + n!
n!
=
3n
n!
+ 1.
55
By the table, limn→∞ 3n/n! = 0 and so by the AoL Theorem
lim
n→∞
(
3n
n!
+ 1
)
= 1.
(d) Careful! This is just a constant times 1/n3 and so (by the AoL or directly) it tends
to zero.
(e) Here the table says that the limit is 0. Note that to prove it using Lemma 4.1.6, you
should write it as
n28
2n
+ 5
n7
2n
+
1
2n
.
Then 4.1.6, says each fraction has limit zero and so the AoL says that
lim
n→∞
n28 + 5n7 + 1
2n
= 0 + 5 · 0 + 0 = 0.

In the next example we will use the following general result:
Lemma 4.2.5. Suppose that (an)n≥1 is a convergent sequence, say with limn→∞ an = `.
Let r and s be real numbers such that r ≤ an ≤ s for all sufficiently large n ∈ N, say for
all n ≥M . Then r ≤ ` ≤ s.
Proof. Suppose (for a contradiction) that, ` < r. Let ε = r − ` and choose N1 so that
for all n ≥ N1, |an − `| < ε. Set N = max{N1,M}. Then for any n ≥ N we have
`− ε < an < `+ ε = `+ (r − `) = r.
This contradicts the hypothesis that an ≥ r. The same argument shows that ` ≤ s.
Here is a more complicated type of example which we will see quite a lot.
Example 4.2.6. Let the sequence (an)n≥1 be defined inductively by
a1 = 2,
and for n ≥ 1
an+1 =
a2n + 2
2an + 1
.
We show that (an)n≥1 converges and then find the limit.
To do this we first show that
56
(A) ∀n ∈ N, an ≥ 1, and
(B) ∀n ∈ N, an+1 ≤ an.
Finally,
(C) This forces (an)n≥1 to converge. Now use the AoL to solve an equation for the limit
`.
Proof of A: Now obviously a1 ≥ 1. So, suppose for induction, that for some natural
number k ≥ 1 we have ak ≥ 1. Then
ak+1 ≥ 1 ⇐⇒ a
2
k + 2
2ak + 1
≥ 1 ⇐⇒ a2k + 2 ≥ 2ak + 1
(here we are using the fact that by induction 2ak + 1 is positive because ak is). But
a2k + 2 ≥ 2ak + 1 ⇐⇒ a2k − 2ak + 1 ≥ 0 ⇐⇒ (ak − 1)2 ≥ 0,
which is certainly true. So working back through these equivalences we see that ak+1 ≥ 1
as required.
Remark. It is very important in this sort of argument that one has ⇐⇒ or at least ⇐
since one is trying to prove the first statement using the validity of the final statement.
If you just have ⇒ you would not be justified in drawing these conclusions.
Proof of B: This is not by induction, but assume n ≥ 1 is given. We have
an+1 ≤ an ⇐⇒ a
2
n + 2
2an + 1
≤ an ⇐⇒ a2n + 2 ≤ 2a2n + an ⇐⇒ 0 ≤ a2n + an − 2.
But, by part (A), an ≥ 1 so a2n ≥ 1, and hence a2n + an ≥ 2, so we are done.
Step C. So we have now shown that (an)n≥1 is a strictly decreasing sequence which is
bounded (above by 2 and below by 1). Hence, by the Monotone Convergence Theorem
(or, rather, by its variant in the Exercises for Week 3) it converges. Let its limit be `.
We calculate ` explicitly as follows.
We first note that, by Lemma 4.2.5, as an ≥ 0 for all n, then ` ≥ 0 also holds.
By repeated use of the Algebra of Limits theorem, we have a2n → `2, a2n+2→ `2+2,
2an + 1→ 2`+ 1 and, finally,
a2n + 2
2an + 1
→ `
2 + 2
2`+ 1
as n→∞
57
(note that the denominator is not zero since ` ≥ 0.) Thus
lim
n→∞
an+1 =
`2 + 2
2`+ 1
.
However, Lemma 4.1.3 shows that limn→∞ an+1 = limn→∞ an. So putting these equa-
tions together we see that
`2 + 2
2`+ 1
= `.
We can now solve this for `: rearranging the equation gives `2 + 2 = 2`2 + ` and hence
gives the quadratic equation `2 + `− 2 = 0, or (` + 2)(`− 1) = 0. Thus, either ` = 1 or
` = −2. But we know that ` ≥ 0, so ` 6= −2 and hence ` = 1. Thus
lim
n→∞
an = 1.
Remarks 4.2.7. It is important to realise that the calculation of the limit in Example 4.2.1
was valid only because we already knew that the limit existed.
To bring this point home, reflect on the following (incorrect!) proof that (−1)n → 0
as n→∞ (which we know to be false from Example 2.1.4): Let an = (−1)n. Then the
sequence (an)n≥1 is defined inductively by a1 = −1 and an+1 = −an. Let l = limn→∞ an.
Then by the Algebra of Limits Theorem we have limn→∞(−an) = −l, i.e. limn→∞ an+1 =
−l. But, as above, limn→∞ an = limn→∞ an+1, so l = −l, whence 2l = 0 and so l = 0 as
required!
More subtle examples will appear on future Exercise sheets.
4.3 Newton’s Method for Finding Roots of Equa-
tions - optional
This sub-section is an aside that will not be covered in the class; as such, it is not exam-
inable, but you might find it interesting and/or useful.
Suppose that we wish to find a solution to an equation of the form
f(x) = 0
where f : R→ R is some function (e.g. we shall take f(x) to be x2−2 below and thereby
look for a square root of 2).
58
Newton’s method is as follows.
Let x1 be a reasonable approximation to a solution of the equation. For n ≥ 1, let
xn+1 = xn − f(xn)
f ′(xn)
.
Then, under suitable assumptions on x1 and f , it can be shown that the sequence
(xn)n≥1 will converge to a solution and, further, is a very good way of finding closer and
closer approximations to a solution.
Example 4.3.1. Let x1 = 1 and f(x) = x
2 − 2. Then Newton’s method suggests looking
at the sequence defined inductively by
xn+1 = xn −
(
x2n − 2
2xn
)
Simplifying this gives:
xn+1 =
xn
2
+
1
xn
.
Now one can show that this sequences converges but let us just assume that here and
let λ denote the limit. We check that λ =
√
2.
Now one can easily show that λ 6= 0, so we may apply the Algebra of Limits Theorem
to obtain
lim
n→∞
(
xn
2
+
1
xn
)
=
λ
2
+
1
λ
.
But also xn+1 → λ as n → ∞, so λ = λ2 + 1λ and it is a simple matter to solve this
equation to obtain λ =
√
2 as required.
Let us now evaluate a few terms to see how well they approximate
√
2.
59
We have
x1 = 1
x2 =
1
2
+
1
1
=
3
2
' 1 · 5000000
x3 =
3
4
+
2
3
=
17
12
' 1 · 4166667
x4 =
17
24
+
12
17
=
577
408
' 1 · 4142156
x5 =
577
816
+
408
577
' 1 · 4142136.
In fact, to seven decimal places we have that
√
2 is indeed equal to 1 · 4142136.
Example 4.3.2. Let us calculate
√
10 by Newton’s method. We take f(x) = x2 − 10 and
x1 = 3. The Newton sequence for this function is defined inductively by
xn+1 = xn −
(
x2n − 10
2xn
)
which, upon simplification, becomes
xn+1 =
xn
2
+
5
xn
.
[Check: If xn → λ as n → ∞, then by the usual argument, λ = λ2 + 5λ , which solves to
λ =
√
10. So the limit, if it exists (which we assume here), is
√
10.]
We have
x1 = 3
x2 =
3
2
+
5
3
=
19
6
' 3 · 1666667
x3 =
19
12
+
30
19
=
721
228
' 3 · 1622807
In fact, to seven decimal places,
√
10 = 3 · 1622776.
60
Chapter 5
Divergence
Example: Recall from Theorem 2.3.9 that if a sequence is convergent then it is bounded.
We can turn this around and see that certain sequences are not convergent simply because
they are not bounded; for example (
en
n2
)
n≥1
,
or some of the examples on the Exercise sheet for Week 6. To see this, let K > 0 be
given. We know from Lemma 4.1.6 that n2/en → 0. Choose ε = 1/K in the definition of
limit to find N such that n2/en < 1/K for n ≥ N . Taking reciprocals we get
en
n2
> K for all n ≥ N.
So the sequence (n2/en)
n≥1 is eventually larger than any given number, i.e. is unbounded
and hence not convergent. Of course, this argument is completely general, so we will
make a definition and a theorem out of it.
5.1 Sequences that Tend to Infinity
Definition 5.1.1. A sequence (an)n≥1 is divergent if it is not convergent, i.e. if there
is no l ∈ R such that an → l as n→∞.
Definition 5.1.2. We say that a sequence (an)n≥1 tends to plus infinity as n tends
to infinity if for each positive real number K, there exists an integer N (depending on
K) such that for all n ≥ N , an > K. That is
∀K > 0, ∃N > 0 : ∀n ≥ 1, n ≥ N =⇒ an > K.
61
In this case we write an → +∞ as n→∞, or limn→∞ an = +∞.
Example 5.1.3. The sequence ((−1)n)n≥1 is divergent since there is no l ∈ R such that
(−1)n → l as n → ∞. (see Example 2.3.4). But it does not tend to infinity as n → ∞
because one may simply take K = 1: there is clearly no N such that for all n ≥ N ,
(−1)n > 1.
Example 5.1.4. The sequence (
√
n)n≥1 is not bounded and so is divergent (by Theo-
rem 2.3.9). It does tend to infinity as n → ∞. For let K > 0 be given. Choose
N = [K2] + 1. Then if n ≥ N we have that n ≥ [K2] + 1 > K2. Hence √n > √K2 = K,
as required.
Example 5.1.5. Here is an example one needs to be careful about. Consider the sequence
((−1)n · n)n≥1. This is clearly not a bounded sequence, so is not convergent. But it does
not tend to infinity either. For if it did, taking K = 1 we would have an N such that
for all n ≥ N, (−1)n · n > 1. Which is absurd since half the time it is negative.
Theorem 5.1.6 (The Reciprocal Rule). (i) Let (an)n≥1 be a sequence of non-zero real
numbers such that an → +∞ as n→∞. Then
1
an
→ 0
as n→∞.
(ii) Let (an)n≥1 be a sequence of non-zero real numbers such that for all sufficiently large
n, an > 0. Assume that the sequence (
1
an
)
n≥1
is null. Then an → +∞ as n→∞.
Proof. (i) Suppose that an → +∞ as n→∞ and let ε > 0 be given.
Taking K = 1/ε > 0 in Definition 5.1.2, there exists N ∈ N such that for all n ≥ N ,
an > K, i.e. an > 1/ε. In particular these an are positive. Hence for all n ≥ N ,∣∣∣∣ 1an − 0
∣∣∣∣ = 1an < 11/ε = ε,
which proves that 1/an → 0 as n→∞.
(ii) Now suppose that 1/an → 0 as n→∞. Let K > 0 be given.
Then 1/K > 0, so taking ε = 1/K we see that there exists an N such that for all
62
n ≥ N , ∣∣∣∣ 1an − 0
∣∣∣∣ < ε.
We may also take N large enough so that we have an > 0 for all n ≥ N . Thus for all
n ≥ N ,
0 <
1
an
< ε =
1
K
.
Therefore for all n ≥ N , an > K, so limn→∞ an = +∞ as required.
Examples 5.1.7. One may invert the special null sequences of Section 4.1. For example,
we have that for any c > 0, n! · cn → +∞ as n → ∞. Similarly, if c > 1, we have
cn/nk → +∞ as n→∞. (In both cases the proof is left as an exercise.)
Consider now the sequence (n!− 8n)n≥1. We have
1
n!− 8n =
1
n!(1− 8n
n!
)
=
1
n!
· 1
(1− 8n
n!
)
→ 0 · 1
1− 0 = 0,
by Lemma 4.1.4 with c = 8, and AoL. Also, the fact that 1 − 8n/n! → 1 (as n → ∞),
ensures that for sufficiently large n, n!− 8n > 0. Thus, by The Reciprocal Rule 5.1.6(ii),
n!− 8n → +∞ as n→∞.
We now prove an Algebra of Limits Theorem for sequences tending to infinity.
Theorem 5.1.8. (i) Suppose that (an)n≥1 and (bn)n≥1 both tend to plus infinity. Then
(a) an + bn → +∞ as n→∞;
(b) if c > 0, then c · an → +∞ as n→∞;
(c) an · bn → +∞ as n→∞.
(ii) (The Infinite Sandwich Rule.) If bn → +∞ as n→∞, and (an)n≥1 is any sequence
such that an ≥ bn for all sufficiently large n, then an → +∞ as n→∞.
Proof. For (i)(b), let K > 0 be given. Then K/c > 0, so there exists N ∈ N such that
an > K/c for all n ≥ N . Hence c · an > K for all n ≥ N , and we are done.
The rest of the proofs are left as exercises.
Definition 5.1.9. We say that a sequence (an)n≥1 tends to −∞ as n → ∞, if for all
K < 0, there exists N ∈ N such that for all n ≥ N , an < K. This is written: an → −∞
as n→∞.
[This is easily seen to be equivalent to saying that −an → +∞ as n→∞.]
63
Example 5.1.10. The sequence ((−1)n · n)n≥1 is unbounded (so does not converge) but
neither tends to +∞ nor to −∞ as n→∞.
Similarly (8n − n!)→ −∞ as n→∞. Why? Because this is exactly the same state-
ment as saying that −(8n − n!)→ +∞ as n→∞. Which we proved in Examples 5.1.7.
Questions 6A:
Do the following sequences converge/diverge/tend to plus infinity or tend to minus
infinity?
(a)
(
cos(npi)
√
n
)
n≥1 (b)
(
sin(npi)
√
n
)
n≥1
c)
(√
n2 + 2√
n
)
n≥1
(d)
(
n3 + 3n
n2 + 2n
)
n≥1
e)
(
n2 + 2n
n3 + 3n
)
n≥1
(f)
(
1√
n−√2n
)
n≥1
64
Chapter 6
Subsequences
Looking at subsequences of a given sequence gives a practical test, Theorem 6.1.3, for
non-convergence. These also feature in two of the most important ideas and results in
analysis, namely Cauchy sequences and the Bolzano-Weierstrass theorem.
6.1 The Subsequence Test for Non-Convergence
Definition 6.1.1. Suppose that 1 ≤ k1 < k2 < · · · < kn < · · · is a strictly increasing
sequence of natural numbers. Then, given any sequence (an)n≥1 of real numbers we can
form the sequence (akn)n≥1. Such a sequence is called a subsequence of the sequence
(an)n≥1. In other words, a subsequence of (an)n≥1 is any sequence obtained by leaving out
terms (as long as infinitely many are left in).
Example 6.1.2. The sequence (4n)n≥1 is a subsequence of the sequence (n2)n≥1: we take
kn = 2
n. Then with an = n
2, we have akn = (kn)
2 = (2n)2 = 22n = 4n.
Note As easy induction shows that for all n ∈ N we have kn ≥ n.
Theorem 6.1.3. Let (an)n≥1 be a sequence. For any subsequence (akn)n≥1 of the sequence
(an)n≥1 we have:
(i) if an → l as n→∞, then akn → l as n→∞;
(ii) if an → +∞ as n→∞, then akn → +∞ as n→∞;
(iii) if an → −∞ as n→∞ then akn → −∞ as n→∞.
Proof. (i) Let ε > 0 be given. Choose N ∈ N so that for all n ≥ N , |an − l| < ε. As
noted above, for all n ∈ N we have kn ≥ n. Hence, if n ≥ N then kn ≥ N , so |akn− l| < ε.
So the same N works for the sequence (akn)n≥1.
65
The proofs of (ii) and (iii) are similar.
As mentioned above, the practical importance of Theorem 6.1.3 is that it gives us a
method of proving that certain sequences do not converge. We can either find two sub-
sequences of the given sequence that converge to different limits, or else one subsequence
that converges to either ∞ or −∞.
Example 6.1.4. The sequence (
(−1)n + 1
n2
)
n≥1
does not converge.
Proof Suppose it does, to l say. Consider the subsequence with kn = 2n. This is the
sequence (
(−1)2n + 1
(2n)2
)
n≥1
=
(
1 +
1
(2n)2
)
n≥1
and this converges to 1. Hence, by Theorem 6.1.3(i), we must have l = 1. But now
consider the subsequence with kn = 2n+ 1, i.e.(
(−1)2n+1 + 1
(2n+ 1)2
)
n≥1
=
(
−1 + 1
(2n+ 1)2
)
n≥1
,
and this converges to −1. Hence by 6.1.3(i) we must have l = −1, a contradiction.
Example 6.1.5. The sequence (n
4
−
[n
4
])
n≥1
does not converge.
Proof Suppose it does, to l say. Consider the subsequence with kn = 4n, i.e.(
4n
4
−
[
4n
4
])
n≥1
.
This is the sequence with all terms equal to 0 which of course converges to 0 and hence
by 6.1.3(i), l = 0. However, consider now the subsequence with kn = 4n+ 1, i.e.(
4n+ 1
4
−
[
4n+ 1
4
])
n≥1
.
Note that [
4n+ 1
4
]
=
[
n+
1
4
]
= n.
So this subsequence has all terms equal to 1/4, and therefore it converges to 1/4. So by
6.1.3(i), l = 1/4, a contradiction.
66
Example 6.1.6. The sequence (
n sin
(npi
2
))
n≥1
neither converges, nor tends to +∞ nor tends to −∞.
Proof First consider the subsequence with kn = 4n+ 1, i.e.(
(4n+ 1) sin
(
(4n+ 1)pi
2
))
n≥1
.
Now
(4n+ 1) sin
(
(4n+ 1)pi
2
)
= (4n+ 1) sin
(
2npi +
pi
2
)
= (4n+ 1) sin
(pi
2
)
= 4n+ 1.
So this subsequence is (4n+ 1)n≥1 which tends to +∞ as n→∞.
Secondly, consider the subsequence with kn = 4n, i.e. the sequence(
4n sin
(
4npi
2
))
n≥1
.
Every term here is 0 (since sin(2npi) = 0 for all n ∈ N). So this subsequence converges
to 0. So by 6.1.3 (i), (ii) and (iii), the original sequence does not converge and nor does
it tend to ∞ or −∞.
Example 6.1.7. Does limn→∞
(√
n− [√n] ) exist?
Hint: you may assume that [
√
m2 +m] = m.
Answer: Set an =
√
n − [√n]. We should use subsequences. One subsequence is pretty
obvious—if we take kn = n
2 then
akn =
√
n2 −
[√
n2
]
= n− n = 0,
so this subsequence clearly has limit 0.
For the second one we use the hint and take kn = n
2 + n; thus
akn =
√
n2 + n−
[√
n2 + n
]
=
√
n2 + n− n.
This is now one of those cases where we use the trick
(x− y) = (x− y)(x+ y)
(x+ y)
.
67
So, in this case
√
n2 + n− n = (
√
n2 + n− n)(√n2 + n+ n)
(
√
n2 + n+ n)
=
(n2 + n)− n2)√
n2 + n+ n
=
n√
n2 + n+ n
=
1√
1 + 1/n+ 1
→ 1
1 + 1
=
1
2
as n→∞.
Since we have two subsequences of the original sequence with different limits the
original sequence cannot have a limit.
(Here is the proof of the hint: Simply observe that
[
√
m2 +m] = m ⇐⇒
√
m2 +m < m+ 1 ⇐⇒ m2 +m < (m+ 1)2 = m2 + 2m+ 1,
which is certainly true!)
68
6.2 Cauchy Sequences and the Bolzano-Weierstrass
Theorem
We conclude this chapter with two fundamental results of analysis. You are not required
to know their proofs in this course. However, since the proofs do not require any further
knowledge on your part, and since they are such useful results, the detailed proofs are
given in the Appendix to this chapter.
Theorem 6.2.1 (The Bolzano-Weierstrass Theorem (1817)). Every bounded sequence
(an) has a convergent subsequence.
Remarks: (1) It is important to note that the Theorem is not saying that (an)n≥1 is
convergent—which is false in general. For instance take our favourite bad example, an =
(−1)n. So, for this example one would have to take a genuine subsequence. Two obvious
examples would be (a2 = 1, a4 = 1, a6 = 1, ...) and (a1 = −1, a3 = −1, a5 = −1, ...)
(2) The way to think about the theorem is as a generalisation of the Monotone Conver-
gence Theorem—which says that if one has an increasing bounded sequence then it is
convergent. So, you can probably guess how one might try to prove this theorem: given
a bounded sequence (an)n≥1 then start with a1, and look for some ak2 ≥ a1 and induct. If
this is not possible then try to do the same with descending sequences. In fact the proof
needs to be a bit more subtle, but it develops from this idea.
We now come to the problem of giving a necessary and sufficient condition on a
sequence for it to converge, without actually knowing what the limit might be. The
following definition is crucial and will feature in many different guises in your future
Analysis and Topology courses.
Definition 6.2.2. A sequence (an)n≥1 is called a Cauchy sequence if for all ε > 0,
there exists N ∈ N such that for all i, j ∈ N with i, j ≥ N , we have |ai − aj| < ε.
∀ε > 0,∃N ∈ N : ∀i, j ∈ N, i, j ≥ N =⇒ |ai − aj| < ε.
So this is saying that the terms of the sequence (an)n≥1 are getting closer and closer
together. Then we have a central theorem.
Theorem 6.2.3. A sequence converges if and only if it is a Cauchy sequence.
It is important in the definition of a Cauchy sequence that we are saying that all the
terms get close together. For example if one defined a sequence inductively by a1 = 1 and
69
an = an−1 + 1/n, then certainly for all ε > 0 we can find N such that |an − an+1| < ε for
n ≥ N . But, in fact this sequence is not convergent (we have seen an informal proof of
this already and will see it again when we consider infinite series). So, the last theorem
would not be true if we just assumed that successive terms got close together.
6.2.1 Proofs for the section - optional
Here are detailed proofs of the Bolzano-Weierstrass Theorem and the resulting theorem
on Cauchy sequences. As mentioned above, these proofs are not required in this course.
But the results are so useful that, if you have the time do go through them, it will set
you up nicely for when you study real and complex analysis and metric spaces next year.
Theorem 6.2.4. (The Bolzano-Weierstrass Theorem). Any bounded sequence (an)
possesses a convergent subsequence. In other words there exist a sequence of numbers
k1 < k2 · · · < kr < kr+1 < · · ·
such that the subsequence (ank)k≥1 is convergent.
Proof. Since (an)n≥1 is bounded, it has a supremum M = sup{an : n ∈ N} and an
infimum N = inf{an : n ∈ N}. (see Chapter 2). The proof is quite sneaky; what we will
do is construct a chain of real numbers
M1 = M ≥M2 · · · ≥Mr · · · ≥ N
and a second sequence
N1 = M1 − 1, N2 = M2 − 1
2
, N3 = M3 − 1
3
, · · · , Nr = Mr − 1
r
· · ·
such that some element akr (with kr > kr−1) is squeezed between them: Nr ≤ akr ≤Mr.
This will do. The reason is that by the Monotone Convergence Theorem, the {Mr} have
a limit, say µ. Then one shows that limr→∞Nr = µ as well and hence by the Sandwich
Theorem limr→∞ akr = µ as well.
OK, let’s see the details. As we said, we take M1 = M and N1 = M1 − 1. The point
here is that N1 is not an upper bound for {an : n ∈ N} and so there exists some ak1 with
N1 < ak1 ≤M1. Now we let M2 = sup{an : n > k1}.
We note here that any upper bound for the {an : n ∈ N} must also be an upper bound
for the smaller set {an : n > k1}. Thus M2 ≤M1.
70
This time we set N2 = M2 − 1/2. Then since N2 is not an upper bound for {an : n >
k1}, there exists some ak2 with k2 > k1 such that N2 < ak2 ≤M2.
Now we induct. Suppose that we have found (M1, N1, ak1 , · · ·Mr, Nr, akr) in this way;
they satisfy
Ni = Mi − 1
i
< aki ≤Mi = sup{aj : j > ki−1} ≤Mi−1
and ki > ki−1 for each 1 < i ≤ r.
Then we set Mr+1 = sup{aj : j > kr} and Nr+1 = Mr+1 − 1/(r+1). Then as Nr+1 is
not an upper bound of {aj : j > kr} there exists some akr+1 with Nr+1 < akr+1 ≤ Mr+1
and kr+1 > kr. This completes the inductive step.
Now, the {M`}`≥1 is a descending sequence and, as each M` is an upper bound of some
collection of the ap, we see that the M` ≥ ap for some such ap. Thus the M` are bounded
below by N . Hence the Monotone Convergence Theorem from Q3 of the Examples for
Week 3 implies that the limit limr→∞Mr exists, say limr→∞Mr = µ.
We next claim that limr→∞Nr = µ as well. To see this pick ε > 0 and pick P such
that if p ≥ P then
Mp − µ = |Mp − µ| < ε/2.
We also know that (for q ≥ Q = [2/ε] + 1), we have
Nq ≥Mq − 1
q
≥Mq − ε
2
.
By the triangle inequality
|Nq − µ| ≤ |Nq −Mq|+ |Mq − µ| < ε
2
+
ε
2
= ε for all q ≥ max{P,Q}.
Thus, limr→∞Nr = µ, as claimed.
Now we are done: since Nr < akr ≤ Mr for each r, the Sandwich Theorem ensures
that limr→∞ akr = µ, as well.
Alternative proof Let {an}n≥1 be a bounded sequence.
If the sequence only takes a finite number of distinct values then at least one of the
values must be taken by infinitely many terms of the sequence. These terms form a
convergent subsequence as required.
So we may assume the sequence takes an infinite number of distinct values, that is
the set {an : n ≥ 1} is infinite.
71
Since {an}n≥1 is a bounded sequence there exists a closed interval I0 ⊆ R : an ∈ I0
for all n ≥ 1.
We split I0 at it’s midway point into two closed sub-intervals. Since {an : n ≥ 1} is
an infinite set the intersection of it with at least one of the two subintervals will be an
infinite set. Call this subinterval I1 (if both subintervals contain infinitely many elements
of the set choose the left hand interval). Thus the set {an : an ∈ I1} is infinite. Choose k1
to be one of the n occurring in the set (perhaps the minimum), so ak1 ∈ I1, and consider
the set {an : n ∈ I1, n > k1} . This is still an infinite set since only a finite number of
elements have been removed from the infinite set {an : an ∈ I1}. Repeat the process.
Split I1 at it’s midway point into two closed sub-intervals. Choose the subinterval I2
such that {an : n ∈ I2, n > k1} is an infinite set. Choose k2 > k1 as the least n in this
set, so ak2 ∈ I2, and consider the infinite set {an : n ∈ I2, n > k2} .
Continuing we have a sequence k1 < k2 < k3 < ... and of closed intervals I0 ⊇ I1 ⊇
I2 ⊇ I3 ⊇ ... such that akr ∈ Ir for all r ≥ 1. Further, if ` (I) is the length of the interval
then ` (Ir) = 2
−r` (I0) .
These facts are sufficient to prove (i.e. it will not be done here) that
⋂∞
r=0 Ir = {a} for
some a ∈ R (it is important for this that the Ir are closed intervals), and limr→∞ akr = a.
Thus we have found a convergent subsequence.
Examples 6.2.5. The Theorem tells us nothing about what is the subsequence {akr} or its
limit µ. Some exercises might give you a feel for the vagaries inherent in the argument.
For the sequence an = 1 − 1/n for n ≥ 1 all subsequences converge, and all to the
same value, 1.
For a sequence like
an = (−1)n 1
n
there are lots of possible subsequences— you could take the descending chain a2n = 1/2n
for all n or the ascending chain a2n+1 = −1/(2n+1) for all n or some messier combination
of the two.
The limit is also not uniquely determined; just think about the case of an = (−1)n
for all n.
In fact one can extend the proof of this theorem a bit to prove the following:
Challenging Exercise: Prove that every sequence (an)n≥1 has a subsequence (akn)n≥1
which is either increasing (i.e. for all n ≥ 1, akn ≤ akn+1) or decreasing (i.e. for all
n ≥ 1, akn ≥ akn+1).
72
We now consider Cauchy sequences as defined in Definition 6.2.2. We begin with:
Lemma 6.2.6. Every Cauchy sequence (an)n≥1 is bounded.
Proof. Take N such that, for i, j ≥ N we have |ai− aj| < 1. In particular, taking i = N
we see that
aN − 1 < aj < aN + 1 for all j ≥ N.
Thus an ≤ max{a1, a2, . . . , aN−1, aN + 1} for all n. The lower bound is similar.
We know that an increasing sequence (an)n≥1 has a limit if and only if it is bounded
(combine the Monotone Convergence Theorem with Theorem 2.3.9). Using Cauchy se-
quences we can get a general analogue:
Theorem 6.2.7. (The Cauchy Sequence Theorem) A sequence (an)n≥1 converges if
and only if it is a Cauchy sequence.
Proof. Suppose first that (an)n≥1 is a Cauchy sequence. By the Bolzano-Weierstrass
Theorem we can at least find a convergent subsequence; say (akr)r≥1 with limr→∞ akr = µ.
Assume ε > 0 is given. By the definition of limit as r →∞ there exists N0 ≥ 1 such
that
|akr − µ| <
ε
2
(1)
for all r ≥ N0.
Also, by the Cauchy condition there exists N1 ≥ 1 such that
|ai − aj| < ε
2
(2)
for all i, j ≥ N1.
Set N = max{N0, N1}. In (2) choose i = kr with r > N . Since kr ≥ r we have
kr > N ≥ N0 and so (1) holds. By the triangle inequality these combine to give
|aj − µ| ≤ |aj − akr |+ |akr − µ| <
ε
2
+
ε
2
= ε for all j ≥ N .
Thus limn→∞ an = µ as we wanted.
Conversely, suppose that (an)n≥1 converges; say with limn→∞ an = ν. Let ε > 0 be
given. There exists N such that |aj − µ| < ε/2 for all j ≥ N . But now we find that for
i, j ≥ N we have
|ai − aj| ≤ |ai − ν] + |aj − ν] < ε
2
+
ε
2
= ε.
73
So we have a Cauchy sequence.
74
Chapter 7
L’Hoˆpital’s Rule
We will use L’Hoˆpital’s Rule, which some of you will have seen before. We can’t math-
ematically justify the rule in this course unit, simply because it involves differentiation
of functions and we have not yet given the rigorous definition of when a function is dif-
ferentiable nor of what the derivative is. That will be done in the second year course on
Real Analysis. But the rule is very useful, so we will use it.
We consider two sequences (an)n≥1 and (bn)n≥1, both tending to infinity. L’Hoˆpital’s
Rule gives a method for calculating limn→∞ an/bn under certain circumstances.
7.1 L’Hoˆpital’s Rule
Assume that f : [1,∞)→ R and g : [1,∞)→ R are two functions which can be differen-
tiated at least twice and for some N > 0 that g′(x) 6= 0 for x > N . Set an = f(n) and
bn = g(n) for n ∈ N.
Assume that lim
n→∞
an = +∞ = lim
n→∞
bn. (†)
Then
lim
n→∞
an
bn
= lim
n→∞
f ′(n)
g′(n)
,
assuming that the Right Hand Side exists. Here g′ = dg/dx.
Second Version: L’Hoˆpital’s Rule also holds if you replace (†) by
Assume that lim
n→∞
an = 0 = lim
n→∞
bn. (††)
Since we do not yet have a rigorous definition of the derivative, we’re not in a position
75
to have a rigorous proof of the validity of L’Hoˆpital’s Rule, though you may have seen
some arguments for it when studying Calculus. Anyway, we will take it as correct (which
it is) and see some examples of its use.
Example 7.1.1. Say an = 2n+ 3 and bn = 3n+ 2. Take f(x) = 2x+ 3 and g(x) = 3x+ 2,
so that clearly
an
bn
=
f(n)
g(n)
and the hypotheses of the rule are satisfied. Thus L’Hoˆpital’s Rule tells us that
lim
n→∞
an
bn
= lim
n→∞
f ′(n)
g′(n)
= lim
n→∞
2
3
=
2
3
.
Example 7.1.2. Let an = 3n
2 − 4n + 2 and bn = (n + 1)2. Here we apply the rule to the
functions f(x) = 3x2−4x+2 and g(x) = (x+1)2, noting that they satisfy the conditions
(twice-differentiability and the latter having nonzero derivative for large enough x). We
obtain
lim
n→∞
3n2 − 4n+ 2
(n+ 1)2
= lim
n→∞
6n− 4
2(n+ 1)
.
Still top and bottom go to +∞ as n→∞. But we may apply the rule again to obtain
lim
n→∞
6n− 4
2(n+ 1)
= lim
n→∞
6
2
= 3.
Of course, in these examples one may also use the previously discussed method of
dividing top and bottom by the fastest-growing term. However, L’Hoˆpital’s Rule really
comes into its own when applied to examples like the following. (They do all satisfy the
differentiability condition and the condition, on the denominator, of being nonzero for
large enough x, though we do not note this explicitly.)
Example 7.1.3. Consider the sequence(
lnn
n
)
n≥1
.
Before applying L’Hoˆpital’s Rule we should note that lnn→∞ as n→ +∞.
So we may indeed apply the Rule in this example (with f(x) = lnx and g(x) = x)
and we see that
lim
n→∞
lnn
n
= lim
n→∞
1
n
1
= lim
n→∞
1
n
= 0.
76
Example 7.1.4. Similarly (with f(x) = ln x and g(x) = ln(x+ 1)):
lim
n→∞
lnn
ln(n+ 1)
= lim
n→∞
1
n
1
(n+1)
= lim
n→∞
n+ 1
n
= lim
n→∞
(
1 +
1
n
)
= 1.
Example 7.1.5. And a more complicated example:
lim
n→∞
ln(4n5 − 1)
ln(n2 + 1)
= lim
n→∞
(
20n4
4n5 − 1 ·
n2 + 1
2n
)
= lim
n→∞
10n3(n2 + 1)
4n5 − 1
= lim
n→∞
10n5 + 10n3
4n5 − 1 = limn→∞
10 + 10
n2
4− 1
n5
=
10 + 0
4− 0 =
5
2
.
However, before applying L’Hoˆpital’s Rule you have to be careful to ensure that (†)
holds, since otherwise you may get rubbish:
Example 7.1.6. Take an = 1− 1n and bn = 2− 1n . then using the Rule we get
lim
n→∞
1− 1
n
2− 1
n
= lim
n→∞
n−2
n−2
= 1.
But even more obviously
lim
n→∞
1− 1
n
2− 1
n
=
1− 0
2− 0 =
1
2
.
What went wrong? The problem is that (†) does not hold, since limn→∞ an 6=∞. So,
the rule should not have been applied.
Finally, L’Hoˆpital’s Rule gives easy proofs of Lemma 4.1.6 and the related result for
logs mentioned after the Tables on the Supplement to Section 5:
Example 7.1.7. For any 0 < c < 1 and k we have limn→∞ nkcn = 0.
Proof: If k ≤ 0 the result follows from limn→∞ cn = 0. So we may assume k > 0.
The exponent k is a real number, not necessarily a natural number. So pick a natural
number K ≥ k. Since nKcn ≥ nkcn, the Sandwich Rule says we need only prove that
limn→∞ nKcn = 0. Secondly, we rewrite this as limn→∞ nK/dn = 0 (for d = 1/c > 1).
This ensures that we are in a situation where we can apply L’Hoˆpital’s Rule and gives
lim
n→∞
nK
dn
= lim
n→∞
K
ln(d)
nK−1
dn
.
By induction on K the RHS has limit 0 (where one starts the induction at K−1 = 0).
The rule for logs is similar: We are discussing limn→∞ lnn/nc, for any c > 0. Again
77
we can apply the rule to get
lim
n→∞
lnn
nc
= lim
n→∞
1
n
cnc−1
= lim
n→∞
1
c
1
nc
→ 0.
78

































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































学霸联盟