xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-MATH10242

时间：2021-03-19

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

学霸联盟

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

学霸联盟