2 Sequences
Sequences are the fundamental tool in our approach to analysis.
2.7 Limits of Sequences
Definition 2.1. A sequence of real numbers is a list indexed by the natural numbers
( s
n
) = (s
1
, s
2
, s
3
, . . .)
We call s
1
the initial term/element.
More formally, we could view a sequence as a function s
n
: N → R. Other letters may be used
(a
n
, b
n
, etc.), though s
n
is typical in the abstract. It is also common to have sequences which start with
a different initial term (e.g., n = 0). If you need to be explicit, write, e.g., ( s
n
)
∞
n=0
.
Examples 2.2. 1. Explicit sequences are often defined by providing a formula for the n
th
term. For
instance, s
n
=
1 +
1
n
n
defines a sequence whose first three terms are
s
1
= 2, s
2
=
9
4
, s
3
=
64
27
, . . .
Since each term is a rational number, (s
n
) could be described as a rational sequence.
2. Sequences can be defined inductively. For instance, if t
1
= 1 and t
n+1
= 3t
n
−1, then
( t
n
) = (1, 2, 5, 14, 41, . . .)
3. u
n
=
1
n
2
−4
defines a sequence with initial term u
3
=
1
5
:
( u
n
)
∞
n=3
=
1
5
,
1
12
,
1
21
, . . .
Limits We are typically most interested in what happens to the terms of a sequence when n gets
large (one reason it is common to be non-explicit as to the initial term). In elementary calculus you
should have become used to examples such as
9
lim
2n
2
+ 3n −1
3n
2
−2
=
2
3
which encapsulates the idea that the expression s
n
=
2n
2
+3n−1
3n
2
−2
gets ‘close to’
2
3
when n is large. We
can easily convince ourselves of this with a calculator/computer: to 4 decimal places,
( s
n
) =
4, 1.3, 1.04, 0.9348, 0.8767, 0.8396, 0.8138, 0.7947, . . .
, s
1000
= 0.6677
Our primary business is to make this idea logically watertight, the major issue being what is meant
by ‘close to.’ In Section 2.8 we will do so by developing the formal definition of limit. Before seeing
this, we quickly refresh a few simple examples. All these examples can be made formal later, but for
the present just rely on your intuition and experience: it is essential to have a good idea of the correct
answer before you try to prove it!
9
If there are multiple letters around, writing lim
n→∞
with a subscript can aid the reader.
18
Examples 2.3. 1. lim
1
n
= 0. Our instinct is that s
n
=
1
n
becomes arbitrarily small as n becomes large.
2. lim
7n+9
2n−4
=
7
2
. To convince yourself of this, you might write
7n+9
2n−4
=
7+
9
n
2−
4
n
and observe that the
1
n
terms become tiny as n increases.
3. The sequence with n
th
term s
n
= (−1)
n
does not converge to anything: it diverges.
( s
n
)
∞
n=0
= (1, −1, 1, −1, 1, −1, . . .)
4. If c
n
=
1
n
cos
πn
6
, then lim c
n
= 0. To see this, observe that the cosine term lies between ±1,
while
1
n
has limit 0.
5. The sequence defined inductively by s
0
= 2, s
n+1
:=
1
2
s
n
+ 3 begins
( s
n
) =
2, 4, 5,
11
2
,
23
4
,
47
8
, . . .
This appears to have limit lim s
n
= 6. It is not hard to spot the pattern s
n
= 6 −
4
2
n
, which may
easily be verified by induction: for the induction step, observe that
1
2
s
n
+ 3 =
1
2
6 −
4
2
n
+ 3 = 6 −
4
2
n+1
Exercises 2.7. Key concepts: Sequences, Use your intuition!
1. Decide whether each sequence converges; if it does, state the limit. No proofs are required; if
you’re unsure what’s going on, try writing out the first few terms.
(a) a
n
=
1
3n + 1
(b) b
n
=
3n + 1
4n −1
(c) c
n
=
n
3
n
(d) d
n
= sin
nπ
4
2. Repeat the previous question for sequences whose n
th
term is as follows:
(a)
n
2
+ 3
n
2
−3
(b) 1 +
2
n
(c) 2
1/n
(d) (−1)
n
n (e)
7n
3
+ 8n
2n
3
−31
(f) sin
nπ
2
(g) sin
2nπ
3
(h)
2
n+1
+ 5
2
n
−7
(i)
1 +
1
n
2
(j)
6n + 4
9n
2
+ 7
3. Give an example of:
(a) A sequence (x
n
) of irrational numbers having a limit lim x
n
that is a rational number.
(b) A sequence (r
n
) of rational numbers having a limit lim r
n
that is an irrational number.
4. Prove by induction that the sequence defined in Example 2.2.2 has n
th
term t
n
=
1
2
3
n−1
+ 1
.
5. In future courses, you’ll meet sequences of functions. For instance, we could define a sequence
( f
n
) of functions f
n
: R → R inductively via
f
0
(x) ≡ 1, f
n+1
(x) := 1 +
Z
x
0
f
n
( t) dt
Compute the functions f
1
, f
2
and f
3
. The sequence ( f
n
) should seem familiar if you think back
to elementary calculus; why?
19
2.8 The Formal Definition of Limit
While intuition regarding limits is essential, mathematics is about proving things rigorously; for this
one needs a formal definition. The essential difficulty is that ‘close to’ is poorly defined without
context; we get round this by considering all possible measures of closeness simultaneously.
Definition 2.4. To say that a sequence (s
n
) converges to a limit s ∈ R means,
10
∀ϵ > 0, ∃N such that n > N =⇒
|
s
n
−s
|
< ϵ
We write lim s
n
= s or simply s
n
→ s; both are read “s
n
approaches (or tends to) s.”
A sequence converges if it has a limit, and diverges otherwise.
Try reading it this way: given any measure of closeness, we can make n large enough so that (by our
given measure) s
n
is close to s. This isn’t as hard as it looks, though a lot of examples will likely be
necessary for it to sink in. . .
Example 2.5. We prove that the sequence with
s
n
= 2 −
1
√
n
converges to s = 2.
By plotting the sequence, we see how ϵ controls
the distance (closeness) from s
n
to the limit s = 2;
no matter the size of ϵ, we must show that (s
n
) has
some tail whose terms are closer to s.
0
s
n
0 20 40 60
s + ϵ
s −ϵ
N
s = 2
n
n larger than this. . .
. . . guarantees s
n
here
Proving such ‘for all, there exists’ statements requires a specific argument structure:
• Suppose ϵ > 0 has been given and describe N as a function of ϵ (ϵ smaller means N larger).
• Verify algebraically that n > N =⇒
|
s
n
−s
|
< ϵ.
Scratch work. To find a suitable N, start with what you want to be true and let it inspire you.
Whenever n > N, we want ϵ >
|
s
n
−s
|
=
2 −
1
√
n
−2
=
1
√
n
.
Choosing N =
1
ϵ
2
should be enough to complete the proof!
Warning! “N =
1
ϵ
2
” is not the correct conclusion! To make it clear that we’ve satisfied the definition,
we rearrange our scratch work: these last three lines are all you need to write!
Formal argument. Suppose ϵ > 0 is given and let N =
1
ϵ
2
. Then
n > N =⇒
|
s
n
−s
|
=
2 −
1
√
n
−2
=
1
√
n
<
1
√
N
= ϵ
Thus lim s
n
= 2, as required.
10
N may be a real number or a natural number (equivalent by the Archimedean property, Theorem 1.22). It tends to be
easier to use N ∈ R for convergence and N ∈ N when directly proving divergence (see Definition 2.9 and Examples 2.10).
20
Lemma 2.6 (Uniqueness of Limit). If (s
n
) converges, then its limit is unique.
The proof structure should be familiar from other uniqueness arguments: assume there are two limits
s = t and obtain a contradiction. The picture explains the strategy: by choosing ϵ =
|
s−t
|
2
in the
definition we obtain a tail of the sequence which must be simultaneously close to both limits.
st
s + et −e
s+t
2
For all n > N, s
n
must lie both here and here!
Proof. Suppose s = t are two limits. Take ϵ =
|
s−t
|
2
and apply Definition 2.4 twice: ∃N
1
, N
2
such that
n > N
1
=⇒
|
s
n
−s
|
<
|
s − t
|
2
and n > N
2
=⇒
|
s
n
−t
|
<
|
s − t
|
2
Define N := max(N
1
, N
2
). Taking any n > N quickly yields a contradiction:
n > N =⇒
|
s − t
|
=
|
s − s
n
+ s
n
−t
|
≤
|
s
n
−s
|
+
|
s
n
−t
|
(△-inequality)
<
|
s − t
|
2
+
|
s − t
|
2
=
|
s − t
|
Theorem 2.7. If k > 0 is constant, then lim
1
n
k
= 0.
Proof. In this, and the examples that follow, only the formal arguments are required; scratch work is
included to show the thought process.
Scratch work. We want n > N =⇒
1
n
k
< ϵ. That is, n >
1
ϵ
1/k
. It should be enough to choose N =
1
ϵ
1/k
.
Formal argument. Suppose ϵ > 0 is given and let N =
1
ϵ
1/k
. Then
n > N =⇒
1
n
k
−0
=
1
n
k
<
1
N
k
= ϵ
We conclude that lim
1
n
k
= 0.
Examples 2.8. 1. We prove that lim
√
n + 4 −
√
n
= 0.
Scratch work. We use a (hopefully) familiar trick for manipulating surd expressions:
√
n + 4 −
√
n =
4
√
n + 4 +
√
n
<
4
2
√
n
=
2
√
n
Formal argument. Suppose ϵ > 0 is given and let N =
4
ϵ
2
. Then
n > N =⇒
√
n + 4 −
√
n
=
4
√
n + 4 +
√
n
<
4
2
√
n
=
2
√
n
<
2
√
N
= ϵ
Thus lim
√
n + 4 −
√
n
= 0.
21
2. We prove that lim
3n+1
n−7
= 3.
Scratch work. Given ϵ > 0, we want to choose N such that
n > N =⇒
3n + 1
n −7
−3
=
(3n + 1) − 3(n − 7)
n −7
=
22
n −7
< ϵ (∗)
For large n (n > 7) everything is positive, so it is sufficient to have n − 7 >
22
ϵ
. . .
Formal argument 1. Suppose ϵ > 0 is given and let N = 7 +
22
ϵ
. Then
n > N =⇒
3n + 1
n −7
−3
=
22
n −7
<
22
N −7
= ϵ
The absolute values are dropped since n > 7. We conclude that lim
3n+1
n−7
= 3.
Scratch work 2. An alternative approach is available if we play with (∗) a little. By insisting that
n ≥ 14, we can simplify the denominator n − 7 ≥
1
2
n =⇒
22
n−7
≤
44
n
.
Formal argument 2. Suppose ϵ > 0 is given and let N = max
14,
44
ϵ
. Then
n > N =⇒
3n + 1
n −7
−3
=
22
n −7
≤
22
1
2
n
=
44
n
(since n ≥ 14)
<
44
N
≤ ϵ (since N ≥
44
ϵ
)
We again conclude that lim
3n+1
n−7
= 3.
The plot illustrates the two choices of N as functions of ϵ.
The second is always larger than the first: if N = N
1
( ϵ)
works in a proof, then any larger choice N
2
( ϵ) will work
also; use this to your advantage to produce simpler argu-
ments!
0
0 1 2 3 4 5
N
1
= 7 +
22
ϵ
N
2
= max
14,
44
ϵ
ϵ
N
3. Given s
n
=
2n
4
−3n+1
3n
4
+n
2
+4
, we prove that lim s
n
=
2
3
.
Scratch work. We want to conclude that
2n
4
−3n+1
3n
4
+n
2
+4
−
2
3
=
−2n
2
−9n−5
3(3n
4
+n
2
+4)
< ϵ. Attempting to solve
for n is crazy! Instead we simplify the fraction using n ≥ 1 and the △-inequality:
−2n
2
−9n −5
3( 3n
4
+ n
2
+ 4)
△
≤
16n
2
3( 3n
4
+ n
2
+ 4)
<
16n
2
9n
4
<
2
n
2
(1 ≤ n ≤ n
2
and n
2
+ 4 > 0)
The final simplification is merely for additional cleanliness.
Formal argument. Suppose ϵ > 0 is given and let N =
q
2
ϵ
. Then,
n > N =⇒
2n
4
−3n + 1
3n
4
+ n
2
+ 4
−
2
3
=
−2n
2
−9n −5
3( 3n
4
+ n
2
+ 4)
△
≤
16n
2
3( 3n
4
+ n
2
+ 4)
(n ≥ 1)
<
16n
2
9n
4
<
2
n
2
<
2
N
2
= ϵ
Other choices of N are feasible (e.g., Exercise 3); everything depends on how you want to
simplify things in your scratch work.
22
Divergent sequences
By negating Definition 2.4, we obtain explicit criteria for divergence.
Definition 2.9. A sequence (s
n
) does not converge to s ∈ R if,
∃ϵ > 0 such that ∀N, ∃n > N with
|
s
n
−s
|
≥ ϵ
A sequence is divergent if it does not converge to any limit s ∈ R. Otherwise said,
∀s ∈ R, ∃ϵ > 0 such that ∀N, ∃n > N with
|
s
n
−s
|
≥ ϵ
Examples 2.10. 1. We prove that the sequence with s
n
=
7
n
does not converge to s = 2.
Scratch work. Of course the limit is really 0.
If ϵ is anything smaller than 2, then s
n
will
eventually be further than ϵ from s = 2.
Choosing ϵ = 1 should be enough. In-
deed, since we only care about large n,
|
s
n
−2
|
=
7
n
−2
= 2 −
7
n
≥ 1 ⇐⇒ n ≥ 7
0
4
6
s
n
0 5 10 15
s = 2
s + ϵ
s −ϵ
n
Every tail contains some
s
n
that do not lie here
Direct proof. Let ϵ = 1. Given N ∈ N, let n = max(7, N + 1). Then n > N and
|
s
n
−2
|
=
7
n
−2
= 2 −
7
n
≥ 1 = ϵ
Contradiction proof. For an alternative approach, suppose lim s
n
= 2 and let ϵ = 1 in Definition
2.4. Then ∃N such that
n > N =⇒
7
n
−2
< 1 =⇒ 1 <
7
n
< 3 =⇒
7
3
< n < 7
This last is false for large n, in particular for n := max(7, N + 1). Contradiction.
While the two arguments are similar, the contradiction approach has the advantage in that you
need only remember one definition!
2. We prove (just by contradiction this time) that s
n
= (−1)
n
defines a divergent sequence.
Suppose that lim s
n
= s and let ϵ = 1 in the definition
of limit. Then ∃N ∈ N such that
n > N =⇒
|
( −1)
n
−s
|
< 1
=⇒ (−1)
n
−1 < s < 1 + (−1)
n
Choosing any even n > N forces 0 < s; any odd
n > N forces s < 0: contradiction.
−1
1
2
10
s + ϵ
s −ϵ
N
s
n
s
n
The choice of ϵ = 1 was suggested by the picture: if ϵ = 1, then, regardless of N, there exist
n > N with
|
s
n
−s
|
> 1.
23
3. We prove directly that the sequence defined by s
n
= ln n is divergent.
Scratch work. Since logarithms increase unboundedly,
11
for large n we should have ln n ≥ s + 1,
for any purported limit s ∈ R.
Proof. Suppose s ∈ R is given and let ϵ = 1. Given N ∈ N, define n = max(N + 1, e
s+1
). Then
n > N and ln n ≥ ln(e
s+1
) = s + 1 (ln is increasing)
=⇒
|
s
n
−s
|
= ln n −s ≥ 1 = ϵ
We conclude that (s
n
) is divergent.
Bounded Sequences
As a first taste using the limit definition abstractly, we consider several related results regarding the
boundedness of sequences.
Theorem 2.11. Suppose (s
n
) is convergent: lim s
n
= s.
1. If s
n
≥ m for all large
12
n, then lim s
n
≥ m.
2. If s
n
≤ M for all large n, then lim s
n
≤ M.
3. (s
n
) is bounded (∃M such that ∀n,
|
s
n
|
≤ M).
Proof. 1. We prove the contrapositive. Suppose s < m and let ϵ =
m−s
2
> 0. Then ∃N such that
n > N =⇒
|
s
n
−s
|
<
m − s
2
=⇒ s
n
−s <
m − s
2
=⇒ s
n
−m <
s − m
2
< 0 =⇒ s
n
< m
2. This is almost identical to part 1.
3. The picture shows the strategy: taking ϵ = 1 in the limit
definition bounds an infinite tail of the sequence; the
finitely many terms that come before are a non-issue.
Let ϵ = 1 in the definition of limit. Then ∃N such that
n > N =⇒
|
s
n
−s
|
< 1 =⇒ s −1 < s
n
< s + 1
=⇒
|
s
n
|
< max{
|
s −1
|
,
|
s + 1
|
}
It follows that every term of the sequence is bounded by
M := max
|
s −1
|
,
|
s + 1
|
,
|
s
n
|
: n ≤ N
s
n
s + 1
s −1
s
N
n
bounded tail
11
Definition 2.19 will state what it means for a sequence to diverge to ∞: this isn’t (yet) what we’re trying to demonstrate.
12
Equivalently s
n
≥ m for all but finitely many n. In the language of the proof, for all n expect perhaps when n ≤ N.
Since we typically care only about large n, this caveat is sometimes left unstated: e.g., s
n
≥ m =⇒ lim s
n
≥ m.
24
Theorem 2.12 (Squeeze Theorem). Suppose sequences satisfy a
n
≤ s
n
≤ b
n
(for all large n), where
the two outer sequences converge to s. Then lim s
n
= s.
Proof. Subtract s from the assumed inequality to obtain
a
n
−s ≤ s
n
−s ≤ b
n
−s =⇒
|
s
n
−s
|
≤ max
|
a
n
−s
|
,
|
b
n
−s
|
Suppose ϵ > 0 is given. Since lim a
n
= s = lim b
n
, there exist N
a
, N
b
such that
n > N
a
=⇒
|
a
n
−s
|
< ϵ and n > N
b
=⇒
|
b
n
−s
|
< ϵ
Now let N = max(N
a
, N
b
) to see that
n > N =⇒
|
s
n
−s
|
≤ max
|
a
n
−s
|
,
|
b
n
−s
|
< ϵ
Example 2.13. Since 0 ≤
1+sin n
n
≤
2
n
for all n, the squeeze theorem forces lim
1+sin n
n
= 0.
Exercises 2.8. Key concepts: ϵ–N definition, divergence, boundedness, squeeze theorem
1. For each sequence, determine the limit and prove your claim.
(a) a
n
=
n
n
2
+1
(b) b
n
=
7n−19
3n+7
(c) c
n
=
4n+3
7n−5
(d) d
n
=
2n+4
5n+2
(e) e
n
=
1
n
sin n (f) f
n
=
n
2
+n−1
3n
2
−10
2. Prove:
(a) lim[
√
n
2
+ 1 − n] = 0 (b) lim[
√
n
2
+ n −n] =
1
2
(c) lim[
√
4n
2
+ n −2n] =
1
4
3. (a) Show that n ≥ 2 =⇒ 2n
2
+ 9n + 5 ≤ 9n
2
.
(b) (Example 2.8.3) Give another proof that lim
2n
4
−3n+1
3n
4
+n
2
+4
=
2
3
by choosing N = max
2,
1
√
ϵ
.
4. (a) Prove that the sequence with n
th
term s
n
=
2
n
2
does not converge to −1.
(b) Prove that (s
n
) does not converge to 1.
5. Prove that the sequence defined by t
n
= n
2
diverges.
6. (Example 2.10.3) Prove by contradiction that ( ln n) diverges.
7. True or false: if (s
n
) is bounded, then it is convergent. Explain.
8. Let (t
n
) be bounded, and let ( s
n
) satisfy lim s
n
= 0. Prove that lim(s
n
t
n
) = 0.
9. We extend Theorem 2.11.
(a) Suppose lim s
n
= s where every s
n
> m. Can we conclude that s > m? Explain.
(b) Let (s
n
) be convergent and suppose lim s
n
> a. Prove that ∃N such that n > N =⇒ s
n
> a.
10. Suppose s ∈ R. Prove:
(a) lim s
n
= s ⇐⇒ lim(s
n
−s) = 0
(b) lim s
n
= s =⇒ lim
|
s
n
|
=
|
s
|
25
2.9 Limit Theorems for Sequences
We’d like to develop rules for limits so that we don’t have to resort to ϵ–N proofs every time. The
rough idea of these results is that limits respect the basic rules of algebra. Rather than dive straight
into abstract proofs, we start with two special cases that illustrate commonly encountered tricks.
Examples 2.14. Suppose that (s
n
) converges to s. We prove that lim 5s
n
= 5s and that lim s
2
n
= s
2
.
1. The sequence (5s
n
) is obtained by multiplying the original terms by 5. To prove lim 5s
n
= 5s
we must show:
∀ϵ > 0, ∃N such that n > N =⇒
|
5s
n
−5s
|
< ϵ (∗)
This last amounts to observing that
|
s
n
−s
|
<
ϵ
5
. Since
ϵ
5
is simply another small number, (∗) is
just the statement lim s
n
= s in disguise! Here is a formal argument.
Let ϵ > 0 be given. Since lim s
n
= s, we know that
13
∃N such that n > N =⇒
|
s
n
−s
|
<
ϵ
5
=⇒
|
5s
n
−5s
|
< ϵ
2. The challenge is to make
s
2
n
−s
2
=
|
s
n
−s
||
s
n
+ s
|
small. The first term can be made arbitrarily
small by the hypothesis lim s
n
= s. To control the second, we use the triangle-inequality:
|
s
n
+ s
|
=
|
s
n
−s + 2s
|
≤
|
s
n
−s
|
+ 2
|
s
|
Assuming
|
s
n
−s
|
≤ 1 gives a bound
|
s + s
n
|
≤ 1 + 2
|
s
|
. We now have enough for a proof.
Suppose lim s
n
= s, that ϵ > 0 is given and let δ = min( 1,
ϵ
1+2
|
s
|
). Then ∃N such that,
n > N =⇒
|
s
n
−s
|
< δ ≤ 1
=⇒
s
2
n
−s
2
=
|
s
n
−s
||
s
n
+ s
|
△
≤
|
s
n
−s
|
(
|
s
n
−s
|
+ 2
|
s
|
)
< δ(1 + 2
|
s
|
) ≤ ϵ
Theorem 2.15 (Limit laws). Limits respect algebraic operations: ±, ×, ÷ and rational roots.
More specifically, if (s
n
) converges to s and (t
n
) to t, then,
1. lim(s
n
±t
n
) = s ± t
2. lim(s
n
t
n
) = st; in particular, if k is constant, then lim ks
n
= ks
3. If t = 0, then lim
s
n
t
n
=
s
t
4. If k ∈ N, then lim
k
√
s
n
=
k
√
s, provided the roots exist (s
n
, s ≥ 0 if k even)
By part 4 and induction on part 2, lim s
q
n
= s
q
for any q ∈ Q.
Examples 2.14 are special cases of part 2 (k = 5 and then t
n
= s
n
).
13
It is non-standard, but if this approach makes you squeamish, you can introduce a second
˜
ϵ:
Given ϵ > 0, let
˜
ϵ =
ϵ
5
, then ∃N such that n > N =⇒
|
s
n
−s
|
<
˜
ϵ =⇒
|
5s
n
−5s
|
< ϵ.
26
Rigorously proving the limit laws takes some work. Before engaging in some of this, we advertise
their benefit by performing some calculations as you might have seen in elementary calculus.
Examples 2.16. 1. We evaluate lim
3n
2
+2
√
n−1
5n
2
−2
using the limit laws.
lim
3n
2
+ 2
√
n −1
5n
2
−2
= lim
3 +
2
n
3/2
−
1
n
2
5 −
2
n
2
(n > 0)
=
lim
3 +
2
n
3/2
−
1
n
2
lim
5 −
2
n
2
(part 3)
=
lim 3 + lim
2
n
3/2
−lim
1
n
2
lim 5 −lim
2
n
2
(part 1)
=
3 + 0 −0
5 −0
=
3
5
(parts 2, 4 and Theorem 2.7))
The calculation involves some generally accepted sleight of hand: none of the limits should
really be written until one knows they exist. To be completely logical would require us to
rewrite the argument upside down, though to sacrifice readability in this manner would be
ill-advised.
2. Suppose (s
n
) is defined inductively via s
1
= 2 and s
n+1
=
1
2
( s
n
+
2
s
n
):
( s
n
) =
2,
3
2
,
17
12
,
577
408
, . . .
This sequence in fact converges, though a proof requires ideas from Section 2.10. Given this
fact, the limit laws allow us to compute the limit s:
s = lim s
n+1
=
1
2
lim s
n
+
2
lim s
n
=
1
2
s +
2
s
=⇒
1
2
s =
1
s
=⇒ s
2
= 2
Since s
n
is plainly always positive, we conclude that lim s
n
=
√
2.
We now commence our assault on the limit laws.
Proof. 1. We use a trick similar to that in Example 2.14.1: control both sequences so that both
|
s
n
−s
|
,
|
t
n
−t
|
<
ϵ
2
, then sum.
Suppose ϵ > 0 is given. Since lim s
n
= s and lim t
n
= t, we see that ∃N
1
, N
2
such that
n > N
1
=⇒
|
s
n
−s
|
<
ϵ
2
and n > N
2
=⇒
|
t
n
−t
|
<
ϵ
2
Let N = max(N
1
, N
2
), then
n > N =⇒
|
s
n
+ t
n
−(s + t)
|
△
≤
|
s
n
−s
|
+
|
t
n
−t
|
<
ϵ
2
+
ϵ
2
= ϵ
The argument for s
n
−t
n
is almost identical.
27
2. Exercise 2.8.8 deals with (and extends) the case when s = 0. We therefore suppose s = 0. The
approach is similar to part 1, we just need to be a bit cleverer to break up
|
s
n
t
n
−st
|
.
Suppose ϵ > 0 is given. By Theorem 2.11, (t
n
) is bounded:
∃M such that ∀n,
|
t
n
|
≤ M
We make assume, WLOG, that M > 0. Since lim s
n
= s and lim t
n
= t, ∃N
1
, N
2
such that
n > N
1
=⇒
|
s
n
−s
|
<
ϵ
2M
and n > N
2
=⇒
|
t
n
−t
|
<
ϵ
2
|
s
|
Let N = max(N
1
, N
2
), then
|
s
n
t
n
−st
|
=
|
s
n
t
n
−st
n
+ st
n
−st
|
△
≤
|
s
n
−s
||
t
n
|
+
|
s
||
t
n
−t
|
<
ϵ
2M
M +
|
s
|
ϵ
2
|
s
|
= ϵ
3 & 4.: See Exercise 7.
With a few general examples, the limit laws allow us to rapidly compute a great variety of limits.
Theorem 2.17. 1. If
|
a
|
< 1 then lim a
n
= 0
2. If a > 0 then lim a
1/n
= 1
3. lim n
1/n
= 1
Examples 2.18. 1. lim(3n)
2/n
= (lim 3
1/n
)
2
(lim n
1/n
)
2
= 1.
2. Observe from the squeeze theorem (2.12) that
sin n
n
≤
1
n
→ 0. We conclude:
lim
n
2/n
+
3 −n
−1
sin n
1/5
4n
−3/2
+ 7
=
(lim n
1/n
)
2
−
3 −lim
sin n
n
1/5
4 lim
1
n
3/2
+ 7
=
1 −
5
√
3
7
Proof. 1. The a = 0 case is trivial. Otherwise, given ϵ > 0, let N = log
|
a
|
ϵ, then
n > N =⇒
|
a
n
|
<
a
N
=
|
a
|
N
= ϵ
2. Suppose a ≥ 1 and let s
n
= a
1/n
−1. Since s
n
> 0, the binomial theorem
14
shows that
a = (1 + s
n
)
n
≥ 1 + ns
n
=⇒ 0 < s
n
≤
a −1
n
The squeeze theorem shows that lim s
n
= 0, whence lim a
1/n
= 1.
The a < 1 case and part 3 are in Exercise 8.
14
(1 + x)
n
=
n
∑
k=0
(
n
k
)
x
k
= 1 + nx +
n(n−1)
2
x
2
+
n(n−1)(n−2)
2·3
x
3
+ ··· + x
n
.
28
Divergence to ±∞ and the ‘divergence laws’
We consider unbounded sequences and provide a positive definition of a type of divergence.
Definition 2.19. We say that (s
n
) diverges to ∞ if,
∀M > 0, ∃N such that n > N =⇒ s
n
> M
We write lim s
n
= ∞, or s
n
→ ∞, and say that s
n
‘tends to’ ∞. The definition for s
n
→ −∞ is similar.
If (s
n
) neither converges nor diverges to ±∞, we say that it diverges by oscillation: you likely wrote
lim s
n
= DNE (“does not exist”) in elementary calculus.
Consider how M describes “closeness” to infinity analogously to how ϵ measures closeness to s in
the original definition of limit (2.4).
Examples 2.20. As with convergence arguments, some scratch work might be helpful.
1. We show that lim(n
2
+ 4n) = ∞.
Let M > 0 be given, and let N =
√
M. Then
n > N =⇒ n
2
+ 4n > n
2
> N
2
= M
2. We prove that s
n
= n
5
−n
4
−2n + 1 diverges to ∞.
The negative terms cause some trouble, though our solution should be familiar from previous
calculations:
s
n
>
1
2
n
5
⇐⇒ n
5
> 2(n
4
+ 2n −1) ⇐⇒ n > 2 +
4
n
3
−
1
n
4
Certainly this holds if n > 6. We can now complete the proof.
Let M > 0 be given, and let N = max(6,
5
√
2M). Then
n > N =⇒ s
n
>
1
2
n
5
>
1
2
(2M) = M
3. We prove that s
n
= n
2
−n
3
diverges to −∞.
First observe that
s
n
= n
2
(1 − n) < −
1
2
n
3
⇐⇒ 1 − n < −
1
2
n ⇐⇒ n ≥ 2
Now let M > 0 be given,
15
and define N = max(2,
3
√
2M). Then
n > N =⇒ n > 2 =⇒ s
n
< −
1
2
n
3
< −
1
2
N
3
≤ −M
15
You may prefer to phrase lim s
n
= −∞ instead as
∀m < 0, ∃N such that n > N =⇒ s
n
< m (in our argument M = −m)
29
Several of the limit laws can be adapted to sequences which diverge to ±∞.
Theorem 2.21. Suppose lim s
n
= ∞.
1. If t
n
≥ s
n
for all (large) n, then lim t
n
= ∞
2. If lim t
n
exists and is finite, then lim s
n
+ t
n
= ∞.
3. If lim t
n
> 0 then lim s
n
t
n
= ∞.
4. lim
1
s
n
= 0
5. If lim t
n
= 0 and t
n
> 0 for all (large) n, then lim
1
t
n
= ∞
Similar statements when lim s
n
= −∞ should be clear.
Proof. We prove two parts; try the rest yourself.
2. Since (t
n
) converges, it is bounded (below): ∃m such that ∀n, t
n
≥ m. Let M be given. Since
lim s
n
= ∞, ∃N such that
n > N =⇒ s
n
> M −m =⇒ s
n
+ t
n
> M −m + m = M
4. Let ϵ > 0 be given, and let M =
1
ϵ
. Then ∃N such that
n > N =⇒ s
n
> M =
1
ϵ
=⇒
1
s
n
< ϵ
Rational Sequences
We can now describe the limit of any sequence
p
n
q
n
where (p
n
), ( q
n
) are polynomials in n.
Example 2.22. By applying Theorem 2.21 (part 3) to
s
n
:= 3n + 4n
−2
→ ∞ and t
n
=
1
2 −n
−2
→
1
2
we see that
lim
3n
3
+ 4
2n
2
−1
= lim
3n + 4n
−2
2 −n
−2
= lim(3n + 4n
−2
) ·lim
1
2 −n
−2
= ∞
More generally, you should be able to confirm a familiar result from elementary calculus:
Corollary 2.23. If p
n
, q
n
are polynomials in n with leading coefficients p, q respectively then
lim
p
n
q
n
=
0 if deg(p
n
) < deg(q
n
)
p
q
if deg(p
n
) = deg(q
n
)
sgn(
p
q
) ∞ if deg(p
n
) > deg(q
n
)
30
Exercises 2.9. Key concepts: Divergence to ±∞, Limit/divergence laws, lim a
1/n
= 1 = lim n
1/n
1. Suppose lim x
n
= 3, lim y
n
= 7 and that all y
n
are non-zero. Determine the following:
(a) lim(x
n
+ y
n
) (b) lim
3y
n
−x
n
y
2
n
(c) lim
p
x
n
y
n
+ 4
2. Suppose s ∈ R. Prove that lim s
n
= s =⇒ lim s
3
n
= s
3
by mimicking Example 2.14.2.
3. Let s
n
= (100n)
100
n
. Describe s
1
and s
10
(1 followed by how many zeros?). Now compute lim s
n
.
4. Define (s
n
) inductively via s
1
= 1 and s
n+1
=
√
s
n
+ 1 for n ≥ 1.
(a) List the first four terms of (s
n
).
(b) It turns out that (s
n
) converges. Assume this and prove that lim s
n
=
1
2
(1 +
√
5) .
5. Prove:
(a) lim(n
3
−98n) = ∞ (b) lim
√
n − n +
4
n
= −∞
6. Let x
1
= 1 and x
n+1
= 3x
2
n
for n ≥ 1.
(a) Show that if (x
n
) converges with limit a, then a =
1
3
or a = 0.
(b) What is lim x
n
? Prove your assertion and explain what is going on.
7. We prove parts 3 and 4 of the limit laws (Theorem 2.15). Assume lim s
n
= s and lim t
n
= t.
(a) Suppose t = 0. Explain why ∃N
1
such that n > N
1
=⇒
|
t
n
|
>
1
2
|
t
|
.
(b) Let ϵ > 0 be given. Since lim t
n
= t, ∃N
2
such that n > N
2
=⇒
|
t
n
−t
|
<
1
2
|
t
|
2
ϵ. Combine
N
1
and N
2
to prove that lim
1
t
n
=
1
t
.
(c) Explain how to conclude part 3: lim
s
n
t
n
=
s
t
.
(d) Use the following inequality (valid when s
n
, s > 0) to construct a proof for part 4
s
1/k
n
−s
1/k
=
|
s
n
−s
|
s
k−1
k
n
+ s
k−2
k
n
s
1
k
+ ··· + s
k−1
k
≤
|
s
n
−s
|
s
k−1
k
8. We finish the proof of Theorem 2.17.
(a) Suppose 0 < a < 1. By considering b =
1
a
, prove that lim a
1/n
= 1.
(b) Let s
n
= n
1/n
−1. Apply the binomial theorem to n = (1 + s
n
)
n
to prove that s
n
<
q
2
n−1
.
Hence conclude that lim n
1/n
= 1.
9. Prove the remaining parts of Theorem 2.21.
10. Assume s
n
= 0 for all n and that the limit L = lim
s
n+1
s
n
exists.
(a) Show that if L < 1, then lim s
n
= 0.
(Hint: if L < a < 1, obtain N so that n > N =⇒
|
s
n
|
< a
n−N
|
s
N
|
)
(b) Show that if L > 1, then lim
|
s
n
|
= +∞.
(Hint: apply (a) to the sequence t
n
=
1
|
s
n
|
)
11. Let p > 0 and a ∈ R be given. How does lim
n→∞
a
n
n
p
depend on the value of a?
31
2.10 Monotone and Cauchy Sequences
The definition of limit (Definition 2.4) has a major weakness: to demonstrate the convergence of
a sequence we must already know its limit! What we’d like is a method for determining whether a
sequence converges without first guessing a suitable limit.
16
In this section we consider two important
classes of sequence for which this can be done.
Definition 2.24. A sequence (s
n
) is said to be:
• Monotone-up
17
if s
n+1
≥ s
n
for all n.
• Monotone-down if s
n+1
≤ s
n
for all n.
• Monotone if either of the above is true.
Examples 2.25. 1. The sequence with n
th
term s
n
=
7
n
+ 4 is (strictly) monotone-down:
s
n+1
=
7
n + 1
<
7
n
= s
n
2. A constant sequence (s
n
) = (s, s, s, s, . . .) is both monotone-up and monotone-down.
Theorem 2.26 (Monotone Convergence).
Every bounded monotone sequence is convergent.
Specifically:
• If (s
n
) is bounded above and monotone-up,
then lim s
n
exists and equals sup{s
n
}.
• If (s
n
) is bounded below and monotone-down,
then lim s
n
exists and equals inf{s
n
}.
n
s
n
sup{s
n
}
In fact the conclusion lim s
n
= sup{s
n
} holds for all monotone-up sequences: if unbounded above,
then the result is ∞ (Exercise 5).
Proof. If (s
n
) is bounded above, then s := sup{s
n
} exists by the completeness axiom (s is finite!).
Let ϵ > 0 be given. By Lemma 1.20, there exists some s
N
> s − ϵ. Since (s
n
) is monotone-up,
n > N =⇒ s
n
≥ s
N
> s − ϵ =⇒ 0 ≤ s −s
n
< ϵ =⇒
|
s − s
n
|
< ϵ
The monotone-down case is similar.
16
This gets at a typical application of sequences: given a sequence whose elements have a useful property, one demon-
strates the existence of a new object (the limit) to which (hopefully!) the useful property transfers. For instance, if ( f
n
)
is a sequence of differentiable functions, we’d like to know if lim f
n
(x) exists and is itself differentiable with derivative
lim f
′
n
(x). Discussions of this ilk dominate Math 140B.
17
Some authors describe a monotone-up sequence as either non-decreasing or increasing. We prefer monotone-up since
it directly describes the direction of any possible movement in the sequence and prevents confusion over whether the
inequality is strict. If necessary, a sequence with s
n+1
> s
n
may be described as strictly increasing or strictly monotone-up.
32
Examples 2.27. 1. Define (s
n
) via s
n
= 1 and s
n+1
=
1
5
( s
n
+ 8):
( s
n
) =
1, 1.8, 1.96, 1.992, 1.9984, 1.99968, . . .
This sequence certainly appears to be monotone-up and converging to 2. Here is a proof:
Bounded above: s
n
< 2 =⇒ s
n+1
<
1
5
[
2 + 8
]
= 2. By induction, (s
n
) is bounded above by 2.
Monotone-up: s
n+1
−s
n
=
4
5
[
2 −s
n
]
> 0 since s
n
< 2.
Convergence: By monotone convergence, s = lim s
n
exists. Now use the limit laws to find s:
s = lim s
n+1
=
1
5
(
lim s
n
+ 8
)
=
1
5
( s + 8) =⇒ s = 2
2. (Example 2.16.2, cont.) Let s
1
= 2 and s
n+1
=
1
2
s
n
+
2
s
n
.
Bounded below: The sequence is plainly always positive and thus bounded below by zero.
Monotone-down: We first obtain an improved lower bound:
s
2
n+1
=
1
4
s
n
+
2
s
n
2
= 2 +
1
4
s
n
−
2
s
n
2
≥ 2
shows
18
that s
2
n
≥ 2 for all n. It follows that
s
n+1
s
n
=
1
2
1 +
2
s
2
n
≤ 1 =⇒ s
n+1
≤ s
n
Convergence: By monotone convergence, s = lim s
n
exists. Example 2.16.2 provides the limit:
s =
1
2
s +
2
s
=⇒ s =
√
2
This shows the necessity of completeness: (s
n
) is a monotone, bounded sequence of rational
numbers, but its limit is irrational.
3. A decimal number d
0
.d
1
d
2
d
3
. . . is the limit of a monotone-up sequence of rational numbers:
d
0
.d
1
d
2
d
3
. . . = d
0
+ lim
n→∞
n
∑
k=1
d
k
10
k
This is bounded above (by d
0
+ 1 ∈ Z) and so converges.
4. The sequence with s
n
=
1 +
1
n
n
is particularly famous. In Exercise 10 we show that (s
n
) is
monotone-up and bounded above. The limit provides, arguably, the oldest definition of e:
e := lim
1 +
1
n
n
18
This is the famous AM–GM inequality
x+y
2
≥
√
xy with x = s
n
and y =
2
s
n
.
33
Limits Superior and Inferior
One interpretation of lim s
n
is that it approximately describes s
n
for large n. Even when a sequence
does not have a limit, it is useful to be able to describe its long-term behavior.
Definition 2.28. Let (s
n
) be a sequence and define two related sequences (v
N
) and ( u
N
):
v
N
:= sup{s
n
: n ≥ N}, u
N
:= inf{s
n
: n ≥ N}
1. The limit superior of (s
n
) is
lim sup s
n
=
(
lim
N→∞
v
N
if (s
n
) bounded above
∞ if (s
n
) unbounded above
2. The limit inferior of (s
n
) is
lim inf s
n
=
(
lim
N→∞
u
N
if (s
n
) bounded below
−∞ if (s
n
) unbounded below
0
s
n
0
lim sup s
n
lim inf s
n
v
N
u
N
n
The original sequence (s
n
) is wedged between (v
n
) and (u
n
) in a manner reminiscent of the squeeze
theorem (though lim sup and lim inf need not be equal). The next result summarizes the situation
more formally; we omit the proof since these claims should be clear from the definition and previous
results, particularly the monotone convergence theorem.
Lemma 2.29. 1. (v
N
) is monotone-down and ( u
N
) monotone-up.
2. lim sup s
n
and lim inf s
n
exist for any sequence (they might be infinite).
3. If n ≥ N, then u
N
≤ s
n
≤ v
N
.
4. lim inf s
n
≤ lim sup s
n
.
Examples 2.30. 1. If s
n
=
1
n
, then v
N
= s
N
and u
N
= 0, whence lim sup s
n
= lim inf s
n
= 0.
2. The picture shows the sequences (s
n
), ( u
N
) and ( v
N
) when s
n
= 6 + (−1)
n
1 +
5
n
We won’t compute everything precisely, but the
picture suggests (s
n
) has two “sub”-sequences:
the odd terms increase while the even terms de-
crease towards, respectively
lim inf s
n
= 5, lim sup s
n
= 7
Here is one value from each derived sequence:
u
3
= inf{s
n
: n ≥ 3} = s
3
≈ 3.333
v
13
= sup{s
n
: n ≥ 13} = s
14
≈ 7.357
0
0 10
7
5
s
n
u
N
v
N
n,N
3 13
u
3
= inf{s
n
: n ≥ 3}
34
3. Let s
n
= (−1)
n
. This time the calculation is easy: for any N,
u
N
= inf{s
n
: n ≥ N} = −1 and v
N
= sup{s
n
: n ≥ N} = 1
Therefore lim sup s
n
= 1 and lim inf s
n
= −1.
Theorem 2.31. For any sequence (s
n
),
lim sup s
n
= lim inf s
n
⇐⇒ lim s
n
exists
In such a case all three values are equal.
Note that the limits can be ±∞.
0
s
n
0
lim s
n
n
Proof. (⇒) Suppose s := lim sup s
n
= lim inf s
n
.
• If s is finite, apply the squeeze theorem to u
n
≤ s
n
≤ v
n
(both extremes converge to s).
• If s = ∞, then u
n
≤ s
n
for all n. Theorem 2.21.1 shows that lim s
n
= ∞ = s.
• If s = −∞, instead use s
n
≤ v
n
.
( ⇐) We could prove this now, but it will come almost for free a little later. . .
Cauchy Sequences
We now come to a class of sequences whose analogues will dominate your future studies.
Definition 2.32. A sequence (s
n
) is Cauchy
19
if
∀ϵ > 0, ∃N such that m, n > N =⇒
|
s
n
−s
m
|
< ϵ
A sequence is Cauchy when terms in the tails of the sequence are constrained to stay close to one
another. As we’ll see shortly, this will provide an alternative way to detect and describe convergence.
Examples 2.33. 1. Let s
n
=
1
n
. Let ϵ > 0 be given and let N =
1
ϵ
. Then
m > n > N =⇒
|
s
m
−s
n
|
=
1
n
−
1
m
<
1
n
<
1
N
= ϵ (WLOG m > n)
Thus (s
n
) is Cauchy. A similar argument works for any s
n
=
1
n
k
for positive k.
2. Suppose s
1
= 5 and s
n+1
= s
n
+
1
n(n+1)
. As before, let ϵ > 0 be given and let N =
1
ϵ
. Then,
|
s
n+1
−s
n
|
=
1
n( n + 1)
=
1
n
−
1
n + 1
=⇒
|
s
m
−s
n
|
△
≤
|
s
n+1
−s
n
|
+ ··· +
|
s
m
−s
m−1
|
=
1
n
−
1
m
<
1
n
<
1
N
= ϵ
Again we have a Cauchy sequence.
19
Augustin-Louis Cauchy (1789–1857) was a French mathematician, responsible (in part) for the ϵ-N definition of limit.
35
3. Define (s
n
)
∞
n=0
inductively:
s
0
= 1, s
n+1
=
(
s
n
+ 3
−n
if n even
s
n
−2
−n
if n odd
( s
n
) =
1, 2,
3
2
,
29
18
,
107
72
, . . .
Since
|
s
n+1
−s
n
|
≤ 2
−n
, we see that
m > n =⇒
|
s
m
−s
n
|
△
≤
|
s
n+1
−s
n
|
+ ··· +
|
s
m
−s
m−1
|
=
m−1
∑
k=n
|
s
k+1
−s
k
|
≤
m−1
∑
k=n
2
−k
=
2
−n
−2
−m
1 −2
−1
< 2
1−n
where we used the familiar geometric sum formula from calculus:
b−1
∑
k=a
r
k
=
r
a
−r
b
1−r
.
Suppose ϵ > 0 is given, and let N = 1 −log
2
ϵ = log
2
2
ϵ
. Then
m > n > N =⇒
|
s
m
−s
n
|
< 2
1−n
< 2
1−N
= ϵ
We conclude that (s
n
) is Cauchy.
The last picture illustrates the essential point of Cauchy sequences: (s
n
) appears to converge. . .
Theorem 2.34 (Cauchy Completeness). A sequence of real numbers is convergent if and only if it is
Cauchy.
Proof. (⇒) Suppose lim s
n
= s (is finite). Given ϵ > 0, we may choose N such that
m, n > N =⇒
|
s
n
−s
|
<
ϵ
2
and
|
s
m
−s
|
<
ϵ
2
=⇒
|
s
n
−s
m
|
=
|
s
n
−s + s − s
m
|
△
≤
|
s
n
−s
|
+
|
s − s
m
|
< ϵ
Otherwise said, (s
n
) is Cauchy.
( ⇐) To discuss the convergence of (s
n
) we need a potential limit. In view of Theorem 2.31, the
obvious candidates are lim sup s
n
and lim inf s
n
. We have two goals: show that (s
n
) is bounded
whence the limits superior and inferior are finite; then show that these are equal.
(Boundedness of (s
n
)) Take ϵ = 1 in Definition 2.32:
∃N such that m, n > N =⇒
|
s
n
−s
m
|
< 1
It follows that
n > N =⇒
|
s
n
−s
N+1
|
< 1 =⇒ s
N+1
−1 < s
n
< s
N+1
+ 1
whence (s
n
) is bounded. It follows that lim sup s
n
and lim inf s
n
are both finite.
36
(lim sup s
n
= lim inf s
n
) Suppose ϵ > 0 is given. Since (s
n
) is Cauchy,
∃N ∈ N such that m, n > N =⇒
|
s
n
−s
m
|
< ϵ =⇒ s
n
< s
m
+ ϵ
Take the supremum over all n > N: since v
N+1
= sup{s
n
: n ≥ N + 1}, we see that
m > N =⇒ v
N+1
≤ s
m
+ ϵ
Now take the infimum of the right hand side over all m > N to obtain
v
N+1
≤ u
N+1
+ ϵ (since u
N+1
= inf{s
m
: m ≥ N + 1})
Since (v
N+1
) is monotone-down and ( u
N+1
) monotone-up, we see that
lim sup s
n
≤ v
N+1
≤ u
N+1
+ ϵ ≤ lim inf s
n
+ ϵ =⇒ lim sup s
n
≤ lim inf s
n
+ ϵ
Since ϵ > 0 was arbitrary, we conclude that lim sup s
n
≤ lim inf s
n
. By Lemma 2.29 we
have equality.
By Theorem 2.31, we conclude that (s
n
) converges to lim sup s
n
= lim inf s
n
.
By the Theorem, Examples 2.33 all converge. All three limits can be found precisely (for instance,
see Exercise 7). With a small modification to the second example, however, we obtain something
genuinely new:
Example (2.33.2 cont). Let s
1
= 5 and, for each n, define s
n+1
:= s
n
+
sin n
n(n+1)
. Since
|
sin n
|
≤ 1, the
computation proceeds almost the same as before:
|
s
n+1
−s
n
|
=
|
sin n
|
n( n + 1)
≤
1
n( n + 1)
= ···
The new sequence is Cauchy and thus convergent, though good luck explicitly finding its limit!
The main point is easy to miss: the Cauchy condition is a powerful tool for determining whether a
sequence converges without first guessing a limit. While the proof depends on monotone convergence
(via limit superior/inferior), Cauchy completeness is more powerful in that it applies even to non-
monotone sequences.
An Alternative Definition of R Cauchy sequences suggest a definition of the real numbers which
does not rely on Dedekind cuts (Section 1.6).
Define an equivalence relation ∼ on the collection C of all Cauchy sequences of rational numbers:
20
( s
n
) ∼ (t
n
) ⇐⇒ lim(s
n
−t
n
) = 0
Now define R :=
C
∼
to be the set of equivalence classes. All this is done without reference to
Cauchy completeness, though it certainly informs our intuition that (s
n
) and (t
n
) have the same limit
(as real numbers). Significant work is still required to properly define +, ·, ≤, etc., and to verify the
axioms of a complete ordered field—we won’t pursue this.
20
We don’t need real numbers to define the limit of the rational sequence (s
n
−t
n
): ∀ϵ ∈ Q
+
is enough. . .
37
Exercises 2.10. Key concepts: Monotone sequences & Convergence, Cauchy sequences & completeness,
Limits superior/inferior
1. Use Definition 2.32 to show that the sequence with s
n
=
1
n
2
is Cauchy. Repeat for t
n
=
1
n(n−2)
.
2. Let s
1
= 1 and s
n+1
=
n
n+1
s
2
n
for n ≥ 1.
(a) Find s
2
, s
3
and s
4
.
(b) Show that lim s
n
exists and hence prove that lim s
n
= 0.
3. Let s
1
= 1 and s
n+1
=
1
3
( s
n
+ 1) for n ≥ 1.
(a) Find s
2
, s
3
and s
4
.
(b) Use induction to show that s
n
>
1
2
for all n, and conclude that (s
n
) is monotone-down.
(c) Show that lim s
n
exists and find lim s
n
.
4. (a) Let (s
n
) be a sequence such that ∀n,
|
s
n+1
−s
n
|
≤ 3
−n
. Prove that (s
n
) is Cauchy.
(b) Let s
1
= 10 and, for each n, let s
n+1
= s
n
+
cos n
3
n
. Explain why (s
n
) is convergent.
(c) Is the result in (a) true if we only assume that
|
s
n+1
−s
n
|
≤
1
n
for all n ∈ N?
5. Suppose (s
n
) is unbounded and monotone-up. Prove that lim s
n
= ∞.
(Thus lim s
n
= sup{s
n
} for any monotone-up sequence)
6. Let s
n
=
(−1)
n
n
. Find the sequences (u
N
), (v
N
) and explicitly compute lim sup s
n
and lim inf s
n
.
7. Consider the sequence in Example 2.33.3. Explain why s
2n
= s
2n−2
−
2
4
n
+
9
9
n
.
Now use the geometric sum formula to evaluate lim s
2n
.
(Since (s
n
) converges, this means the original sequence has the same limit)
8. Let S be a bounded nonempty set for which sup S /∈ S. Prove that there exists a monotone-up
sequence (s
n
) of points in S such that lim s
n
= sup S.
(Hint: for each n, use sup S −
1
n
to build s
n
)
9. Let (s
n
) be a monotone-up sequence of positive numbers and define σ
n
=
1
n
( s
1
+ s
2
+ ···+ s
n
).
Prove that (σ
n
) is monotone-up.
10. (Hard!) We prove that the sequence defined by s
n
=
1 +
1
n
n
is convergent.
(a) Show that
1 +
1
n+1
1 +
1
n
= 1 −
1
( n + 1)
2
and
1 +
1
n
1 +
1
n+1
= 1 +
1
n( n + 2)
(b) Prove Bernoulli’s inequality by induction:
For all real x > −1 and n ∈ N
0
we have ( 1 + x)
n
≥ 1 + nx.
(c) By considering
s
n+1
s
n
, use parts (a) and (b) to prove that (s
n
) is monotone-up.
(d) Similarly, show that t
n
:=
1 +
1
n
n+1
=
1 +
1
n
s
n
defines a monotone-down sequence.
(e) Prove that (s
n
) and ( t
n
) converge, and to the same limit (this is Bernoulli’s definition of e).
(f) Prove that lim(1 −
1
n
)
n
= e
−1
.
38
2.11 Subsequences
The overall behavior of a sequence is often hard to describe, but if we delete some of its terms we
might obtain a subsequence with much simpler behavior.
Definition 2.35. Let (s
n
) be a sequence. A subsequence (s
n
k
) is a subset ( s
n
k
) ⊆ (s
n
), where
n
1
< n
2
< n
3
< ···
A subsequence is simply an infinite subset whose order is inherited from the original sequence.
Example 2.36. Take s
n
= (−1)
n
(recall Example 2.10.2) and let
n
k
= 2k. Then s
n
k
= 1 for all k. Note two important facts:
• The subsequence (s
n
k
)
∞
k=0
is indexed by k, not n.
• The subsequence is constant and thus convergent.
−1
0
1
s
n
n
Our main goal in this section is to prove the famous Bolzano–Weierstraß theorem (illustrated in the
example): that every bounded sequence has a convergent subsequence.
Lemma 2.37. If lim
n→∞
s
n
= s, then every subsequence (s
n
k
) satisfies lim
k→∞
s
n
k
= s.
Proof. Suppose s is finite and suppose ϵ > 0 is given. Then ∃N such that n > N =⇒
|
s
n
−s
|
< ϵ.
Since n
k
≥ k for all k, we see that
k > N =⇒ n
k
> N =⇒
|
s
n
k
−s
|
< ϵ
The case where s = ±∞ is an exercise.
Lemma 2.38. Every sequence has a monotonic subsequence.
Proof. Given (s
n
), we call the term s
n
‘dominant’ if m > n =⇒ s
m
< s
n
. There are two cases:
1. If there are infinitely many dominant terms, then the subsequence of such is monotone-down.
2. If there are finitely many dominant terms, choose s
n
1
after all such. Since s
n
1
is not dominant,
∃n
2
> n
1
such that s
n
2
≥ s
n
1
. Induct to obtain a monotone-up subsequence.
n
s
n
s
n
k
dominant terms
n
s
n
s
n
k
Case 1: monotone-down subsequence Case 2: monotone-up subsequence
39
Theorem 2.39. Given a sequence (s
n
), there exist subsequences (s
n
k
) and ( s
n
l
) such that
lim s
n
k
= lim sup s
n
and lim s
n
l
= lim inf s
n
By the lemmas, we may moreover assume that these subsequences are monotonic.
Example 2.40. The picture shows the sequence with
n
th
term
s
n
=
(
4
n
( −1)
n
2
+1
when n is even
1 −
1
n
when n is odd
Monotonic subsequences with limits lim sup s
n
= 1
and lim inf s
n
= 0 are indicated.
−1
0
1
2
s
n
10 20
n
Proof. We prove only the lim sup claim, since the other is similar. There are three cases to consider;
visualizing the third is particularly difficult and may take several readings.
(lim sup s
n
= ∞) Since (s
n
) is unbounded above, for any
k > 0 there exist infinitely many terms s
n
> k. We may
therefore inductively choose a subsequence (s
n
k
) via
n
1
= min{n ∈ N : s
n
1
> 1}
n
k
= min{n ∈ N : n
k
> n
k−1
, and s
n
k
> k}
Choosing the minimum isn’t necessary, though it
keeps the subsequence explicit. Clearly
s
n
k
> k =⇒ lim
k→∞
s
n
k
= ∞ = lim sup s
n
0
1
2
3
4
5
s
n
1
s
n
2
s
n
3
s
n
4
s
n
5
n
s
n
Example: lim sup
√
n
2
(1 + sin n) = ∞
(lim sup s
n
= −∞) Since lim inf s
n
≤ lim sup s
n
= −∞, Lemma 2.31 says that lim s
n
= −∞, whence
( s
n
) itself is a suitable subsequence.
(lim sup s
n
= v finite) Let n
1
= 1 and define s
n
k
for k ≥ 2 inductively:
• Since (v
N
) is monotone-down and converges to v, take ϵ =
1
2k
to see that
21
∃N
k
> n
k−1
such that v ≤ v
N
k
< v +
1
2k
• Since v
N
k
= sup{s
n
: n ≥ N
k
}, Lemma 1.20 says
∃n
k
≥ N
k
such that s
n
k
> v
N
k
−
1
2k
But then
|
v − s
n
k
|
△
≤
|
v − v
N
k
|
+
|
v
N
k
−s
n
k
|
<
1
k
. The squeeze theorem says that lim
k→∞
s
n
k
= v.
21
(v
N
) being monotone-down is crucial: if N satisfies v
N
−v <
1
2k
, so does N
k
:= max(N, 1 + n
k−1
).
40
Example (2.40 cont.). The example shows why the two-step construction is necessary. It may seem
that we should simply be able to choose subsequences of (u
N
) and ( v
N
). Indeed,
( u
N
) =
−1, −1, −1, −1
| {z }
s
4
, −
1
2
, −
1
2
, −
1
2
, −
1
2
| {z }
s
8
, −
1
3
, −
1
3
, −
1
3
, −
1
3
| {z }
s
12
, . . .
contains a subsequence of (s
n
) converging to lim inf s
n
= 0. Unfortunately, (v
N
) = (2, 2, 1, 1, 1, . . .)
does not contain a subsequence of (s
n
). Taking n
k
= 2k + 1 (k ≥ 2) results in the displayed sequence:
s
n
k
= 1 −
1
2k + 1
> 1 −
1
2k
= v
N
k
−
1
2k
There are two immediate corollaries. The first (see Exercise 3) fully establishes Theorem 2.31
lim sup s
n
= lim inf s
n
⇐⇒ lim s
n
exists (could be ±∞ )
The second is the main goal of this section.
Theorem 2.41 (Bolzano–Weierstraß). Every bounded sequence has a convergent subsequence.
Proof 1. Lemma 2.38 says there exists a monotone subsequence. This is bounded and thus converges
by the monotone convergence theorem.
Proof 2. By Theorem 2.39, there exists a subsequence converging to the finite value lim sup s
n
.
For a third proof(!) we present the classic ‘shrinking-interval’ argument which has the benefit of
easily generalizing to higher dimensions.
Proof 3. Suppose (s
n
) is bounded by M. One of the intervals [ −M, 0] or [0, M] must contain infinitely
many terms of the sequence (perhaps both do!). Call this interval E
0
and choose any n
0
∈ E
0
.
Split E
0
into left- and right half-intervals, one of which must contain infinitely many terms of the
sequence for which n > n
0
;
22
call this half-interval E
1
and choose any s
n
1
∈ E
1
with n
1
> n
0
.
Repeat this ad infinitum to obtain a subsequence (s
n
k
) and a family of nested intervals
[−M, M] ⊃ E
0
⊃ E
1
⊃ E
2
⊃ ··· of width
|
E
k
|
=
M
2
k
with s
n
k
∈ E
k
It remains only to see that (s
n
k
) converges; we leave this to Exercise 5.
Example 2.42. (s
n
) = (sin n) is bounded and therefore has a
convergent subsequence! Its limit s must lie in the interval [−1, 1].
The picture shows the first 1000 terms—remember that n is mea-
sured in radians. It is not at all clear from the picture what s or
our mystery subsequence should be! There is a reason for this, as
we’ll see momentarily. . .
−1
0
1
n
s
n
22
Only finitely many terms in (s
n
) could come before s
n
0
. . .
41
Subsequential Limits, Divergence by Oscillation & Closed Sets
Recall Definition 2.19: a sequence (s
n
) diverges by oscillation if it neither converges nor diverges to
±∞. We can now give a positive statement of this idea.
( s
n
) diverges by oscillation
Thm 2.31
⇐⇒ lim inf s
n
= lim sup s
n
Thm 2.39
⇐⇒ (s
n
) has subsequences tending to different limits
The word oscillation comes from the third interpretation: if s
1
= s
2
are limits of two subsequences,
then any tail of the sequence {s
n
: n > N} contains infinitely many terms arbitrarily close to s
1
and
infinitely many (other) terms arbitrarily close to s
2
. The original sequence (s
n
) therefore oscillates
between neighborhoods of s
1
and s
2
. Of course there could be many other subsequential limits. . .
Definition 2.43. We call s ∈ R ∪ {±∞} a subsequential limit of a sequence (s
n
) if there exists a
subsequence (s
n
k
) such that lim
k→∞
s
n
k
= s.
Examples 2.44. 1. The sequence defined by s
n
=
1
n
has only one subsequential limit, namely zero.
Recall Lemma 2.37: lim s
n
= 0 implies that every subsequence also converges to 0.
2. If s
n
= (−1)
n
, then the subsequential limits are ±1.
3. The sequence s
n
= n
2
(1 + (−1)
n
) has subsequential limits 0 and ∞.
4. All positive even integers are subsequential limits of (s
n
) = (2, 4, 2, 4, 6, 2, 4, 6, 8, 2, 4, 6, 8, 10, . . .).
5. (Hard!) Recall the countability of Q from a previous class: the standard argument enumerates
the rationals by constructing a sequence
(r
n
) =
0
1
,
1
1
, −
1
1
| {z }
|
p
|
+q=2
,
1
2
, −
1
2
,
2
1
, −
2
1
| {z }
|
p
|
+q=3
,
1
3
, −
1
3
,
3
1
, −
3
1
| {z }
|
p
|
+q=4
,
1
4
, −
1
4
,
2
3
, −
2
3
,
3
2
, −
3
2
,
4
1
, −
4
1
| {z }
|
p
|
+q=5
, . . .
We claim that the set of subsequential limits of (r
n
) is in fact the set R ∪ {±∞}!
To see this, let a ∈ R be given and choose a subsequence ( r
n
k
) inductively:
• By the density of Q in R (Corollary 1.23), the set S
n
= Q ∩(a −
1
n
, a +
1
n
) contains infinitely
many rational numbers and thus infinitely many terms of the sequence (r
n
).
• Choose any r
n
1
∈ S
1
and, for each k ≥ 2, choose any
r
n
k
∈ S
k
such that n
k
> n
k−1
• Since
|
r
n
k
− a
|
<
1
n
k
≤
1
k
, we conclude that lim
k→∞
r
n
k
= a.
An argument for the subsequential limits ±∞ is in the Exercises. Somewhat amazingly, the
specific sequence (r
n
) is irrelevant: the conclusion is the same for any sequence enumerating Q!
6. (Even harder—Example 2.42, cont.) We won’t prove it, but the set of subsequential limits of
( s
n
) = (sin n) is the entire interval [−1, 1]! Otherwise said, for any s ∈ [−1, 1] there exists a
subsequence ( sin n
k
) such that lim
k→∞
sin n
k
= s.
42
Theorem 2.45. Let (s
n
) be a sequence in R and let S be its set of subsequential limits. Then
1. S is non-empty (as a subset of R ∪ {±∞}).
2. sup S = lim sup s
n
and inf S = lim inf s
n
.
3. lim s
n
exists iff S has only one element: namely lim s
n
.
Proof. 1. By Theorem 2.39, lim sup s
n
∈ S.
2. By part 1, lim sup s
n
≤ sup S. For any convergent subsequence (s
n
k
) we have n
k
≥ k, whence
∀N, {s
n
k
: k ≥ N} ⊆ {s
n
: n ≥ N} =⇒ lim s
n
k
= lim sup s
n
k
≤ lim sup s
n
Since this holds for every convergent subsequence, we have sup S ≤ lim sup s
n
and therefore
equality. The result for inf S is similar.
3. Applying Theorem 2.31, we see that lim s
n
exists if and only if
lim sup s
n
= lim inf s
n
⇐⇒ sup S = inf S ⇐⇒ S has only one element
Closed Sets You should be comfortable with the notion of a closed interval (e.g. [0, 1]) from elemen-
tary calculus. Sequences allow us to make a formal definition.
Definition 2.46. Let A ⊆ R.
• We say that s ∈ R is a limit point of A if there exists a sequence (s
n
) ⊆ A converging to s.
• The closure A is the set of limit points of A. Plainly A ⊆ A for any set.
• A is closed if it equals its closure: A = A.
Examples 2.47. 1. The interval [0, 1] is closed. If (s
n
) ⊆ [0, 1] has lim s
n
= s, then
0 ≤ s
n
≤ 1
Thm 2.11
=⇒ s ∈ [0, 1]
More generally, every ‘closed interval’ [a, b] is closed, as are finite unions of closed intervals, for
instance [1, 5] ∪ [7, 11].
2. The ‘half-open’ interval (0, 1] is not closed: its closure is (0, 1] = [0, 1]. In particular, the se-
quence s
n
=
1
n
lies in ( 0, 1], but lim s
n
= 0 ∈ (0, 1].
3. Example 2.44.5 shows that the closure of the rational numbers is the reals: Q = R.
Theorem 2.48. If (s
n
) is a sequence, then its set of (finite) subsequential limits is closed.
We omit the proof since it involve unpleasantly many subscripts (subsequences of subsequences. . . ).
43
Exercises 2.11. Key concepts: Subsequences of a convergent sequence all have the same limit,
Existence of (monotone) subsequences tending to lim sup s
n
/ lim inf s
n
, Subsequential Limits,
Bolzano–Weierstraß: boundedness =⇒ ∃ convergent subsequence
1. Consider the sequences with the following n
th
terms:
a
n
= (−1)
n
b
n
=
1
n
c
n
= n
2
d
n
=
6n + 4
7n −3
For each sequence: state whether it converges, diverges to ±∞ , or diverges by oscillation; give
an example of a monotone subsequence; state the set of subsequential limits; state the limits
superior and inferior.
2. Prove the case of Lemma 2.37 when lim s
n
= ∞
3. Suppose that lim s
n
= s (could be ±∞). Use Theorem 2.39 and Lemma 2.37 to prove that
lim sup s
n
= s = lim inf s
n
.
(This completes the proof of Theorem 2.31)
4. Suppose that L = lim s
2
n
exists and is finite.
(a) Given an example of such a sequence where (s
n
) is divergent.
(b) Prove that (s
n
) contains a convergent subsequence. What are the possible limits of this
subsequence? Why?
(Hint: use Bolzano–Weierstraß)
5. Complete the third proof of Bolzano–Weierstraß (Theorem 2.41) by proving that the constructed
subsequence (s
n
k
) is Cauchy.
6. (a) Show that the closed interval [a, b] is a closed set in the sense of Definition 2.46.
(b) Is there a sequence (s
n
) such that (0, 1) is its set of subsequential limits?
7. By considering Example 2.47.2, or otherwise, show that an infinite union of closed intervals
need not be closed.
8. Let (r
n
) be any sequence enumerating of the set Q of rational numbers. Show that there exists
a subsequence (r
n
k
) such that lim
k→∞
r
n
k
= +∞.
(Hint: modify the argument in Example 2.44.5)
9. (Hard) Let (s
n
) be the sequence of numbers defined
in the figure, listed in the indicated order.
(a) Find the set S of subsequential limits of (s
n
).
(b) Determine lim sup s
n
and lim inf s
n
.
1
1
2
1
3
1
4
1
5
···
1
1
2
1
3
1
4
1
5
···
1
1
2
1
3
1
4
1
5
···
1
1
2
1
3
1
4
1
5
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
2.12 Lim sup and Lim inf
In this short section we collect a couple of useful results, mostly for later use. First we observe that
the limit laws do not work as tightly for limits superior and inferior.
Theorem 2.49. Let (s
n
), (t
n
) be bounded sequences. Then:
1. lim sup(s
n
+ t
n
) ≤ lim sup s
n
+ lim sup t
n
2. If, in addition, (s
n
) is convergent to s, then we have equality
lim sup(s
n
+ t
n
) = s + lim sup t
n
Natural modifications can be made for infima and products of sequences (see Exercise 3).
Example 2.50. To convince yourself that equality is unlikely, consider s
n
= (−1)
n
= −t
n
. Plainly
lim sup(s
n
+ t
n
) = 0 < 2 = lim sup s
n
+ lim sup t
n
Proof. 1. For each N, the set {s
n
+ t
n
: n ≥ N} is bounded above by
sup{s
n
: n ≥ N}+ sup{t
n
: n ≥ N}
from which
sup{s
n
+ t
n
: n ≥ N} ≤ sup{s
n
: n ≥ N}+ sup{t
n
: n ≥ N}
Take limits as N → ∞ for the first result.
2. By part 1, we know that
lim sup(s
n
+ t
n
) ≤ s + lim sup t
n
For the other direction, rearrange and apply part 1 again:
lim sup t
n
= lim sup
( s
n
+ t
n
) − s
n
≤ lim sup(s
n
+ t
n
) + lim sup(−s
n
)
= lim sup(s
n
+ t
n
) − s
The next result will be critical when we study infinite series, particularly the ratio and root tests.
Theorem 2.51. Let (s
n
) be a non-zero sequence. Then
lim inf
s
n+1
s
n
≤ lim inf
|
s
n
|
1/n
≤ lim sup
|
s
n
|
1/n
≤ lim sup
s
n+1
s
n
In particular, lim
s
n+1
s
n
= L =⇒ lim
|
s
n
|
1/n
= L. ( †)
45
Examples 2.52. 1. Here is a quick proof that lim n
1/n
= 1 (recall Theorem 2.17). Let s
n
= n, then
lim
s
n+1
s
n
= lim
n + 1
n
= 1 =⇒ lim n
1/n
= lim
|
s
n
|
1/n
= 1
2. Apply the corollary to s
n
= n! to see that
lim(n!)
1/n
= lim
s
n+1
s
n
= lim(n + 1) = ∞
Proof. We prove the third inequality. Assume lim sup
s
n+1
s
n
= L = ∞ (otherwise the inequality is
trivial). Suppose ϵ > 0 is given, and denote a = L + ϵ. Then
L = lim
N→∞
sup
s
n+1
s
n
: n ≥ N
< a =⇒ ∃N such that sup
s
n+1
s
n
: n ≥ N
< a
Now let b = a
−N
|
s
N
|
. For any n ≥ N, we therefore have
s
n+1
s
n
< a, whence
n > N =⇒
|
s
n
|
< a
n−N
|
s
N
|
=⇒
|
s
n
|
1/n
< a
a
−N
|
s
N
|
1/n
= ab
1/n
=⇒ lim sup
|
s
n
|
1/n
≤ a lim b
1/n
= a = L + ϵ
Since ϵ > 0 was arbitrary, we conclude the third inequality: lim sup
|
s
n
|
1/n
≤ L.
The second inequality is trivial and the first is similar to the third.
Exercises 2.12. Key concepts: “Limit laws” for lim sup and lim inf, lim
s
n+1
s
n
= lim
|
s
n
|
1/n
1. Compute lim
1
n
( n!)
1/n
(Hint: let s
n
=
n!
n
n
in Theorem 2.51 and recall that lim
1 +
1
n
n
= e)
2. Evaluate lim
(2n)!
(n!)
2
1/n
3. Let (s
n
) and ( t
n
) be non-negative, bounded sequences.
(a) Prove that lim sup(s
n
t
n
) ≤
(
lim sup s
n
) (
lim sup t
n
)
(b) Give an example which shows that we do not expect equality in part (a).
(c) If, in addition, lim s
n
= s, prove that lim sup(s
n
t
n
) = s lim sup t
n
.
4. Consider the sequence with s
2m
= s
2m+1
= 2
−m
:
( s
n
)
∞
n=0
=
1, 1,
1
2
,
1
2
,
1
4
,
1
4
,
1
8
,
1
8
, . . .
Compute
|
s
n
|
1/n
and
s
n+1
s
n
when n is even and then when it is odd. Thus find all expressions
in Theorem 2.51 and conclude that the converse of (†) is false.
46