Lecture 9: Limsup, Liminf, and the Bolzano-Weierstrass Theorem

18.100A: Complete Lecture Notes Lecture 9: Limsup, Liminf, and the Bolzano-Weierstrass Theorem Theorem 1 (Some Special Sequences) What follows are some special sequences to have in our toolbox. 1. If p > 0, then limn→∞ n−p = 0. 1 2. If p > 0 then p n = 1. 1 3. limn→∞ n n = 1. Proof : 1. Let  > 0. Then, choose M > (1/)1/p . Hence, if n ≥ M , 1 1 1 − 0 = p ≤ p < . p n |n | M 2. Suppose p > 1. Then, p1/n − 1 > 0 which may be proven by induction. Furthermore, we have p = (1 + (p1/n − 1))n ≥ 1 + n(p1/n − 1). Therefore, 0 < p1/n − 1 ≤ If p < 1, then p−1 n . Hence, we may apply the Squeeze Theorem, obtaining limn→∞ |p1/n − 1| = 0. lim p1/n = lim n→∞ n→∞ 1 1 = = 1. 1/n 1 (1/p) Furthermore, if p = 1 then it is clear that limn→∞ p1/n = 1. Hence, in all cases, the limit is 1. 3. Let xn = n1/n − 1 ≥ 0. We want to show that limn→∞ xn = 0, as this will imply the end result. Notice that n n = (1 + xn ) = n   X n j=0 j xjn   n(n − 1) 2 n 2 n! · x2n = · xn . ≥ xn = 2 2(n − 2)! 2 Thus, for n > 1, r 0 ≤ xn ≤ 2 =⇒ xn → 0. n−1 Limsup/Liminf Question 2. Does a bounded sequence have a convergent subsequence? 1 Definition 3 (Limsup/Liminf) Let {xn } be a bounded sequence. We define, if the limits exist, lim sup xn := lim (sup{xk | k ≥ n}) n→∞ n→∞ lim inf xn := lim (inf{xk | k ≥ n}). n→∞ n→∞ These are called the limit superior and limit inferior respectively. We will now show that these limits always exist. Theorem 4 Let {xn } be a bounded sequence, and let an = sup{xk | k ≥ n} bn = inf{xk | k ≥ n}. Then, 1. {an } is monotone decreasing and bounded, and {bn } is monotone increasing and bounded. 2. lim inf n→∞ xn ≤ lim supn→∞ xn . Proof 1. Since, ∀ ∈ N, {xk | k ≥ n + 1} ⊆ {xk | k ≥ n}, we have that an+1 = sup{xk | k ≥ n + 1} ≤ sup{xk | k ≥ n} = an . Similarly, ∀n ∈ N, bn+1 ≥ bn . Given {xn } is a bounded sequence, ∃B ≥ 0 such that ∀n ∈ N, −B ≤ xn ≤ B. Therefore, ∀n ∈ N, −B ≤ bn ≤ an ≤ B which implies both sequences are bounded. 2. By the above equation, ∀n ∈ N, bn ≤ an =⇒ lim inf n→∞ xn = limn→∞ bn ≤ limn→∞ an = lim supn→∞ xn . Let’s consider a few examples. Example 5 Let xn = (−1)n . Calculate the lim inf and lim sup of this sequence. Proof : Notice that {(−1)k | l ≥ n} = {−1, 1}. Thus, the supremum of these sets is always 1 and the infimum is always −1. Therefore, lim sup xn = 1 and lim inf xn = −1. n→∞ n→∞  2 Example 6 Let xn = 1 n. Calculate the lim inf and lim sup of this sequence. Proof : We may do this directly: sup{1/k | k ≥ n} = 1 → 0 =⇒ lim sup xn = 0. n n→∞ inf{1/k | k ≥ n} = 0 → 0 =⇒ lim inf xn = 0. n→∞  The limit inferior and the limit superior allow us to answer the question posed at the beginning of this section. Theorem 7 Let {xn } be a bounded sequence. Then, there exists subsequences {xnk } and {xmk } such that lim xnk = lim sup xn k→∞ n→∞ lim xmk = lim sup xn . k→∞ n→∞ Proof : Let an = sup{xk | k ≥ n}. Then, ∃n1 ∈ N such that a1 − 1 < xn1 ≤ a1 . Now, ∃n2 > n1 such that an1 +1 − 1 < xn2 ≤ an1 +1 2 since an+1 = sup{xk | k ≥ n1 + 1}. Similarly, ∃n3 > n2 such that 1 < xn3 ≤ an2 +1 . 3 Continuing in this way, we obtain a sequence of integers n1 < n2 < n3 < . . . such that an2 +1 − ank +1 − 1 < xnk ≤ ank +1 . k+1 Given limk→∞ ank +1 = lim supn→∞ xn , by the Squeeze Theorem, lim xnk = lim sup xn . k→∞ n→∞ The direction for the lim inf works out the same way so that portion of the proof is left to the reader. Theorem 8 (Bolzano-Weierstrass) Every bounded sequence has a convergent subsequence. Remark 9. We may abbreviate the Bolzano-Weierstrass theorem to B-W. Proof : This follows immediately from the previous theorem, but is so important that it itself is a theorem. Notation 10 When it is clear, we may have the following notational shorthand: lim inf n→∞ xn := lim inf xn , and lim supn→∞ xn := lim sup xn . 3 Theorem 11 Let {xn } be a bounded sequence. Then, {xn } converges if and only if lim inf xn = lim sup xn . Proof ( ⇐= ) Suppose lim inf xn = lim sup xn . Then, ∀n ∈ N, inf{xk | k ≥ n} ≤ xn ≤ sup{xk | k ≥ n}. By the Squeeze Theorem, since limk→∞ inf{xk | k ≥ n} = limk→∞ sup{xk | k ≥ n} by assumption, we have lim xn = lim inf xn = lim sup xn . n→∞ Therefore, xn converges. ( =⇒ ) Let x = limn→∞ xn . Therefore, every subsequence of {xn } converges to x, so lim inf xn = x and lim sup xn = x by a theorem we proved in Lecture 7. Hence, lim inf xn = lim sup xn . 4