1.2 Sequences and limits, from zero

Convergence to L is a game you can always win. However small a tolerance someone names, the terms eventually stay within it. This chapter teaches you to play the game, to write the proof that you win, and the four big theorems that follow.

In school, $\lim_{n\to\infty} \frac{n+1}{n} = 1$ was computed: divide top and bottom by $n$ , let $\frac1n$ “become 0”. That is a fine method, but it never said what a limit is, so it could not tell you when the rules work. The definition below does. It looks hard because it has three quantifiers. It is a game with two players, and once you see the game, the proofs follow a fixed pattern you can learn: scratch work to find $N$ , then a forward write-up.

Before you start

Chapter 1.1 (supremum, the approximation property, the Archimedean property) and quantifier order from 0.1.

Quick checkIn

\forall \varepsilon > 0\ \exists N:\ \dots

, may

N

depend on

\varepsilon

Quick checkBy the Archimedean property, for

\varepsilon = 0.003

is there a natural number

n

with

\frac1n < 0.003

The picture: a game

A sceptic names a tolerance $\varepsilon$ (the green band around $L$ ). The prover must answer with a point $N$ in the sequence such that every term after the $N$ -th lies inside the band. If the prover can always answer, however thin the band, the sequence converges to $L$ . Slide $\varepsilon$ down and watch $N$ grow: a smaller tolerance needs a later starting point, which is why $N$ is allowed to depend on $\varepsilon$ . Switch to $(-1)^n$ : for $\varepsilon = 1$ , odd terms sit at distance 2 from $L = 1$ forever, so no $N$ works.

Where this came from· From 'approaches' to epsilon

Newton and Leibniz used limits without defining them, speaking of quantities that “vanish” or become “infinitely small”. Bishop Berkeley mocked these in 1734 in The Analyst as “ghosts of departed quantities”. Calculus kept working, but nobody could say why. Augustin-Louis Cauchy’s Cours d’analyse (1821) tried to fix this by defining a limit in words: the terms get closer and closer to a fixed value, until they differ from it by as little as one wishes. His proofs also used inequalities with small numbers named $\varepsilon$ and $\delta$ . The fully quantified definition with “for every $\varepsilon$ there is an $N$ ”, which no longer talks about motion or infinitely small quantities, is credited to Karl Weierstrass and his Berlin lectures in the following decades. The problem they were solving was to make every theorem of calculus rest on inequalities that can be checked, and the game in this chapter is that idea.

Definitions

Definition B

Sequence

A sequence is an infinite list $a_1, a_2, a_3, \dots$ of real numbers, written $(a_n)$ . Formally it is a function $a: \mathbb N \to \mathbb R$ , with $a_n$ the value at $n$ .

In one lineAn infinite list of real numbers $a_1, a_2, a_3, \dots$ ; formally a function from the natural numbers to the reals.

Why it existsLimits of sequences are the simplest limits, and every other limit in analysis can be described through them.

Definition B

Convergent sequence

A sequence $(a_n)$ converges to $L$ , written $a_n \to L$ or $\lim a_n = L$ , if

\forall \varepsilon > 0\ \ \exists N \in \mathbb N\ \ \forall n > N:\quad |a_n - L| < \varepsilon.

$L$ is the limit. Here $|a_n - L|$ is the distance from $a_n$ to $L$ , so $|a_n - L| < \varepsilon$ says $a_n$ is inside the band $(L - \varepsilon, L + \varepsilon)$ .

In one line $a_n \to L$ if for every $\varepsilon > 0$ there is an $N$ such that $|a_n - L| < \varepsilon$ for every $n > N$ .

Why it existsIt captures 'eventually as close as you like' with no talk of infinitely small quantities.

Definition B

Divergent sequence

A sequence diverges if it does not converge to any $L$ . By the negation rules of 0.1, $(a_n)$ does not converge to $L$ when $\exists \varepsilon > 0\ \forall N\ \exists n > N:\ |a_n - L| \ge \varepsilon$ .

In one lineA sequence that converges to no real number.

Why it existsNaming the negation lets us prove non-convergence, such as for $(-1)^n$ .

How to prove a limit: scratch work, then write-up

Every $\varepsilon$ - $N$ proof has two parts. In scratch work you start from the goal $|a_n - L| < \varepsilon$ and work backwards to find how large $n$ must be. In the write-up you go forwards: “Let $\varepsilon > 0$ . Choose $N = \dots$ . Then for $n > N$ , …”. Chapter 0.7 explains why the two must be kept apart.

Why· Why you may make the expression bigger

In scratch step 3 we replaced $\frac5{n+2}$ with $\frac5n$ , which is larger. That is allowed, and it is the most useful trick in analysis: if a bigger quantity is less than $\varepsilon$ , the smaller one certainly is. You may over-estimate the distance freely; you may never under-estimate it. Choosing a simple upper bound makes the inequality easy to solve for $n$ .

Worked example

Prove

\frac{1}{\sqrt n} \to 0

Solution.

Scratch: solve the goal for $n$ . $\left|\frac1{\sqrt n} - 0\right| = \frac1{\sqrt n} < \varepsilon \iff \sqrt n > \frac1\varepsilon \iff n > \frac1{\varepsilon^2}$ . Every step is reversible for positive quantities, so this tells us exactly which $n$ work.
Write-up: start. Let $\varepsilon > 0$ , and choose $N \in \mathbb N$ with $N \ge \frac1{\varepsilon^2}$ (Archimedean property). ‘For every $\varepsilon$ ’: take it arbitrary. Then build $N$ from it.
Write-up: check. If $n > N$ then $n > \frac1{\varepsilon^2}$ , so $\sqrt n > \frac1\varepsilon$ and $\frac1{\sqrt n} < \varepsilon$ . The scratch-work steps, now run forwards.

Answer. $\frac1{\sqrt n} \to 0$ . $\blacksquare$ For $\varepsilon = 0.01$ this gives $N = 10000$ : after the 10000th term every term is within $0.01$ of 0.

Why· The recipe, in one place

Scratch work (on the side, not part of the proof): write the goal $|a_n - L| < \varepsilon$ , simplify the left side, over-estimate it by something simple like $\frac{c}{n}$ , and solve $\frac cn < \varepsilon$ to get $n > \frac c\varepsilon$ .

Write-up (the proof the reader sees): “Let $\varepsilon > 0$ . Choose $N \ge \frac c\varepsilon$ . Then for every $n > N$ , $|a_n - L| = \dots < \frac cn < \frac cN \le \varepsilon$ .” Every symbol is introduced before it is used: $\varepsilon$ is arbitrary, $N$ is built from it, $n$ is arbitrary beyond $N$ .

Why the two parts are separate: the scratch work runs backwards from the goal, so each line says “this is true if that is true”. The write-up must run forwards, so each line says “this is true because that was true”. The same inequalities appear in both, in opposite order.

Worked example

Prove

\frac{2n^2 + 1}{n^2 + n + 1} \to 2

Solution.

Guess the limit. Divide top and bottom by $n^2$ : $\frac{2 + 1/n^2}{1 + 1/n + 1/n^2}$ , which looks like $\frac21 = 2$ . Scratch work. The school method finds the candidate $L$ . The definition then proves it.
Scratch: simplify the distance. $\left|\dfrac{2n^2 + 1}{n^2 + n + 1} - 2\right| = \left|\dfrac{2n^2 + 1 - 2n^2 - 2n - 2}{n^2 + n + 1}\right| = \dfrac{2n + 1}{n^2 + n + 1}$ . One fraction. The $n^2$ terms cancel, which is what makes the distance small.
Scratch: over-estimate. For $n \ge 1$ , $2n + 1 \le 3n$ and $n^2 + n + 1 > n^2$ . So $\dfrac{2n + 1}{n^2 + n + 1} < \dfrac{3n}{n^2} = \dfrac3n$ . Make the top bigger and the bottom smaller, so the fraction gets bigger. A bigger fraction below $\varepsilon$ forces the original below $\varepsilon$ .
Scratch: solve. $\frac3n < \varepsilon \iff n > \frac3\varepsilon$ . This tells us how to choose $N$ .
Write-up. Let $\varepsilon > 0$ and choose $N \in \mathbb N$ with $N \ge \frac3\varepsilon$ . For $n > N$ : $\left|\frac{2n^2+1}{n^2+n+1} - 2\right| = \frac{2n+1}{n^2+n+1} < \frac3n < \frac3N \le \varepsilon$ . Forwards now. The first step is the simplification from step 2, then step 3, then $n > N$ gives $\frac3n < \frac3N$ , then $N \ge \frac3\varepsilon$ gives $\frac3N \le \varepsilon$ .

Answer. The sequence converges to $2$ . $\blacksquare$ For $\varepsilon = 0.01$ this gives $N = 300$ .

Your answerFor

a_n = \frac{2n^2 + 1}{n^2 + n + 1}

and

\varepsilon = 0.04

, the rule from the example is

N \ge \frac3\varepsilon

. What is

N

Quick checkA proof of

a_n \to 0

says: 'Let

N = 100

. Then for

n > N

|a_n| < 0.01

.' What is wrong?

Your answerFor

a_n = \frac{3n+1}{n+2}

and

\varepsilon = 0.01

, the step-through's rule gives

N \ge \frac{5}{\varepsilon}

. What is the smallest such whole number

N

The triangle inequality

Definition B

Triangle inequality

For all real $x, y$ : $|x + y| \le |x| + |y|$ . In the form used most: $|a - c| \le |a - b| + |b - c|$ , the distance from $a$ to $c$ is at most the distance via any third point $b$ .

In one line $|x + y| \le |x| + |y|$ : the direct distance is never longer than a detour.

Why it existsIt lets you split one distance into two smaller pieces and bound each, which is how almost every limit theorem is proved.

Proofstandard

The idea: Both x and −x are at most |x|; add the corresponding inequalities.

-|x| \le x \le |x|

and

-|y| \le y \le |y|

Every number lies between its absolute value and minus its absolute value.

-(|x| + |y|) \le x + y \le |x| + |y|

Add the two chains.

|x + y| \le |x| + |y|

. For the second form, put

x = a - b

y = b - c

\blacksquare

|z| \le c

means exactly

-c \le z \le c

Worked example

Prove

(-1)^n

diverges.

Solution. To show a sequence does not converge, you play the sceptic: you must pick a tolerance $\varepsilon$ that no prover can answer, whatever limit $L$ is proposed.

What we must show. For every $L$ : $(-1)^n$ does not converge to $L$ . That is: $\exists \varepsilon > 0\ \forall N\ \exists n > N:\ |(-1)^n - L| \ge \varepsilon$ . The negation of the definition (0.1): “for every” and “there is” swap, and the final inequality flips.
Choose the tolerance. Take $\varepsilon = 1$ , whatever $L$ is. The terms $1$ and $-1$ are 2 apart, so a band of radius 1 around any $L$ cannot hold both.
Use both kinds of term. Let $N$ be any natural number. There is an $n > N$ with $(-1)^n = 1$ (an even $n$ ) and an $n' > N$ with $(-1)^{n'} = -1$ (an odd $n'$ ). Suppose both were within 1 of $L$ . Then the triangle inequality gives $2 = |1 - (-1)| \le |1 - L| + |L - (-1)| < 1 + 1 = 2$ , which is false. The triangle inequality in the form $|a - c| \le |a - b| + |b - c|$ , with the detour through $L$ .
Conclude. So at least one of the two terms is at distance $\ge 1$ from $L$ , and that term has index above $N$ . This is the “there is $n > N$ ” the negation asks for.

Answer. No $L$ works, so $(-1)^n$ diverges. $\blacksquare$

The limit laws

These are the rules you used in school. Each is proved by splitting a distance with the triangle inequality and giving each piece part of the budget $\varepsilon$ , the ” $\varepsilon/2$ trick” from 1.1.

Theorem B Abbott Thm 2.2.7

Limits are unique

If $a_n \to L$ and $a_n \to M$ , then $L = M$ .

In one lineA sequence cannot converge to two different limits.

Why it is trueIf it did, terms would eventually be within ε of both, so the two limits would be closer than 2ε for every ε, hence equal.

ProofAbbott 2.2.7

The idea: Give each limit half the budget: eventually a_n is within ε/2 of L and within ε/2 of M, so |L − M| < ε. A distance smaller than every positive ε is zero.

Let

\varepsilon > 0

Arbitrary tolerance.

There are

N_1, N_2

with

|a_n - L| < \frac\varepsilon2

for

n > N_1

and

|a_n - M| < \frac\varepsilon2

for

n > N_2

. Let

n > \max(N_1, N_2)

Convergence to

L

with tolerance

\varepsilon/2

, and to

M

with

\varepsilon/2

; take the later of the two starting points so both hold.The ε/2 trick: two pieces, half the budget each.

|L - M| \le |L - a_n| + |a_n - M| < \frac\varepsilon2 + \frac\varepsilon2 = \varepsilon

Triangle inequality through the point

a_n

Since

|L - M| < \varepsilon

for every

\varepsilon > 0

|L - M| = 0

, so

L = M

\blacksquare

A non-negative number less than every positive number must be 0 (otherwise take

\varepsilon

equal to it).

Theorem B Abbott Thm 2.3.2

Convergent sequences are bounded

If $(a_n)$ converges, there is $M$ with $|a_n| \le M$ for all $n$ .

In one lineIf $a_n \to L$ , some single number bounds every $|a_n|$ .

Why it is trueAfter N all terms are within 1 of L; the finitely many before N are bounded by their maximum.

ProofAbbott 2.3.2

The idea: Take ε = 1: after some N every term is within 1 of L, so |a_n| < |L| + 1. Only finitely many terms come before N, and a finite list has a largest absolute value.

Let

a_n \to L

. There is

N

with

|a_n - L| < 1

for

n > N

The definition with

\varepsilon = 1

For

n > N

|a_n| < |L| + 1

Triangle inequality:

|a_n| = |a_n - L + L| \le |a_n - L| + |L|

Let

M = \max(|a_1|, \dots, |a_N|, |L| + 1)

. Then

|a_n| \le M

for every

n

\blacksquare

A finite list of numbers has a maximum.

Theorem B Abbott Thm 2.3.3

Algebraic limit laws

Let $a_n \to a$ and $b_n \to b$ . Then (1) $a_n + b_n \to a + b$ ; (2) $c\,a_n \to ca$ for any constant $c$ ; (3) $a_n b_n \to ab$ ; (4) if $b \ne 0$ (and every $b_n \ne 0$ ), $a_n / b_n \to a/b$ .

In one lineIf $a_n \to a$ and $b_n \to b$ , then $a_n + b_n \to a + b$ , $c\,a_n \to ca$ , $a_n b_n \to ab$ , and $a_n/b_n \to a/b$ when $b \ne 0$ .

Why it is trueEach is the triangle inequality plus a split of the budget ε.

Proof of the sum law (1)Abbott 2.3.3

The idea: Split |(a_n + b_n) − (a + b)| into |a_n − a| + |b_n − b| and give each half the budget.

Let

\varepsilon > 0

Arbitrary tolerance.

Choose

N_1, N_2

with

|a_n - a| < \frac\varepsilon2

for

n > N_1

and

|b_n - b| < \frac\varepsilon2

for

n > N_2

. Let

N = \max(N_1, N_2)

Use each convergence with tolerance

\varepsilon/2

; after the later starting point, both hold.

For

n > N

|(a_n + b_n) - (a + b)| = |(a_n - a) + (b_n - b)| \le |a_n - a| + |b_n - b| < \frac\varepsilon2 + \frac\varepsilon2 = \varepsilon

\blacksquare

Regroup, then the triangle inequality.

Proof of the product law (3)Abbott 2.3.3

The idea: Add and subtract a_n b to split a_n b_n − ab into a_n(b_n − b) + b(a_n − a). The first piece needs a bound on |a_n|, which convergent sequences have.

We need

|a_n b_n - ab|

small.

The difference we must make small.

a_n b_n - ab = a_n(b_n - b) + b(a_n - a)

Add and subtract

a_n b

: zero added, so the value is unchanged, but now each piece contains one small difference.The 'add and subtract' trick. It is chosen so that each piece contains a difference we can control.

|a_n b_n - ab| \le |a_n|\,|b_n - b| + |b|\,|a_n - a|

Triangle inequality.

There is

M > 0

with

|a_n| \le M

for all

n

Convergent sequences are bounded (proved above); choose

M > 0

Let

\varepsilon > 0

Scratch work, backwards: we want each piece below

\frac\varepsilon2

. The first piece is at most

M|b_n - b|

, so we need

|b_n - b| < \frac\varepsilon{2M}

. The second is

|b|\,|a_n - a|

, so we need

|a_n - a| < \frac{\varepsilon}{2|b|}

. If

b = 0

that divides by 0, so we use

|b| + 1

in its place, which is always positive and always at least

|b|

Choose

N_1

with

|b_n - b| < \frac{\varepsilon}{2M}

for

n > N_1

and

N_2

with

|a_n - a| < \frac{\varepsilon}{2(|b| + 1)}

for

n > N_2

. Let

N = \max(N_1, N_2)

Use the two convergences with these two tolerances, and take the later starting point so both hold at once.

For

n > N

|a_n b_n - ab| \le |a_n|\,|b_n - b| + |b|\,|a_n - a| < M \cdot \frac{\varepsilon}{2M} + |b| \cdot \frac{\varepsilon}{2(|b|+1)} \le \frac\varepsilon2 + \frac\varepsilon2 = \varepsilon

\blacksquare

Substitute the bounds. For the second piece,

|b| \le |b| + 1

makes

\frac{|b|}{|b|+1} \le 1

, so that piece is at most

\frac\varepsilon2

even when

b = 0

Proof of the constant-multiple law (2) and the quotient law (4)Abbott 2.3.3

The idea: The constant multiple is the product law with the constant sequence c, c, c, ... The quotient is the product law with the reciprocal sequence 1/b_n, so we only need 1/b_n tends to 1/b.

For (2): let

b_n = c

for all

n

, so

b_n \to c

The constant sequence

c, c, c, \dots

converges to

c

|c - c| = 0 < \varepsilon

for every

n

Then

c\,a_n = a_n b_n \to a c

\blacksquare

(2)

Product law (3) with this

b_n

For (4): first take

\varepsilon = \frac{|b|}{2}

b_n \to b

. There is

N_0

with

|b_n - b| < \frac{|b|}2

for

n > N_0

We want to show

\frac1{b_n} \to \frac1b

, for

b \ne 0

. Scratch work:

\left|\frac1{b_n} - \frac1b\right| = \frac{|b - b_n|}{|b_n|\,|b|}

, and the danger is

|b_n|

being tiny in the denominator, so we first show it stays away from 0.

So for

n > N_0

|b_n| > \frac{|b|}{2}

Triangle inequality:

|b| = |b - b_n + b_n| \le |b - b_n| + |b_n| < \frac{|b|}2 + |b_n|

Let

\varepsilon > 0

and choose

N_1

with

|b_n - b| < \frac{\varepsilon |b|^2}{2}

for

n > N_1

. For

n > \max(N_0, N_1)

\left|\frac1{b_n} - \frac1b\right| = \frac{|b_n - b|}{|b_n|\,|b|} < \frac{\varepsilon|b|^2/2}{(|b|/2)\,|b|} = \varepsilon

Combine the two facts: the numerator is small and the denominator is bounded below.

\frac1{b_n} \to \frac1b

, and

\frac{a_n}{b_n} = a_n \cdot \frac1{b_n} \to a \cdot \frac1b = \frac ab

\blacksquare

(4)

Product law with the sequences

a_n

and

\frac1{b_n}

Worked example

Find

\lim \dfrac{4n^2 + 3n}{n^2 - 2}

using the limit laws, naming the law used at each step.

Solution.

Divide top and bottom by the highest power. $\dfrac{4n^2 + 3n}{n^2 - 2} = \dfrac{4 + \frac3n}{1 - \frac2{n^2}}$ . Each part now has a limit we know. This is the school trick, and the laws are what make it legal.
Start from one known limit. $\frac1n \to 0$ . Archimedean property: for $\varepsilon > 0$ choose $N \ge \frac1\varepsilon$ , as in this chapter’s first examples.
Build the pieces. $\frac1{n^2} = \frac1n \cdot \frac1n \to 0 \cdot 0 = 0$ (product law). Then $\frac3n \to 3 \cdot 0 = 0$ and $\frac2{n^2} \to 0$ (constant-multiple law). Each new limit is made from earlier ones.
Top and bottom. Top: $4 + \frac3n \to 4 + 0 = 4$ (sum law, with the constant sequence 4). Bottom: $1 - \frac2{n^2} \to 1 - 0 = 1$ (sum law). A constant sequence converges to that constant.
Quotient. The bottom’s limit is $1 \ne 0$ , so the quotient law gives $\dfrac41 = 4$ . The quotient law needs the limit of the denominator to be non-zero. Here it is 1.

Answer. $\lim \dfrac{4n^2 + 3n}{n^2 - 2} = 4$ .

Worked example

Use the squeeze theorem to show

\frac{\sin n}{n} \to 0

Solution. The squeeze theorem says: if $a_n \le b_n \le c_n$ and $a_n, c_n \to L$ , then $b_n \to L$ . It is proved in general in the last problems; here is the idea at work.

Bound the awkward term. $-1 \le \sin n \le 1$ , so dividing by $n > 0$ : $-\frac1n \le \frac{\sin n}{n} \le \frac1n$ . We cannot compute $\sin n$ for large $n$ , but we know it is trapped between $-1$ and $1$ .
Check both outer sequences. $\frac1n \to 0$ and $-\frac1n \to 0$ (constant-multiple law with $c = -1$ ). Both outer sequences must have the same limit.
Squeeze. Let $\varepsilon > 0$ . Choose $N \ge \frac1\varepsilon$ . For $n > N$ : $-\varepsilon < -\frac1n \le \frac{\sin n}{n} \le \frac1n < \varepsilon$ , so $\left|\frac{\sin n}{n} - 0\right| < \varepsilon$ . This is the squeeze theorem with $L = 0$ , proved in one line here: when both outer sequences are inside the band, so is the middle one.

Answer. $\frac{\sin n}{n} \to 0$ .

Quick checkLet

a_n = \frac1n

and

b_n = \frac1n

. Both tend to

0

. Why can't the quotient law tell us the limit of

a_n / b_n

Proof workshopRebuild the proof that limits are unique

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Quick checkIn the product-law proof, why add and subtract

a_n b

Monotone sequences and completeness

Definition B

Monotone sequence

$(a_n)$ is increasing if $a_n \le a_{n+1}$ for all $n$ , decreasing if $a_n \ge a_{n+1}$ for all $n$ , and monotone if it is one or the other.

In one lineA sequence that only goes up ( $a_n \le a_{n+1}$ ) or only goes down ( $a_n \ge a_{n+1}$ ).

Why it existsFor monotone sequences, bounded is enough to converge; that is completeness in action.

Theorem B Abbott Thm 2.4.2

Monotone convergence theorem

If $(a_n)$ is increasing and bounded above, it converges, and its limit is $s = \sup\{a_n : n \in \mathbb N\}$ . (Similarly, decreasing and bounded below implies convergence to the infimum.)

In one lineAn increasing sequence that is bounded above converges, to the supremum of its terms.

Why it is trueThe supremum s is the target: the approximation property puts some term within ε of s, and every later term is even closer because the sequence only goes up.

ProofAbbott 2.4.2

The idea: Completeness gives s = sup of the terms. Given ε, the approximation property gives one term a_N above s − ε; since the sequence increases, every later term is also above s − ε, and none is above s.

Let

s = \sup\{a_n\}

The set of terms is non-empty and bounded above, so the completeness axiom gives a supremum.This is where completeness is used. Over the rationals, 1, 1.4, 1.41, 1.414, … is increasing and bounded but has no rational limit.

Let

\varepsilon > 0

Arbitrary tolerance.

There is

N

with

a_N > s - \varepsilon

Approximation property of the supremum (1.1).

For

n > N

s - \varepsilon < a_N \le a_n \le s

Increasing: later terms are at least

a_N

. Upper bound: no term exceeds

s

Hence

|a_n - s| < \varepsilon

for all

n > N

, and

a_n \to s

\blacksquare

a_n

lies in the band

(s - \varepsilon, s]

, within

\varepsilon

s

Proof workshopRebuild the proof of the monotone convergence theorem

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Worked example

Show that

a_n = 1 + \frac1{1!} + \frac1{2!} + \dots + \frac1{n!}

converges.

Solution.

Compute terms. $a_1 = 2$ , $a_2 = 2.5$ , $a_3 = 2.6667$ , $a_4 = 2.7083$ , $a_5 = 2.7167$ . The terms climb slowly. Scratch work: guess the behaviour. They look increasing and stuck below about 2.72.
Increasing. $a_{n+1} - a_n = \frac1{(n+1)!} > 0$ . Each step adds one positive term.
Bounded above. For $k \ge 2$ , $k! = 2 \cdot 3 \cdots k \ge 2^{k-1}$ , so $\frac1{k!} \le \frac1{2^{k-1}}$ . Then $a_n \le 1 + 1 + \frac12 + \frac14 + \dots + \frac1{2^{n-1}} < 1 + 2 = 3$ . We cannot sum the factorials, so we compare with a geometric sum we can: $1 + \frac12 + \frac14 + \dots < 2$ , because the partial sum $1 + \dots + \frac1{2^{n-1}} = 2 - \frac1{2^{n-1}}$ .
Apply the theorem. Increasing and bounded above, so it converges (monotone convergence), to the supremum of its terms. We never found the limit. Completeness guarantees it exists.

Answer. $a_n$ converges, and the limit is at most 3. (It is $e \approx 2.71828$ ; this is proved in chapter 1.6.)

Your answerFor

a_1 = 1

a_{n+1} = \frac12\left(a_n + \frac2{a_n}\right)

, compute

a_3

as a fraction.

Worked example the Babylonian method for $\sqrt 2$

The sequence

a_1 = 1

a_{n+1} = \frac12\left(a_n + \frac{2}{a_n}\right)

: show it converges and find the limit.

Solution.

Compute terms. $a_1 = 1$ , $a_2 = 1.5$ , $a_3 \approx 1.41667$ , $a_4 \approx 1.414216$ . After $a_1$ the terms go down, towards $\sqrt 2 \approx 1.414214$ . Scratch work: see the behaviour before proving it.
All terms are positive. $a_1 = 1 > 0$ , and if $a_n > 0$ then $a_{n+1} = \frac12(a_n + \frac2{a_n}) > 0$ . Induction. Positivity lets us divide by $a_n$ and keep inequalities the right way round below.
Bounded below by $\sqrt 2$ (for $n \ge 2$ ). $a_{n+1} - \sqrt 2 = \frac{(a_n - \sqrt 2)^2}{2a_n} \ge 0$ . Expand $\frac12(a_n + \frac2{a_n}) - \sqrt 2$ over the common denominator $2a_n$ ; the numerator is $a_n^2 - 2\sqrt2 a_n + 2 = (a_n - \sqrt 2)^2$ , a perfect square, and $2a_n > 0$ . So every term from $a_2$ on is $\ge \sqrt 2$ .
Decreasing (for $n \ge 2$ ). $a_{n+1} - a_n = \frac12\left(\frac2{a_n} - a_n\right) = \frac{2 - a_n^2}{2a_n} \le 0$ , because $a_n \ge \sqrt 2$ gives $a_n^2 \ge 2$ . Compute the difference and use step 3.
Converges. From $a_2$ on, the sequence is decreasing and bounded below, so it converges to the infimum $L$ of its terms (monotone convergence). Since $\sqrt 2$ is a lower bound and $L$ is the greatest lower bound, $L \ge \sqrt 2 > 0$ . The theorem gives existence of the limit without knowing its value. Dropping the first term does not change whether or where a sequence converges.
Find $L$ . The shifted sequence $a_{n+1}$ also tends to $L$ , and $\frac2{a_n} \to \frac2L$ by the quotient law (as $L \ne 0$ ). So the recursion gives $L = \frac12\left(L + \frac2L\right)$ , hence $2L^2 = L^2 + 2$ , so $L^2 = 2$ and $L = \sqrt 2$ (as $L > 0$ ). We may only take limits AFTER knowing the limit exists. Doing it first can give nonsense (see the traps).

Answer. $a_n \to \sqrt 2$ . Every $a_n$ is rational, yet the limit is not, so over $\mathbb Q$ this bounded decreasing sequence has no limit: completeness is doing real work. The error roughly squares at each step ( $a_2$ is off by $0.086$ , $a_3$ by $0.0025$ , $a_4$ by $0.0000021$ ), so the number of correct digits about doubles. This is Newton’s method for $x^2 = 2$ , and the same idea is used to compute square roots on computers.

Python labWatch the Babylonian sequence close in on the square root of 2

from fractions import Fraction
import math

c = 2          # we are computing the square root of c
a = 1.0        # the starting value a_1
for n in range(1, 8):
    err = a - math.sqrt(c)
    print(f"a_{n} = {a:.15f}   error = {err:.2e}")
    a = (a + c / a) / 2

# Every term is a fraction when you start from a fraction:
a = Fraction(1)
for n in range(1, 5):
    print(f"a_{n} = {a}")
    a = (a + Fraction(c) / a) / 2

Try this. Change c = 2 to c = 10 and the start to a = 100. How many steps until the error is below $10^{-12}$ ? Then count the correct digits at each step: they roughly double every time, because the next error is about the square of the current one (step 3 above).

Subsequences, Bolzano–Weierstrass and Cauchy sequences

Definition B

Subsequence

A subsequence of $(a_n)$ is $(a_{n_k}) = a_{n_1}, a_{n_2}, a_{n_3}, \dots$ where $n_1 < n_2 < n_3 < \dots$ are natural numbers.

In one lineA sequence formed by picking terms of $(a_n)$ in order, skipping any: $a_{n_1}, a_{n_2}, \dots$ with $n_1 < n_2 < \dots$ .

Why it existsEven a divergent sequence can have convergent subsequences; finding one is a key step in many existence proofs.

For $(-1)^n$ , the even-indexed terms form the subsequence $1, 1, 1, \dots$ , which converges.

Theorem B Abbott Thm 2.5.5

Bolzano–Weierstrass theorem

Every bounded sequence of real numbers has a convergent subsequence.

In one lineEvery bounded sequence has a convergent subsequence.

Why it is trueHalve the bounding interval forever, always keeping a half with infinitely many terms; the nested halves shrink to a point, and one term from each half gives the subsequence.

ProofAbbott 2.5.5

The idea: Bisection. Start with an interval containing every term. Halve it; one half contains infinitely many terms; keep that half and pick a term from it with a later index. Repeat. The halves are nested and shrink, so by the nested interval property (1.1) they close in on one point x, and the chosen terms converge to x.

Let

|a_n| \le M

for all

n

, and let

I_1 = [-M, M]

. Pick

n_1 = 1

Bounded means all terms lie in some interval.

Halve

I_1

. At least one half contains

a_n

for infinitely many

n

; call it

I_2

, and pick

n_2 > n_1

with

a_{n_2} \in I_2

If both halves had only finitely many terms, the whole sequence would have finitely many terms.

Continuing, we get nested intervals

I_1 \supseteq I_2 \supseteq \dots

, each half the length of the last, with

a_{n_k} \in I_k

and

n_1 < n_2 < \dots

Repeat the same step forever (induction).

Some

x

lies in every

I_k

Nested interval property (the stretch problem of 1.1), which uses completeness. Write

I_k = [c_k, d_k]

. Every left end

c_j

is at most every right end

d_m

(compare both with the later interval

I_{\max(j,m)}

), so

x = \sup\{c_k\}

exists and satisfies

c_k \le x \le d_k

for every

k

|a_{n_k} - x| \le \frac{2M}{2^{k-1}}

Both

a_{n_k}

and

x

lie in

I_k

, so they are at most the length of

I_k

apart. That length is

2M/2^{k-1}

So for

k > \frac{2M}\varepsilon

we get

|a_{n_k} - x| < \varepsilon

, and

a_{n_k} \to x

\blacksquare

Given

\varepsilon > 0

we need the bound below

\varepsilon

. Since

2^{k-1} \ge k

(induction),

\frac{2M}{2^{k-1}} \le \frac{2M}{k}

, which is below

\varepsilon

once

k > \frac{2M}{\varepsilon}

(Archimedean).

Quick checkThe sequence

a_n = (-1)^n \left(1 + \frac1n\right)

is bounded. Which statement about it is true?

Definition B

Cauchy sequence

$(a_n)$ is a Cauchy sequence if $\forall \varepsilon > 0\ \exists N\ \forall m, n > N:\ |a_m - a_n| < \varepsilon$ .

In one lineA sequence whose terms eventually stay close to EACH OTHER: for every ε > 0 there is N with $|a_m - a_n| < \varepsilon$ for all $m, n > N$ .

Why it existsIt describes convergence without naming the limit, which is how you prove a limit exists when you cannot compute it.

Theorem B Abbott Thm 2.6.4

Cauchy criterion

A sequence of real numbers converges if and only if it is a Cauchy sequence.

In one lineA sequence of real numbers converges if and only if it is Cauchy.

Why it is trueConvergent implies Cauchy by the triangle inequality. Cauchy implies bounded, so Bolzano–Weierstrass gives a convergent subsequence, and Cauchy forces the whole sequence to follow it.

ProofAbbott 2.6.4

The idea: (⇒) Terms close to L are close to each other: triangle inequality with ε/2 each. (⇐) A Cauchy sequence is bounded; Bolzano–Weierstrass gives a subsequence converging to some x; since all late terms are close to each other and some late terms are close to x, all late terms are close to x.

(

\Rightarrow

) Let

a_n \to L

and

\varepsilon > 0

. Choose

N

with

|a_n - L| < \frac\varepsilon2

for

n > N

Forward direction.

For

m, n > N

|a_m - a_n| \le |a_m - L| + |L - a_n| < \varepsilon

. So

(a_n)

is Cauchy.

Triangle inequality through

L

(

\Leftarrow

) Let

(a_n)

be Cauchy. It is bounded (same argument as for convergent sequences, using

a_{N+1}

in place of

L

Backward direction. First: bounded. With

\varepsilon = 1

, all terms after

N

are within 1 of

a_{N+1}

; the first

N

are finitely many.

So some subsequence

a_{n_k} \to x

Bolzano–Weierstrass.

Let

\varepsilon > 0

. Choose

N

with

|a_m - a_n| < \frac\varepsilon2

for

m, n > N

, and choose

k

with

n_k > N

and

|a_{n_k} - x| < \frac\varepsilon2

Two halves of the budget: Cauchy for

\varepsilon/2

, and the subsequence for

\varepsilon/2

. Such a

k

exists: the subsequence converges, so

|a_{n_k} - x| < \frac\varepsilon2

for all

k

above some

K

; and

n_k \ge k

(the indices strictly increase), so any

k > \max(K, N)

has

n_k > N

as well.

For

n > N

|a_n - x| \le |a_n - a_{n_k}| + |a_{n_k} - x| < \varepsilon

. So

a_n \to x

\blacksquare

Triangle inequality through

a_{n_k}

Quick checkOver the rationals,

1, 1.4, 1.41, 1.414, \dots

(decimal truncations of

\sqrt 2

) is a Cauchy sequence of rationals. Does it converge in

\mathbb Q

Worked example

Show that

a_n = 1 + \frac12 + \frac13 + \dots + \frac1n

is not Cauchy, so it diverges.

Solution. Not Cauchy means: there is an $\varepsilon$ such that for every $N$ we can find two terms beyond $N$ that are at least $\varepsilon$ apart. The sceptic picks the $\varepsilon$ and the two terms.

Write the negation. $\exists \varepsilon > 0\ \forall N\ \exists m, n > N:\ |a_m - a_n| \ge \varepsilon$ . The negation of the Cauchy definition (0.1).
Try a pair far apart. Take $m = 2n$ . Then $a_{2n} - a_n = \frac1{n+1} + \frac1{n+2} + \dots + \frac1{2n}$ . Neighbouring terms differ by $\frac1n$ , which is small, so we compare terms $n$ steps apart instead. The trap-box on neighbours below explains why.
Bound the sum from below. There are $n$ terms and each is at least $\frac1{2n}$ , so the sum is at least $n \cdot \frac1{2n} = \frac12$ . Every denominator is at most $2n$ , so every fraction is at least $\frac1{2n}$ .
Choose $\varepsilon$ and the pair. Take $\varepsilon = \frac12$ . For any $N$ , take $n = N + 1$ and $m = 2n$ . Both are beyond $N$ and $|a_m - a_n| \ge \frac12$ . This matches the negation in step 1.

Answer. The sequence is not Cauchy, so by the Cauchy criterion it does not converge. The terms $\frac1n \to 0$ , yet the sum grows without bound. $\blacksquare$

Your answerFor

a_n = \frac1n

and

\varepsilon = 0.1

, find the smallest

N

such that

|a_m - a_n| < \varepsilon

for ALL

m, n > N

. (Use that for

m, n > N

both terms lie in

(0, \frac1{N+1}]

, so the worst gap is just under

\frac1{N+1}

A preview· Preview: complete metric spaces

Chapter 4.2 uses “every Cauchy sequence converges” as the DEFINITION of a complete space, for spaces of vectors and functions. The contraction mapping theorem built on it proves that differential equations have solutions (7.1), and it is how MATH 376’s Picard iteration works.

Where it is used

Used inside maths· Inside maths: the definitions of continuity, derivative, integral and series

Chapter 1.3 defines continuity with $\varepsilon$ and $\delta$ ; 1.4 defines the derivative as a limit; 1.5 the integral as a limit of sums; 1.6 an infinite series as the limit of its partial sums. Each proof there reuses this chapter’s moves: the $\varepsilon/2$ split, add-and-subtract, bounded convergent sequences, and monotone convergence.

Used in the real world· Numerical computing: when to stop iterating

Iterative solvers (Newton’s method, gradient descent, the power method of 2.11) produce a sequence and must decide when to stop without knowing the limit. They use the Cauchy idea: stop when successive iterates differ by less than a tolerance, such as $|x_{k+1} - x_k| < 10^{-10}$ . The Cauchy criterion says that if this kept holding (for all later pairs), the sequence would converge. Production solvers combine this with checks on the residual because one small step alone does not prove the iterates have settled.

Traps

Watch out· Finding the limit before proving it exists

The sequence $a_1 = 1$ , $a_{n+1} = 2a_n$ gives $1, 2, 4, 8, \dots$ . “Taking limits” of $a_{n+1} = 2a_n$ gives $L = 2L$ , so " $L = 0$ ". The sequence diverges; the algebra was meaningless because no limit existed. Prove convergence first (for example by monotone convergence), then find the limit.

Watch out· N depends on ε, not on n

$N$ is chosen once $\varepsilon$ is known, and then must work for EVERY $n > N$ . “Choose $N = n + 1$ ” is meaningless.

Watch out· Terms getting closer to their neighbours is not enough

$a_n = \sqrt n$ has $a_{n+1} - a_n \to 0$ but diverges. Cauchy requires ALL pairs beyond $N$ to be close, not just neighbours.

Problems

check

For $a_n = \frac{1}{n}$ and $\varepsilon = 0.02$ , find an $N$ that works. Does $N = 40$ work? $N = 60$ ?

Solution

Need $\frac1n < 0.02$ for $n > N$ , i.e. $n > 50$ . $N = 50$ works, and so does any larger $N$ , such as 60. $N = 40$ fails: $n = 45$ gives $\frac1{45} \approx 0.022 > 0.02$ .

check

Write the negation of ” $(a_n)$ is a Cauchy sequence”.

Solution

$\exists \varepsilon > 0\ \forall N\ \exists m, n > N:\ |a_m - a_n| \ge \varepsilon$ .

check

Is every bounded sequence convergent? Is every convergent sequence bounded?

Solution

No: $(-1)^n$ is bounded and divergent. Yes: proved in this chapter.

useAbbott Exercise 2.2.2 style

Prove from the definition: $\frac{2n + 1}{5n + 4} \to \frac25$ .

Solution

Scratch: $\left|\frac{2n+1}{5n+4} - \frac25\right| = \left|\frac{5(2n+1) - 2(5n+4)}{5(5n+4)}\right| = \frac{3}{25n + 20} < \frac{3}{25n} < \frac1{8n}$ . Need $\frac{1}{8n} < \varepsilon$ : $n > \frac1{8\varepsilon}$ . Write-up: let $\varepsilon > 0$ , choose $N \ge \frac1{8\varepsilon}$ ; for $n > N$ , $\left|\frac{2n+1}{5n+4} - \frac25\right| < \frac1{8n} < \frac1{8N} \le \varepsilon$ .

use

Prove $\frac{n^2}{n^2 + 1} \to 1$ , choosing an explicit $N$ for each $\varepsilon$ .

Solution

$\left|\frac{n^2}{n^2+1} - 1\right| = \frac1{n^2 + 1} < \frac1n$ . Let $\varepsilon > 0$ and choose $N \ge \frac1\varepsilon$ . For $n > N$ : $\frac1{n^2+1} < \frac1n < \frac1N \le \varepsilon$ .

use

Using the limit laws (not the definition), find $\lim \frac{3n^2 - n}{2n^2 + 5}$ , saying which law each step uses.

Solution

Divide top and bottom by $n^2$ : $\frac{3 - \frac1n}{2 + \frac5{n^2}}$ . Since $\frac1n \to 0$ , the product law gives $\frac1{n^2} \to 0$ , the constant-multiple law gives $\frac5{n^2} \to 0$ , the sum law gives top $\to 3$ and bottom $\to 2$ , and the quotient law (bottom limit $2 \ne 0$ ) gives $\frac32$ .

proveAbbott Exercise 2.3.3 (squeeze)

Prove the squeeze theorem: if $a_n \le b_n \le c_n$ for all $n$ and $a_n \to L$ , $c_n \to L$ , then $b_n \to L$ .

Solution

Let $\varepsilon > 0$ . Choose $N$ so that for $n > N$ , $L - \varepsilon < a_n$ and $c_n < L + \varepsilon$ . Then $L - \varepsilon < a_n \le b_n \le c_n < L + \varepsilon$ , so $|b_n - L| < \varepsilon$ .

prove

Prove: if $a_n \to L$ and $L > 0$ , then $a_n > 0$ for all sufficiently large $n$ .

Solution

Take $\varepsilon = \frac L2 > 0$ . There is $N$ with $|a_n - L| < \frac L2$ for $n > N$ , so $a_n > L - \frac L2 = \frac L2 > 0$ .

proveAbbott Exercise 2.5.2 style

Prove that if $a_n \to L$ then every subsequence $a_{n_k} \to L$ . Use this to give a second proof that $(-1)^n$ diverges.

Solution

Let $\varepsilon > 0$ and choose $N$ with $|a_n - L| < \varepsilon$ for $n > N$ . Since $n_k \ge k$ (by induction, the indices strictly increase), for $k > N$ we have $n_k > N$ , so $|a_{n_k} - L| < \varepsilon$ . For $(-1)^n$ : the even subsequence tends to 1 and the odd one to $-1$ ; if the sequence converged to $L$ , both would tend to $L$ , forcing $1 = L = -1$ .

prove

Prove the sequence $a_n = 1 + \frac1{2^2} + \frac1{3^2} + \dots + \frac1{n^2}$ converges. (Hint: $\frac1{k^2} < \frac1{k(k-1)} = \frac1{k-1} - \frac1k$ for $k \ge 2$ .)

Solution

$(a_n)$ is increasing (each step adds a positive term). Bounded: $a_n < 1 + \sum_{k=2}^n \left(\frac1{k-1} - \frac1k\right) = 1 + 1 - \frac1n < 2$ , a telescoping sum. By monotone convergence it converges. (Its limit is $\frac{\pi^2}6$ , first proved by Euler in 1735. Monotone convergence tells you the limit exists without telling you its value.)

stretchAbbott Exercise 2.6 style

A sequence is contractive if there is a number $r$ with $0 < r < 1$ and $|a_{n+1} - a_n| \le r\,|a_n - a_{n-1}|$ for all $n \ge 2$ . Prove every contractive sequence is Cauchy, so it converges. (Hint: bound $|a_{n+1} - a_n|$ by $c\,r^{n-1}$ , then add up the steps from $n$ to $m$ with a geometric sum.)

Solution

Plan. A sequence whose steps shrink geometrically cannot wander far, so the tail is small.

Let $c = |a_2 - a_1|$ . Applying the condition repeatedly, $|a_{n+1} - a_n| \le c\,r^{n-1}$ . (Induction: true for $n = 1$ ; if $|a_n - a_{n-1}| \le c\,r^{n-2}$ then $|a_{n+1} - a_n| \le r\,c\,r^{n-2}$ .)
For $m > n$ , by the triangle inequality repeated, $|a_m - a_n| \le \sum_{k=n}^{m-1} |a_{k+1} - a_k| \le c\sum_{k=n}^{m-1} r^{k-1} \le c\,\dfrac{r^{n-1}}{1 - r}$ .
$r^{n} \to 0$ : write $r = \frac1{1+h}$ with $h > 0$ . Then $(1 + h)^n \ge 1 + nh > nh$ , so $r^n < \frac1{nh}$ .
Let $\varepsilon > 0$ . Using step 3 choose $N$ so that $c\,\dfrac{r^{N-1}}{1-r} < \varepsilon$ (possible since $r^{n-1} < \frac1{(n-1)h}$ gets arbitrarily small). Then for $m > n > N$ , $|a_m - a_n| \le c\,\dfrac{r^{n-1}}{1-r} \le c\,\dfrac{r^{N-1}}{1-r} < \varepsilon$ , because $r^{n-1} \le r^{N-1}$ . So $(a_n)$ is Cauchy, and converges by the Cauchy criterion. $\blacksquare$

Check with the Babylonian-style sequence $a_{n+1} = 1 + \frac12 a_n$ starting from $a_1 = 0$ : the steps are $1, \frac12, \frac14, \dots$ , so $r = \frac12$ , and the limit is $2$ .

Summary

$a_n \to L$ means: for every $\varepsilon > 0$ there is $N$ such that every term after $N$ is within $\varepsilon$ of $L$ . A game: they choose $\varepsilon$ , you choose $N$ (depending on $\varepsilon$ ).
Proofs: scratch work backwards from $|a_n - L| < \varepsilon$ to find $N$ (over-estimating freely), then a forward write-up starting “Let $\varepsilon > 0$ ”.
The moves: triangle inequality, the $\varepsilon/2$ split, add-and-subtract, “convergent implies bounded”.
Limit laws (sum, product, quotient) justify the school rules.
Monotone convergence: increasing and bounded above implies convergent, to the supremum. This is completeness.
Bolzano–Weierstrass: bounded sequences have convergent subsequences. Cauchy criterion: in $\mathbb R$ , convergent iff Cauchy.
Never “take limits of both sides” before proving the limit exists.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture: a game

Definitions

Sequence

Convergent sequence

Divergent sequence

How to prove a limit: scratch work, then write-up

The triangle inequality

Triangle inequality

The limit laws

Limits are unique

Convergent sequences are bounded

Algebraic limit laws

Monotone sequences and completeness

Monotone sequence

Monotone convergence theorem

Subsequences, Bolzano–Weierstrass and Cauchy sequences

Subsequence

Bolzano–Weierstrass theorem

Cauchy sequence

Cauchy criterion

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere