7 Limits of Sequences
Sequences are the fundamental tool in our approach to analysis.
Definition 7.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.
This is strictly the definition of an infinite sequence; finite sequences don’t appear in this course. Other
letters may be used (a
n
, b
n
, etc.), though s
n
is most common in the abstract. It is also common to have
sequences which start with a different initial term (n = 0 is particularly common). If you need to be
explicit, describe the range of indices with sub/superscripts, e.g. (s
n
)
∞
n=0
.
Examples 7.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 t
1
= 1 and t
n+1
= 3t
n
− 1 together define
the sequence
( 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 In analysis we are typically interested in what happens to the terms of a sequence (s
n
) when
n gets large (as such, it is common to be non-explicit as to the initial term). In elementary calculus,
you should have become used to writing expressions such as
11
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, we have
( 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. In the next section we will do so
by developing the formal definition of limit. Before seeing this, we quickly refresh a few simple
examples from elementary calculus. At the moment, all these rely on your intuition and experience.
This is a good thing to practice: in analysis it is often essential to have a good idea of the correct
answer before you try to prove it!
11
If there are multiple letters in your expression, then for clarity it can be helpful to write lim
n→∞
with a subscript.
19
Examples 7.3. 1. lim
1
n
= 0. Our instinct is 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). Indeed
( s
n
)
∞
n=0
= (1, −1, 1, −1, 1, −1, . . .)
isn’t getting closer to any real number.
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. Indeed it is not hard to spot the pattern s
n
= 6 −
4
2
n
which
is easily verified by induction: for the induction step, simply observe that
1
2
s
n
+ 3 =
1
2
6 −
4
2
n
+ 3 = 6 −
4
2
n+1
Exercises 7. 1. Decide whether each sequence converges; if it does, give 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 7.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?
20
8 The Formal Definition of Limit
Definition 8.1. A sequence (s
n
) converges to a limit s ∈ R, if
12
∀ϵ > 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.
This isn’t as hard as it looks! The best way to understand it is to work a lot of examples. . .
Example 8.2. We show that the sequence with n
th
term s
n
= 2 −
1
√
n
converges to s = 2.
If we plot the sequence like a function, we see how ϵ controls the distance from s
n
is to the limit s; the
definition requires us to show that no matter how small we make ϵ, there is some tail of the sequence
(all s
n
with n > N) whose terms are less than a distance ϵ from the limit.
0
1
s
n
0 20 40 60 80 100
s + ϵ
s − ϵ
N
s = 2
n
. . . guarantees that s
n
lives here
n being larger than this. . .
To verify a ‘for all, there exists’ statement requires an argument with a specific structure:
• Suppose ϵ > 0 has been provided and describe N, dependent on ϵ (ϵ 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.
We want
|
s
n
−s
|
=
2 −
1
√
n
−2
=
1
√
n
< ϵ (equivalently n >
1
ϵ
2
) whenever n > N.
Choosing N =
1
ϵ
2
should be enough to complete the proof!
Warning! We do not yet have a proof: “N =
1
ϵ
2
” is not the correct conclusion! We finish by rear-
ranging our scratch work to make it clear that the definition is satisfied.
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 s
n
→ 2, as required.
12
N can be quantified as either a real or a natural number, the definitions being equivalent by the Archimedean property:
if N ∈ R satisfies the definition, then ∃
e
N ∈ N such that
e
N ≥ N; but then n >
e
N =⇒ n > N . . . It tends to be easier to use
R for convergence and N when directly proving divergence (see Definition 8.5).
21
The last three lines are all we need—think of them as the concert performance after much rehearsal!
With practice, you might be able to do simple ϵ–N arguments like these without scratch work, though
even experts usually require some.
Before seeing more examples, we prove a hopefully intuitive result.
Lemma 8.3 (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 defini-
tion we obtain a tail of the sequence (all terms s
n
coming after some N) 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 8.1 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
}. Then,
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
|
Contradiction.
Examples 8.4. We give several more examples of using the limit definition. Remember that only the
formal arguments needs to be presented; some scratch work is included to show the thought process.
1. For any k ∈ R
+
, we prove that lim
1
n
k
= 0.
Scratch work. Given ϵ > 0, we want to choose N such that
n > N =⇒
1
n
k
< ϵ
This amounts to having n >
1
ϵ
1/k
, so it is enough to choose N to be the right hand side.
Formal argument. Let ϵ > 0 be given, and let N =
1
ϵ
1/k
. Then
n > N =⇒
1
n
k
−0
=
1
n
k
<
1
N
k
= ϵ
We conclude that
1
n
k
→ 0, as required.
22
2. We prove that lim
√
n + 4 −
√
n
= 0.
Scratch work. Everything follows from a (hopefully) familiar algebraic trick for manipulating
surd expressions:
√
n + 4 −
√
n =
4
√
n + 4 +
√
n
<
4
2
√
n
=
2
√
n
Formal argument. Let ϵ > 0 be 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, as required.
3. 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 for us to have
n −7 >
22
ϵ
or equivalently n > 7 +
22
ϵ
Formal argument 1. Let ϵ > 0 be 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 (cont). An alternative approach is available if we play with (∗) a little. By insisting
that n ≥ 14, we may simplify the denominator
n −7 ≥
1
2
n =⇒
22
n −7
≤
22
1
2
n
=
44
n
Formal argument 2. Let ϵ > 0 be 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.
23
The plot illustrates the two choices of N as functions of ϵ. Observe how the second is always
larger than the first: if N = N
1
( ϵ) works in a proof, then any larger choice N
2
( ϵ) will also,
n > N
2
≥ N
1
=⇒ n > N =⇒
|
s
n
−s
|
< ϵ
Use this to your advantage to produce simpler arguments.
0
100
N
0 1 2 3 4 5
N
1
= 7 +
22
ϵ
N
2
= max
14,
44
ϵ
ϵ
4. 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
n > N =⇒
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 (as in the first method previously) is crazy! Instead we simplify the
fraction by observing that since n ≥ 1, we have
−2n
2
−9n −5
3( 3n
4
+ n
2
+ 4)
≤
16n
2
3( 3n
4
+ n
2
+ 4)
(1 ≤ n ≤ n
2
and the △-inequality)
<
16n
2
9n
4
<
2
n
2
(n
2
+ 4 > 0 =⇒ 3n
4
+ n
2
+ 4 > 3n
4
)
The final simplification is merely for additional tidying.
Formal argument. Let ϵ > 0 be given, and let N =
q
2
ϵ
. Then
n > N =⇒
s
n
−
2
3
=
−2n
2
−9n −5
3( 3n
4
+ n
2
+ 4)
<
16n
2
9n
4
(since n ≥ 1)
<
2
n
2
<
2
N
2
= ϵ
Other choices of N are feasible (see e.g. Exercise 5); everything depends on how you want to
simplify things in your scratch work.
24
Divergent sequences
By negating Definition 8.1, we obtain a new definition.
Definition 8.5. 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 8.6. 1. We prove that the sequence with s
n
=
7
n
does not converge to s = 2.
Visualization. We intuitively know that s
n
→ 0. If ϵ is anything smaller than 2, then the terms
s
n
will eventually be further than this from s = 2.
0
4
6
s
n
0 5 10 15
s = 2
s + ϵ
s − ϵ
n
Every tail of the sequence contains
elements s
n
that do not lie here
Direct argument. Let ϵ = 1. Since we are only concerned with large values of n, we see that
|
s
n
−s
|
=
7
n
−2
= 2 −
7
n
≥ ϵ = 1 ⇐⇒
7
n
≤ 1 ⇐⇒ n ≥ 7
Given N ∈ N, let
13
n = max{7, N + 1}. But then
|
s
n
−s
|
=
7
n
−2
≥ ϵ, from which we
conclude that s
n
↛ 2.
Contradiction argument. For an alternative approach, we suppose s
n
→ 2 and let ϵ = 1 in
Definition 8.1. Then ∃N such that
n > N =⇒
7
n
−2
< 1 =⇒ 1 <
7
n
< 3 =⇒
7
3
< n < 7
Regardless of the value of N, this cannot hold for all n > N: in particular n := max{7, N + 1}.
Contradiction.
The two arguments are very similar, though consider that a significant advantage of the contra-
diction approach is that you only have to remember one definition!
13
This is why we prefer to let N be a natural number when proving divergence. If N ∈ R, then we’d have to use the
ceiling function (n = max{14, ⌈N⌉ + 1}), or resort to the Archimedean property on which it depends (∃n > max{14, N}).
Either way is ugly and potentially confusing, so better avoided.
25
2. We prove that the sequence defined by s
n
= (−1)
n
is divergent.
Suppose, for contradiction, that s
n
→ s. The picture shows the case s ≥ 0 and strongly suggests
that ϵ = 1 will lead to a contradiction (why?).
−1
1
2
s
n
10 20
s + ϵ
s − ϵ
N
s
n
Regardless of N, every tail
of the sequence after here. . .
. . . contains some elements
s
n
that do not lie here
Let ϵ = 1 in the definition of limit. Then ∃N ∈ N such that
n > N =⇒
|
( −1)
n
−s
|
< 1
One each of the values {n
e
, n
o
} = {N, N + 1} is even and the other odd. There are two cases:
• If s ≥ 0 then
|
( −1)
n
o
−s
|
=
|
−1 − s
|
= s + 1 ≥ 1 = ϵ .
• If s < 0 then
|
( −1)
n
e
−s
|
=
|
1 −s
|
= 1 − s ≥ 1 = ϵ.
Either way we have a contradiction. We conclude that (s
n
) is divergent.
3. We show that the sequence defined by s
n
= ln n is divergent.
14
Our intuition from calculus is that logarithms increase unboundedly. For any s ∈ R, letting
ϵ = 1 should be enough, for eventually ln n ≥ s + 1. This time we prove directly using the
definition of divergence (8.5).
Suppose s ∈ R, let ϵ = 1, and suppose that N ∈ N is given. Define n = max{N + 1, e
s+1
} and
observe that. Then
n > N and ln n ≥ ln(e
s+1
) = s + 1 (ln is increasing, and so respects inequalities!)
In particular,
|
s
n
−s
|
= ln n −s ≥ 1 = ϵ
We conclude that (s
n
) is divergent.
14
In the next section we’ll have a definition of what it means for a sequence to diverge to ∞: this is what’s happening for
s
n
= ln n, but it’s not (yet) what we’re trying to demonstrate.
26
A Little Abstraction
Working explicitly with the limit definition is tedious. In the next section we’ll develop and summa-
rize the limit laws so we can combine limits of sequences without providing new ϵ-N proofs. To start
working towards this, here are three general results.
Lemma 8.7. If lim s
n
= s, then lim s
2
n
= s
2
.
The challenge is that we want to bound
s
2
n
−s
2
=
|
s
n
−s
||
s
n
+ s
|
, which means we need some
control over
|
s
n
+ s
|
. One way uses the triangle-inequality,
|
s
n
+ s
|
=
|
s
n
−s + 2s
|
≤
|
s
n
−s
|
+ 2
|
s
|
Assuming
|
s
n
−s
|
≤ 1 gives us a fixed bound
|
s + s
n
|
≤ 1 + 2
|
s
|
. We may now begin a proof.
Proof. Suppose s
n
→ s. Let ϵ > 0 be given, and let δ = min{1,
ϵ
1+2
|
s
|
}. Since s
n
→ s, ∃N such that
n > N =⇒
|
s
n
−s
|
< δ
But then
n > N =⇒
s
2
n
−s
2
=
|
s
n
−s
||
s
n
+ s
|
≤
|
s
n
−s
|
(
|
s
n
−s
|
+ 2
|
s
|
)
(△-inequality)
< δ(1 + 2
|
s
|
) (since
|
s
n
−s
|
< δ ≤ 1)
≤ ϵ
Theorem 8.8. Suppose lim s
n
= s.
1. If s
n
≥ m for all except finitely many n, then s ≥ m.
2. If s
n
≤ M for all except finitely many n, then s ≤ M.
Proof. We prove part 1 by contradiction—part 2 is similar.
Suppose s
n
→ 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 (add s −m to both sides)
By assumption, s
n
< m holds for at most finitely many n. Contradiction.
The expression for all but finitely many n can be added to many abstract limit theorems; other com-
mon variants are for all large n, and for some tail of the sequence. To avoid cumbersome language, the
expression is often omitted. Remember that convergence/divergence is concerned with what hap-
pens when n is large: we can change or delete the first million terms of (s
n
) without altering it’s
convergence status!
27
Theorem 8.9 (Squeeze Theorem). Suppose three sequences satisfy a
n
≤ s
n
≤ b
n
(for all large n) and
that (a
n
) and (b
n
) both converge to s. Then lim s
n
= s.
Proof. By subtracting s from our assumed inequality, we see that
a
n
−s ≤ s
n
−s ≤ b
n
−s =⇒
|
s
n
−s
|
≤ max{
|
a
n
−s
|
,
|
b
n
−s
|
}
It remains to bound the right hand side by ϵ. Let ϵ > 0 be given, then there exist N
a
, N
b
such that
n > N
a
=⇒
|
a
n
−s
|
< ϵ and n > N
b
=⇒
|
b
n
−s
|
< ϵ
Finally let N = max{N
a
, N
b
} to see that
n > N =⇒
|
s
n
−s
|
≤ max{
|
a
n
−s
|
,
|
b
n
−s
|
} < ϵ
Example 8.10. If s
n
=
1+sin n
n
, then 0 ≤ s
n
≤
2
n
. The squeeze theorem quickly forces lim s
n
= 0.
Exercises 8. 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. Let (t
n
) be a bounded sequence (there exists M such that
|
t
n
|
≤ M for all n), and let (s
n
) be a
sequence such that lim s
n
= 0. Prove that lim(s
n
t
n
) = 0.
(Hint: given ϵ, note that
ϵ
|
M
|
is also a small number. . . )
3. Prove the following
(a) lim[
√
n
2
+ 1 − n] = 0 (b) lim[
√
n
2
+ n −n] =
1
2
(c) lim[
√
4n
2
+ n −2n] =
1
4
4. Let (s
n
) be a convergent sequence, and suppose lim s
n
> a. Prove that there exists N such that
n > N =⇒ s
n
> a.
5. (a) Show that n ≥ 2 =⇒ 2n
2
+ 9n + 5 ≤ 9n
2
.
(b) (Recall Example 8.4.4) Provide another argument that lim
2n
4
−3n+1
3n
4
+n
2
+4
=
2
3
by choosing N =
max{2,
1
√
ϵ
}.
6. (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.
7. Prove that the sequence defined by t
n
= n
2
diverges.
8. Provide a contradiction argument to justify Example 8.6.3: (ln n) diverges.
9. (Recall Theorem 8.8) Suppose lim s
n
= s where every s
n
> m. Can we conclude that s > m?
Explain your answer.
10. (a) If
|
s
n
−s
|
< 1, explain why
s
2
n
+ ss
n
+ s
2
< 1 + 3
|
s
|
+ 3
|
s
|
2
(b) Suppose s
n
→ s. Prove that s
3
n
→ s
3
.
28
9 Limit Theorems for Sequences
We’d like to develop some rules for working with limits so that we don’t have to resort to an ϵ–N
proof every time. The rough idea is that limits respect the basic rules of algebra. For instance. . .
Example 9.1. If lim s
n
= s, it seems natural that a new sequence (5s
n
) obtained by multiplying the
original terms by 5 should have limit lim 5s
n
= 5s. Consider what we have to prove to confirm this:
∀ϵ > 0, ∃N such that n > N =⇒
|
5s
n
−5s
|
< ϵ
This last amounts to observing that
|
s
n
−s
|
<
ϵ
5
. The challenge here is to see that we’re essentially
done: this is just the statement lim s
n
= s in disguise! Here is a more formal argument.
Let ϵ > 0 be given. Since lim s
n
= s, we know that
∃N such that n > N =⇒
|
s
n
−s
|
<
ϵ
5
=⇒
|
5s
n
−5s
|
< ϵ
The trick in the example will be used repeatedly in the proofs that follow. What’s critical is that
you read the limit definition correctly: given any small number (ϵ,
ϵ
5
, etc.) there is some tail of the
sequence which remains closer to the limit than this.
Theorem 9.2 (Limit laws). Limit calculations respect algebraic operations: ±, ×, ÷ and 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; as a special case, 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)
Our first example was the special case of part 2 with k = 5. Note also how parts 2 and 4 extend
Lemma 8.7: by induction we now have s
q
n
→ s
q
for any q ∈ Q.
Proving the limit laws takes a little work, including a small lemma. To advertise their benefit, we
repeated apply them to a limit calculation as you might have seen it in elementary calculus.
Examples 9.3. 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
=
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 lim
1
n
= 0 (Example 8.4.1))
This calculation involves some generally accepted sleight of hand; formally we’re working from
the bottom up since lim
3n
2
+2
√
n−1
5n
2
−2
shouldn’t really be written until you know it exists!
29
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 we’ll need to wait until the next section to see why.
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. The strategy for the first is simple: control both
sequences so that both
|
s
n
−s
|
,
|
t
n
−t
|
<
ϵ
2
, then add. The only challenge is writing it formally.
Proof of Theorem 9.2, part 1. Let ϵ > 0 be given. Since s
n
→ s and t
n
→ t, we see that ∃N
1
, N
2
such that
∃N
1
such that n > N
1
=⇒
|
s
n
−s
|
<
ϵ
2
and,
∃N
2
such that 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.
The multiplicative limit law requires a preparatory result.
Lemma 9.4. (s
n
) convergent =⇒ (s
n
) bounded (∃M such that ∀n,
|
s
n
|
≤ M).
The converse to this statement is false: why?
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.
Proof. Suppose lim s
n
= s and 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
30
The approach to part 2 is similar to part 1, we just need to be a bit cleverer to break up
|
s
n
t
n
−st
|
.
Proof of Theorem 9.2, part 2. Exercise 8.2 deals with (and extends) the case when s = 0. Instead sup-
pose s = 0, and let ϵ > 0 be given. Since s
n
→ s and t
n
→ t,
( t
n
) is bounded (Lemma) : ∃M such that ∀n,
|
t
n
|
≤ M
∃N
1
, N
2
such that n > N
1
=⇒
|
s
n
−s
|
<
ϵ
2M
and n > N
2
=⇒
|
t
n
−t
|
<
ϵ
2
|
s
|
Again 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
|
= ϵ
The proofs of parts 3 and 4 are in Exercise 6.
More basic examples With a few simple general examples, the limit laws allow us to rapidly com-
pute the limits of a great variety of sequences.
Theorem 9.5. 1. If k > 0 then lim
1
n
k
= 0
2. If
|
a
|
< 1 then lim a
n
= 0
3. If a > 0 then lim a
1/n
= 1
4. lim n
1/n
= 1
Examples 9.6. 1. lim( 3n)
2/n
= (lim 3
1/n
)
2
(lim n
1/n
)
2
= 1.
2. 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
Note that lim
sin n
n
= 0 follows from the squeeze theorem:
sin n
n
≤
1
n
→ 0.
Proof. 1. This is Example 8.4.1.
2. The a = 0 case is trivial. Otherwise, given ϵ > 0, let N = log
|
a
|
ϵ and observe that
n > N =⇒
|
a
n
|
<
a
N
=
|
a
|
N
= ϵ
3. Suppose a ≥ 1, and let s
n
:= a
1/n
−1. Since s
n
> 0, the binomial theorem
15
shows that
a = (1 + s
n
)
n
≥ 1 + ns
n
=⇒ 0 < s
n
≤
a −1
n
The squeeze theorem (8.9) shows that s
n
→ 0, whence lim a
1/n
= 1.
We leave the a < 1 case and part 4 to Exercise 7.
15
(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
.
31
Divergence to ±∞ and the ‘divergence laws’
We now consider unbounded sequences and provide a positive definition of a type of divergence.
Definition 9.7. We say that (s
n
) diverges to ∞ if,
∀M > 0, ∃N such that n > N =⇒ s
n
> M
We write s
n
→ ∞ or lim s
n
= ∞. The definition for s
n
→ −∞ is similar.
If (s
n
) neither converges nor diverges to ±∞, we say that it diverges by oscillation.
16
Consider how M is trying to describe “closeness” to infinity similarly to how ϵ measures closeness
to s in the original definition of limit (8.1).
Examples 9.8. As with convergence proofs, it is a good idea to try some scratch work first!
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. Prove that s
n
= n
5
−n
4
−2n + 1 → ∞.
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. Prove that the sequence defined by 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,
17
and define N = max{2,
3
√
2M}. Then
n > N =⇒ n > 2 =⇒ s
n
< −
1
2
n
3
< −
1
2
N
3
≤ −M
16
In such cases lim s
n
is meaningless; you likely wrote lim s
n
= DNE (“does not exist”) in elementary calculus.
17
The notion that s
n
→ −∞ can be phrased in multiple ways: some prefer
∀m < 0, ∃N such that n > N =⇒ s
n
< m (in our argument M = −m)
32
Several of the limit laws can be adapted to sequences which diverge to ±∞.
Theorem 9.9. 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 s
n
→ −∞ should be clear.
Proof. We prove two of the results: 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 find the limit of any rational sequence:
p
n
q
n
where (p
n
), (q
n
) are
polynomials in n.
Example 9.10. By applying Theorem 9.9 (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
= ∞
Indeed, you should be able to confirm the familiar result from elementary calculus:
Corollary 9.11. 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
)
33
Exercises 9. 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. Consider s
n
= (100n)
100
n
. Describe s
1
(1 followed by how many zeros?). Repeat for s
10
. Now
compute the limit lim s
n
.
3. 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) .
4. Prove the following:
(a) lim(n
3
−98n) = ∞ (b) lim
√
n − n +
4
n
= −∞
5. 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.
6. We prove parts 3 and 4 of the limit laws (Theorem 9.2). 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 t
n
→ t, ∃N
2
such that n > N
2
=⇒
|
t
n
−t
|
<
1
2
|
t
|
2
ϵ. Combine
N
1
and N
2
to provide a proof 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 help 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
7. We finish the proof of Theorem 9.5.
(a) Suppose 0 < a < 1. Prove that lim a
1/n
= 1.
(Hint: consider b =
1
a
. . . )
(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.
8. Prove the remaining parts of Theorem 9.9.
9. 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
|
)
(c) Let p > 0 and a ∈ R be given. How does lim
n→∞
a
n
n
p
depend on the value of a?
34
10 Monotone and Cauchy Sequences
The definition of limit (Definition 8.1) exhibits 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.
18
In this section we consider two important
classes of sequence for which this can be done.
Definition 10.1. A sequence (s
n
) is:
• Monotone-up
19
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 10.2. 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 10.3 (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 ∞ (see Exercise 5). The statement is lim s
n
= inf{s
n
} for monotone-down sequences.
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 4.8, there exists some s
N
> s − ϵ. Since (s
n
) is monotone-up, we have
n > N =⇒ s
n
≥ s
N
> s − ϵ =⇒ 0 ≤ s − s
n
< ϵ =⇒
|
s − s
n
|
< ϵ
The monotone-down case is similar.
18
This gets at the typical role of sequences in analysis: to demonstrate the existence of and define a new object (the limit)
and, more broadly, to transfer useful properties from the sequence to the limit. For instance, if ( f
n
) is a sequence of differ-
entiable 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 will dominate Math 140B.
19
Some authors describe such as sequence as either non-decreasing or increasing. We prefer monotone-up/down since this
directly describes the direction of any potential movement in the sequence and prevents confusion over whether the in-
equality is strict. A sequence with s
n+1
> s
n
may be described as strictly increasing or strictly monotone-up.
35
Examples 10.4. 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, . . .
The sequence certainly appears to be monotone-up and converging to 2. We prove this:
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 9.3.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
20
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 9.3.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 0.d
1
d
2
d
3
. . . may be viewed as the limit of a monotone-up sequence of rational numbers:
0.d
1
d
2
d
3
. . . = lim
n→∞
n
∑
k=0
d
k
10
k
This is bounded above by 1 and so converges. Compare this with Example 4.4.
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
20
In case you’ve seen it before, this is the famous AM–GM inequality
x+y
2
≥
√
xy with x = s
n
and y =
2
s
n
.
36
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 remains useful to be able to describe its long-term behavior.
Definition 10.5. 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/N
The original sequence (s
n
) is almost wedged between
21
( v
n
) and (u
n
) in a situation reminiscent of
the squeeze theorem (except 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 10.6. 1. (v
N
) is monotone-down, (u
N
) is monotone-up, and u
N
≤ s
N+1
≤ v
N
.
2. lim sup s
n
and lim inf s
n
exist for any sequence (they might be infinite).
3. lim inf s
n
≤ lim sup s
n
.
Examples 10.7. 1. The picture shows 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
5
= 4
v
7
= sup{s
n
: n > 7} = s
8
= 7.625
0
0 10
7
5
s
n
u
N
v
N
n/N
3 7
u
3
= inf{s
n
: n > 3}
2. If s
n
=
1
n
, then v
N
= s
N+1
and u
N
= 0 for all N, whence lim sup s
n
= lim inf s
n
= 0.
21
A minor redefinition would remove the ‘almost,’ but at the cost of making some subsequent arguments a little messier.
It is still reasonable to think of (u
N
) and (v
N
) as providing a long-term envelope for the original sequence.
37
3. Let s
n
= (−1)
n
. This time the calculation is easy:
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.
Lemma 10.8. For any sequence (s
n
),
lim inf s
n
= lim sup s
n
=⇒ lim s
n
exists
(the limit can be infinite!).
In such a case all three values are equal.
0
s
n
0
lim s
n
n
In fact the converse to this is also true: we could prove it now, but it will come for free a little later. . .
Proof. (s finite) Since u
n−1
≤ s
n
≤ v
n−1
for all n, the squeeze theorem tells us that lim s
n
= s.
(s = ∞) Since u
n−1
≤ s
n
for all n and lim u
n−1
= ∞, it follows (Theorem 9.9.1) that lim s
n
= ∞.
(s = −∞) This time s
n
≤ v
n−1
→ −∞ =⇒ lim s
n
= −∞.
Cauchy Sequences
We now come to a class of sequences whose analogues will dominate your study of analysis.
Definition 10.9. A sequence (s
n
) is Cauchy
22
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 10.10. 1. Let s
n
=
1
n
. Let ϵ > 0 be given and let N =
1
ϵ
. Then
23
m > n > N =⇒
|
s
m
−s
n
|
=
1
n
−
1
m
<
1
n
<
1
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.
22
Augustin-Louis Cauchy (1789–1857) was a French mathematician, responsible (in part) for the ϵ-N definition of limit.
38
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
0
1
2
0 2 4 6 8 10 12 14
n
s
n
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 picture in the last example illustrates the essential point regarding Cauchy sequences: (s
n
) ap-
pears very much to converge. . .
Theorem 10.11 (Cauchy Completeness). A sequence of real numbers is convergent if and only if it
is Cauchy.
Proof. (⇒) Suppose lim s
n
= s (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
|
< ϵ
whence (s
n
) is Cauchy.
( ⇐) To discuss the convergence of (s
n
) we first need a potential limit! In view of Lemma 10.8, 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 10.9:
∃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 finite.
23
Since m, n are arbitrary, WLOG we may assume m > n; equality is never interesting in these situations. This assump-
tion is very common and we’ll use it repeatedly without comment.
39
(lim sup s
n
= lim inf s
n
) Since (s
n
) is Cauchy, given ϵ > 0,
∃N such that m, n > N =⇒
|
s
n
−s
m
|
< ϵ =⇒ s
n
< s
m
+ ϵ
Taking v
N
= sup{s
n
: n > N}, we see that
m > N =⇒ v
N
≤ s
m
+ ϵ
Taking the infimum of the right hand side yields
v
N
≤ u
N
+ ϵ (since u
N
= inf{s
m
: m > N})
Since (v
N
) is monotone-down and (u
N
) monotone-up, we see that
lim sup s
n
≤ v
N
≤ u
N
+ ϵ ≤ lim inf s
n
+ ϵ =⇒ lim sup s
n
≤ lim inf s
n
+ ϵ
This last holds for all ϵ > 0, whence lim sup s
n
≤ lim inf s
n
. By Lemma 10.6 we have
equality.
By Lemma 10.8, we conclude that (s
n
) converges to lim sup s
n
= lim inf s
n
.
In view of the Theorem, the previous examples 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 (10.10.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 therefore convergent; good luck explicitly finding its limit though!
The main point is easy to miss: Cauchy Completeness provides a powerful tool for determining
whether a sequence converges without first guessing a limit. While the result depends on monotone
convergence (via limit superior/inferior), it is more powerful in that it applies even to non-monotone
sequences. We finish with an application of this idea.
An Alternative Definition of R Cauchy sequences suggest a definition of the real numbers which
does not rely on Dedekind cuts (Section 6).
Define an equivalence relation ∼ on the collection C of all Cauchy sequences of rational numbers:
24
( s
n
) ∼ (t
n
) ⇐⇒ lim(s
n
−t
n
) = 0
We then define R :=
C
∼
. 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. Some work is still required to
define +, ·, ≤, etc., and to verify the axioms of a complete ordered field—we won’t pursue this.
24
We don’t need real numbers to define the limit of the rational sequence (s
n
−t
n
): ∀ϵ ∈ Q
+
is enough. . .
40
Exercises 10. 1. Use the definition to show that the sequence with n
th
term 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 10.10.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) Use parts (a) and (b) to prove that (s
n
) is monotone-up.
(Hint: consider
s
n+1
s
n
)
(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 limit is e).
(Hint: compute t
n
−s
n
)
41
11 Subsequences
The general behavior of a sequence is often hard to ascertain, but if we delete some of its terms we
might obtain a subsequence with interesting behavior.
Definition 11.1. 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, with order inherited from the original sequence.
Example 11.2. Take s
n
= (−1)
n
(recall Example 8.6.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 result illustrated in the example, that every bounded
sequence has a convergent subsequence (the famous Bolzano–Weierstraß theorem).
Lemma 11.3. If lim
n→∞
s
n
= s, then every subsequence (s
n
k
) also satisfies lim
k→∞
s
n
k
= s.
Proof. Suppose s is finite and let ϵ > 0 be 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 11.4. 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
42
Theorem 11.5. 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
Combining with the lemmas, we may assume these subsequences are monotonic.
Example 11.6. 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
, s
n
k
> k}
Choosing the minimum isn’t necessary here, but it at
least 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 10.8 says that lim s
n
= −∞, whence
( s
n
) itself is a suitable subsequence.
(lim sup s
n
= v finite) We follow an inductive construction: let n
1
= 1 and define s
n
k
for k ≥ 2 via,
• Since (v
N
) is monotone-down and converges to v, take ϵ =
1
2k
to see that
25
∃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 4.8 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.
25
(v
N
) being monotone-down is crucial: if N satisfies v
N
−v <
1
2k
, so does N
k
:= max{N, n
k−1
}.
43
Example (11.6 cont.). The example shows why the two-step construction is necessary. It may seem
that we should simply be able to modify subsequences of (u
N
) and (v
N
). Indeed,
( u
N
) =
−1, −1, −1, −1, −
1
2
, −
1
2
, −
1
2
, −
1
2
, −
1
3
, −
1
3
, −
1
3
, −
1
3
, . . .
contains a monotonic subsequence of (s
n
) converging to lim inf s
n
= 0. Unfortunately, the same isn’t
true for (v
N
) = (2, 1, 1, 1, 1 . . .) , where v
N
k
= 1 for all k ≥ 2; taking n
k
= 2k − 1 results in
s
n
k
= 1 −
1
2k −1
> 1 −
1
2k
= v
N
k
−
1
2k
The above discussion rapidly provides two results, the first of which is Exercise 3.
Theorem 11.7 (Lemma 10.8 with converse). For any sequence,
lim sup s
n
= lim inf s
n
⇐⇒ lim s
n
exists
Theorem 11.8 (Bolzano–Weierstraß). Every bounded sequence has a convergent subsequence.
Proof 1. Lemma 11.4 says there exists a monotone subsequence. This is bounded and thus converges
by the monotone convergence theorem.
Proof 2. By Theorem 11.5, 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
generalizing to higher dimensions (rather than intervals, take boxes. . . ).
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!). 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
;
26
call this half-interval E
1
and choose any s
n
1
∈ E
1
for which 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 11.9. (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
26
Only finitely many terms in (s
n
) come before s
n
0
. . .
44
Subsequential Limits, Divergence by Oscillation & Closed Sets
Recall Definition 9.7, where we stated that 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 11.7
⇐⇒ lim inf s
n
= lim sup s
n
Thm 11.5
⇐⇒ (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 11.10. 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 11.11. 1. The sequence defined by s
n
=
1
n
has only one subsequential limit, namely zero.
Recall Lemma 11.3: 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 full set of 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 4.12), 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
27
r
n
k
∈ S
k
such that n
k
> n
k−1
• Since
|
r
n
k
− a
|
<
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 11.9, 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.
45
Theorem 11.12. 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 11.5, 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 11.7, 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. Using sequences, we can make a formal definition.
Definition 11.13. 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.
• A is closed if it equals its closure: A = A.
Examples 11.14. 1. The interval [0, 1] is closed. If (s
n
) ⊆ [0, 1] has lim s
n
= s, then
0 ≤ s
n
≤ 1
Thm 8.8
=⇒ 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 interval (0, 1] is not closed since its closure is (0, 1] = [0, 1]. In particular, the sequence
s
n
=
1
n
lies in the original interval but has limit 0. Indeed this example shows that an infinite
union of closed intervals need not be closed.
Theorem 11.15. If (s
n
) is a sequence, then its set of (finite) subsequential limits is closed.
We omit the proof since it is hard to read, involving unpleasantly many subscripts (subsequences of
subsequences. . . ).
27
As in the proof of Theorem 11.5, we could make this more explicit by choosing minimums, but there is no need: if
there are infinitely many r
n
in S
k
, then only finitely many of them can come before r
n
k−1
.
46
Exercises 11. 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
(a) For each sequence, give an example of a monotone subsequence.
(b) For each sequence, state its set of subsequential limits.
(c) For each sequence, state its lim sup and lim inf.
(d) Which of the sequences converge? diverge to +∞? diverge to −∞?
(e) Which of the sequences are bounded?
2. Prove the case of Lemma 11.3 when lim s
n
= ∞
3. Suppose that lim s
n
= s (could be ±∞). Use Theorem 11.5 and Lemma 11.3 to prove that
lim sup s
n
= s = lim inf s
n
.
(This completes the proof of Theorem 11.7)
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 11.8) 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 11.13.
(b) Is there a sequence (s
n
) such that (0, 1) is its set of subsequential limits?
7. 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 11.11.5)
8. (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
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
12 Lim sup and Lim inf
In this 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 12.1. Let (s
n
), (t
n
) be bounded sequences.
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
Modifications can be made infima and products of sequences (Exercise 3).
Example 12.2. To see that equality is unlikely, take s
n
= (−1)
n
= −t
n
, then
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}
Simply take limits as N → ∞ for the first result.
2. By part 1, we already know that
lim sup(s
n
+ t
n
) ≤ s + lim sup t
n
For the other direction, let a
n
= s
n
+ t
n
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 12.3. 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 ( †)
48
Examples 12.4. 1. Here is a quick proof that lim n
1/n
= 1 (recall Theorem 9.5): 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. Let s
n
= n! and apply the corollary to see that
lim(n!)
1/n
= lim
s
n+1
s
n
= lim(n + 1) = ∞
Proof. Assume lim sup
s
n+1
s
n
= L = ∞ (otherwise the third inequality is trivial) and let ϵ > 0. Then
lim
N→∞
sup
s
n+1
s
n
: n > N
< L + ϵ =⇒ ∃N such that sup
s
n+1
s
n
: n > N
< L + ϵ
For brevity, denote a = L + ϵ and b = a
−N−1
|
s
N+1
|
. For any n > N, we therefore have
s
n+1
s
n
< a =⇒
|
s
n
|
< a
n−N−1
|
s
N+1
|
=⇒
|
s
n
|
1/n
< a
a
−N−1
|
s
N+1
|
1/n
= ab
1/n
=⇒ lim sup
|
s
n
|
1/n
≤ a lim b
1/n
= a = L + ϵ
Since this holds for all ϵ > 0, 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 12. 1. Compute lim
1
n
( n!)
1/n
(Hint: let s
n
=
n!
n
n
in Theorem 12.3 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 12.3 and hence conclude that the converse of (†) is false.
49
