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{a1a2, … }, which exists by completeness of R. Thus, each an ≤ L. On the other hand, for each ε>0, since L-ε is not an upper bound of the {an}, we can find aN > L-ε. Hence for all nN, we have an ≥ aN > L-ε while an ≤ 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 (xn) 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 xn > 0. Hence, (xn) 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 xn ≥ 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 an be the n-th partial sum. Since n! ≥ 2n-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, an 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 (an) where

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

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 nN, we have |an – L| < ε/2. Hence, when mnN, 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 mn > N, we get |am – an| < 1. Fix some n>N and let B = |an|. It follows that for all m>N, |am| ≤ |am – an| + |an| < B+1. So the set of am for mN 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 (an) 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 bn takes the sup of more elements than bn+1. Since (an) has a lower bound so does (bn) and by MCT, (bn) converges to some L.

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

  • when mnN, we have |aman| < ε/2;
  • when nN, we have |bn – L| < ε/2, or L-(ε/2) < bL+(ε/2).

Now since L-(ε/2) < bN+1, 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 nN 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 mN, 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 an → L and cn → L. Then bn → L.

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

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

Hence when nN, 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 2sin(n) ≤ 2 and 0<a_n \le 2/n^2. Since 2/n2 → 0, the result follows from the squeeze theorem. ♦

Cesàro mean

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

Sketch of answer (highlight to read). [ For ε > 0, pick N such that if n>N, |anL| < ε/2. Then |bnL| ≤ (|a1L|+|a2L|+…+|anL|)/n. Let B=|a1L|+|a2L|+…+|aN-L|. Then |bnL|≤(B/n) + ε/2. So pick M>max(N, 2B/ε). Then when n>MB/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 an = (-1)n, 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

subsequence of a sequence (an) is a sequence of the form (bm), where

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

Thus in the sequence an = (-1)n, 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 (an) be a sequence.

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

Proof.

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

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

This entry was posted in Notes and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s