Basic Analysis: Sequence Convergence (2)

Monotone Convergence

We start with a useful theorem.

Monotone Convergence Theorem (MCT). A sequence $(a_n)$ is monotonically increasing (or just increasing) if $a_n \le a_{n+1}$ for all n. Now the theorem says: an increasing sequence with an upper bound is convergent.

Proof.

Let L = sup{a₁, a₂, … }, which exists by completeness of R. Thus, each a_n ≤ L. On the other hand, for each ε>0, since L-ε is not an upper bound of the {a_n}, we can find a_N > L-ε. Hence for all n > N, we have a_n ≥ a_N > L-ε while a_n ≤ L which gives:

$n>N \implies L-\epsilon < a_n \le L \implies |L-a_n|< \epsilon.$ ♦

In practice, the monotonic convergence theorem often tells us a limit exists without giving any hint on what it might be. In some cases, it may be derivable.

Example 1. Consider the recurrence relations $x_0=2$ , $x_{n+1} = 6-\frac 5{x_n}$ . Prove that (x_n) is convergent and find its limit.

Answer. We shall prove that $2\le x_n < x_{n+1}$ by induction. For n=0 this is obvious. Suppose we have $2\le x_k < x_{k+1}$ . For the next iteration, we have:

$x_{k+2} = 6 - \frac 5{x_{k+1}} > 6 - \frac 5{x_k} = x_{k+1}.$

This shows that $2\le x_{k+1} < x_{k+2}$ which completes the induction. Next, note that $x_{n+1} = 6 - \frac 5{x_n} < 6$ since x_n > 0. Hence, (x_n) is an increasing sequence with an upper bound and must converge to some L.

From $x_{n+1} = 6-\frac 5{x_n}$ , the LHS → L while the RHS → 6-(5/L). Equating and solving give L=1 or L=5. Since each x_n ≥ 2, the limit can’t be 1. So L=5. ♦

Example 2. Prove that $1 + \frac 1{\sqrt{2!}} + \frac 1{\sqrt{3!}} + \ldots$ converges.

Answer. Let a_n be the n-th partial sum. Since n! ≥ 2^n-1, we have $1/\sqrt{n!} \le 1/2^{(n-1)/2}$ . But $\sum_n 1/2^{(n-1)/2}$ converges by sum of geometric series. Hence, a_n is an increasing sequence with an upper bound. By MCT, it converges. ♦

However, there’s no easy way to evaluate this sum.

Note: in proving MCT, we explicitly used the fact that R is complete. This property is critical since the theorem does not hold for Q. For example, we can easily have the sequence 1, 1.4, 1.41, 1.414, … which contains more and more significant figures of √2. We get an increasing sequence of rational numbers, with no limit in Q. On the other hand, since R is complete, there’s a limit in R.

This gives a good sense of what completeness means. We get a mental picture of “gaps” occurring in Q, so that a sequence of elements which get successively closer still may not converge. The next section will elucidate this even further.

Cauchy Sequences

We’ll define what it means for a sequence of numbers to get successively closer.

Definition. A Cauchy sequence is a sequence (a_n) where

for any ε>0, there exists N such that when m, n > N, we have |a_m– a_n| < ε.

Some results are quite easy to prove.

A convergent sequence is Cauchy.
A Cauchy sequence is bounded.

Proof.

For the first statement, suppose the sequence → L. For any ε>0, there exists N such that when n > N, we have |a_n – L| < ε/2. Hence, when m, n > N, we have $|a_m - a_n| \le |a_m-L| + |L-a_n| < \epsilon$ . So the sequence is Cauchy.

For the second, pick ε=1. We get an N such that when m, n > N, we get |a_m – a_n| < 1. Fix some n>N and let B = |a_n|. It follows that for all m>N, |a_m| ≤ |a_m – a_n| + |a_n| < B+1. So the set of a_m for m > N is bounded. Since there’re only finitely many terms up to N, the whole sequence is bounded. ♦

Notice that the property of being a Cauchy sequence is inherent in the sequence and does not rely on the embedding. In short, a sequence of rational numbers is Cauchy regardless whether we consider it embedded in Q or in R. On the other hand, whether a sequence of rational numbers converges depends on whether the ambient space is Q or R.

Theorem. A Cauchy sequence of real numbers converges to a real number.

Proof. Suppose (a_n) is Cauchy. In particular, it’s bounded and we can let $b_n = \sup(a_n, a_{n+1}, a_{n+2}, \dots)$ . Then $b_1 \ge b_2 \ge b_3\ge \ldots$ since b_n takes the sup of more elements than b_n+1. Since (a_n) has a lower bound so does (b_n) and by MCT, (b_n) converges to some L.

It remains to show (a_n) → L. Let ε > 0. Find integer N such that:

when m, n > N, we have |a_m – a_n| < ε/2;
when n > N, we have |b_n – L| < ε/2, or L-(ε/2) < b_n< L+(ε/2).

Now since L-(ε/2) < b_N₊₁, and sup is the minimum upper bound, L-(ε/2) is not an upper bound of $a_{N+1}, a_{N+2}, a_{N+3}, \ldots$ so we can find n > N such that $a_n \ge L-\frac\epsilon 2$ . Yet $a_n \le b_{N+1} < L+\frac\epsilon 2$ , which gives $|a_n - L| \le \frac\epsilon 2$ .

Hence, for all m > N, we have $|a_m - L| \le |a_m -a_n| + |a_n - L| < \epsilon$ . ♦

Squeeze Theorem

The following theorem is simple but handy.

Squeeze Theorem. Let $(a_n), (b_n), (c_n)$ be three sequences with $a_n \le b_n \le c_n$ . Suppose a_n → L and c_n → L. Then b_n → L.

Proof. Let ε > 0. Pick N such that whenever n > N :

$|a_n - L| < \epsilon\implies L-\epsilon < a_n < L+\epsilon$ ;
$|c_n - L| < \epsilon\implies L-\epsilon < c_n < L+\epsilon$ ;

Hence when n > N, we have $b_n \le c_n < L+\epsilon$ and $b_n \ge a_n > L-\epsilon$ , i.e. $|b_n - L| < \epsilon$ . ♦

Example 3. Prove that $a_n =2^{\sin(n)}/n^2$ has a limit of 0.

Proof. Since sin(n) ≤ 1, we have 2^sin(n) ≤ 2 and $0<a_n \le 2/n^2$ . Since 2/n² → 0, the result follows from the squeeze theorem. ♦

Cesàro mean

Exercise (hard). Prove that if a_n → L, and $b_n = (a_1 + a_2 + \ldots + a_n)/n$ , then b_n → L.

Sketch of answer (highlight to read). [ For ε > 0, pick N such that if n>N, |a_n–L| < ε/2. Then |b_n–L| ≤ (|a₁–L|+|a₂–L|+…+|a_n–L|)/n. Let B=|a₁–L|+|a₂–L|+…+|a_N-L|. Then |b_n–L|≤(B/n) + ε/2. So pick M>max(N, 2B/ε). Then when n>M, B/n < ε/2 also. ]

The new sequence which is obtained via taking the mean of the first n terms is called the Cesàro mean. The above exercise tells us taking the Cesàro mean preserves the limit if it already exists. On the other hand, some non-converging sequences converge after taking the Cesàro mean. E.g. if a_n = (-1)ⁿ, then its Cesàro mean converges to 0 since the n-th term is bounded by [-1/n, +1/n], so it converges by the squeeze theorem.

Subsequences

A subsequence of a sequence (a_n) is a sequence of the form (b_m), where

$b_m = a_{n(m)}$ , for some increasing n(1) < n(2) < n(3) < …

Thus in the sequence a_n = (-1)ⁿ, the even terms form a subsequence (+1, +1, +1, …) with indices n(1)=2, n(2)=4, n(3)=6, … . The odd terms form a subsequence (-1, -1, -1, …) with indices n(k)=2k-1. Hence, a non-convergent sequence can have subsequences which converge to different values.

Theorem. Let (a_n) be a sequence.

If lim (a_n) = L, then every subsequence converges to L.
If every subsequence converges to the same value L, then lim (a_n) = L.

Proof.

For the first statement, suppose we have a subsequence (b_m), where $b_m = a_{n(m)}$ , n(1) < n(2) < n(3) < … . Let ε>0. There exists N such that when n>N, |a_n–L| < ε. Since n(m) ≥ m, whenever m>N, we also have $|b_m-L|=|a_{n(m)}-L| < \epsilon$ . Hence the subsequence (b_m) also converges to L.

For the second statement, suppose (a_n) doesn’t converge to L. Unwinding the definition, there exists ε>0 such that for each N, there exists n>N such that |a_n–L| ≥ ε. In short, there are infinitely many n for which |a_n–L| ≥ ε. If we pick this subsequence, it cannot possibly converge to L. ♦