1. 3. CRITERION FOR CONVERGENCE Example 1.2.21. The order rule in Proposition 1.1.5 reflects the intuition that, if z is very close to 3 and y is very close to 5, then a must be less than y. More specifically, we know a< y when and y are within +l of 3 and 5. Here l is half of the distance Suppose a≤yn,limn→axn=l,limn→n=k. For any∈>0, there is M, such that (you should know from earlier examples how to find this N) m>N , Picking any n>N, we get ≤n<k+∈. Therefore we proved that I-E<k+e for any E>0. It is easy to see that the property is the same as l< h Conversely, we assume limn-oo n=L, limn-oo yn= k, and l k. For any e>0, there is N, such that n> N implies In-l<e and I3n-k <E.Then Tn<l+e, n>k-E=yn (k-∈)-(l+∈) By choosing e k-L 0 at the beginning of the argument, we conclude that Un >n for n>M Exercise1.212. Prove that if limn→∞xn=l, then limn→orn={l Exercise 1.2.13. Prove that limn+oo lIn-4 =0 if and only if limn-+oo n=L Exercise 1.2.14. Prove that if limn_oo In=l, then limn-oo cIn= cl Exercise 1.2.15. Prove that a sequence an converges if and only if the subsequences 2n and 2n+1 converge to the same limit. This is a special case of Proposition 1.1.6 Exercise 1.2.16. Suppose In>0 for sufficiently big n and limn-oo n =0. Prove that limn→+=0 for any p>0. Exercise 1.2.17. Suppose n>0 for sufficiently big n and limn-oo n=0. Suppose yn for sufficiently big n and some constant c>0. Prove that limn-oo rmn=0 1.3 Criterion for Convergence Any number close to 3 must be between 2 and 4, and in particular have the absolute value no more than 4. The intuition leads to the following result Theorem 1.3.1. If n converges, then lrn s B for a constant B and all n
1.3. CRITERION FOR CONVERGENCE 37 Example 1.2.21. The order rule in Proposition 1.1.5 reflects the intuition that, if x is very close to 3 and y is very close to 5, then x must be less than y. More specifically, we know x < y when x and y are within ±1 of 3 and 5. Here 1 is half of the distance between 3 and 5. Suppose xn ≤ yn, limn→∞ xn = l, limn→∞ yn = k. For any > 0, there is N, such that (you should know from earlier examples how to find this N) n > N =⇒ |xn − l| < , |yn − k| < . Picking any n > N, we get l − < xn ≤ yn < k + . Therefore we proved that l − < k + for any > 0. It is easy to see that the property is the same as l ≤ k. Conversely, we assume limn→∞ xn = l, limn→∞ yn = k, and l < k. For any > 0, there is N, such that n > N implies |xn − l| < and |yn − k| < . Then n > N =⇒ xn < l + , yn > k − =⇒ yn − xn > (k − ) − (l + ) = k − l − 2. By choosing = k − l 2 > 0 at the beginning of the argument, we conclude that yn > xn for n > N. Exercise 1.2.12. Prove that if limn→∞ xn = l, then limn→∞ |xn| = |l|. Exercise 1.2.13. Prove that limn→∞ |xn − l| = 0 if and only if limn→∞ xn = l. Exercise 1.2.14. Prove that if limn→∞ xn = l, then limn→∞ cxn = cl. Exercise 1.2.15. Prove that a sequence xn converges if and only if the subsequences x2n and x2n+1 converge to the same limit. This is a special case of Proposition 1.1.6. Exercise 1.2.16. Suppose xn ≥ 0 for sufficiently big n and limn→∞ xn = 0. Prove that limn→∞ x p n = 0 for any p > 0. Exercise 1.2.17. Suppose xn ≥ 0 for sufficiently big n and limn→∞ xn = 0. Suppose yn ≥ c for sufficiently big n and some constant c > 0. Prove that limn→∞ x yn n = 0. 1.3 Criterion for Convergence Any number close to 3 must be between 2 and 4, and in particular have the absolute value no more than 4. The intuition leads to the following result. Theorem 1.3.1. If xn converges, then |xn| ≤ B for a constant B and all n
CHAPTER 1. LIMIT The the basically says that any convergent sequence is bounded. The num ber B is a bound for the sequence If In B for all n, then we say an is bounded above, and B is an upper bound n> B for all n, then we say In is bounded below, and B is a lower bound. A equence is bounded if and only if it is bounded above and bounded below The sequences n,<+(1)" n+I diverge because they are not bounded. On the other hand, the sequence 1, -1, 1, -l,... is bounded but diverges. Therefore the converse of Theorem 1.3. 1 is not true in general Exercise 1.3.1. Prove that if an is bounded for sufficiently big n, i.e.,In B forn>N then In is still bounded Exercise 1.3.2. Suppose n is the union of two subsequences ak and ak. Prove that In is bounded if and only if both al. and l. are bounded 1.3.1 Monotone Sequence The converse of Theorem 1.3. 1 holds under some additional assumption. a sequence n is increasing if It is strictly increasing if The concepts of decreasing and strictly decreasing can be similarly defined. More- over, a sequence is monotone if it is either increasing or decreasin ilo he sequences n 2n v2 are(strictly) decreasing. The sequences n are Theorem 1.3.2. A monotone sequence converges if and only if it is bounded. An increasing sequence n is always bounded below by its first term a1. Therefore n is bounded if and only if it is bounded above. Similarly, a decreasing sequence is bounded if and only if it is bounded below The world record for 100 meter dash is a decreasing sequence bounded below by 0. The proposition reflects the intuition that there is a limit on how fast human being can run. We note that the proposition does not tells us the exact value of the limit, just like we do not know the exact limit of the human ability Example 1.3. 1. Consider the sequence
38 CHAPTER 1. LIMIT The theorem basically says that any convergent sequence is bounded. The number B is a bound for the sequence. If xn ≤ B for all n, then we say xn is bounded above, and B is an upper bound. If xn ≥ B for all n, then we say xn is bounded below, and B is a lower bound. A sequence is bounded if and only if it is bounded above and bounded below. The sequences n, n 2 + (−1)n n + 1 diverge because they are not bounded. On the other hand, the sequence 1, −1, 1, −1, . . . is bounded but diverges. Therefore the converse of Theorem 1.3.1 is not true in general. Exercise 1.3.1. Prove that if xn is bounded for sufficiently big n, i.e., |xn| ≤ B for n ≥ N, then xn is still bounded. Exercise 1.3.2. Suppose xn is the union of two subsequences x 0 k and x 00 k . Prove that xn is bounded if and only if both x 0 k and x 00 k are bounded. 1.3.1 Monotone Sequence The converse of Theorem 1.3.1 holds under some additional assumption. A sequence xn is increasing if x1 ≤ x2 ≤ x3 ≤ · · · ≤ xn ≤ xn+1 ≤ · · · . It is strictly increasing if x1 < x2 < x3 < · · · < xn < xn+1 < · · · . The concepts of decreasing and strictly decreasing can be similarly defined. Moreover, a sequence is monotone if it is either increasing or decreasing. The sequences 1 n , 1 2 n , √n 2 are (strictly) decreasing. The sequences − 1 n , n are increasing. Theorem 1.3.2. A monotone sequence converges if and only if it is bounded. An increasing sequence xn is always bounded below by its first term x1. Therefore xn is bounded if and only if it is bounded above. Similarly, a decreasing sequence is bounded if and only if it is bounded below. The world record for 100 meter dash is a decreasing sequence bounded below by 0. The proposition reflects the intuition that there is a limit on how fast human being can run. We note that the proposition does not tells us the exact value of the limit, just like we do not know the exact limit of the human ability. Example 1.3.1. Consider the sequence xn = 1 1 2 + 1 2 2 + 1 3 2 + · · · + 1 n2
1. 3. CRITERION FOR CONVERGENCE The sequence is clearly increasing. Moreover, the sequence is bounded above by 1++-+ 1+ 2 <2 Therefore the sequence converges The limit of the sequence is the sum of the infinite serie 11 n=1 We will see that the sum is actually 6 Exercise 1.3.3. Show the convergence of sequences 1 13+2+3 1 12 1 1 1 3 1)(2n+1) 4.xn=+x+…+ Example1.32. The number v2+√2+√+… is the limit of the sequence a inductively ,xn+1=√2+xn After trying first couple of terms, we expect the sequence to be increasing. This can be verified by induction. We have I2=V2+V2>21=V2. Moreover, if we the n+1=v2+In>v2+n-1=n This proves inductively that Tn is indeed increasing Next we claim that n is bounded above. For an increasing sequence, we expect its limit to be the upper bound. So we find the hypothetical limit first. Taking the limit on both sides of the equality d+1=2 +an and applying the arithmetic rule, we get 12=2+1. The solution is l=2 or -1. Since In>0, by the order rule, we must have 1>0. Therefore we conclude that l=2
1.3. CRITERION FOR CONVERGENCE 39 The sequence is clearly increasing. Moreover, the sequence is bounded above by xn ≤ 1 + 1 1 · 2 + 1 2 · 3 + · · · + 1 (n − 1)n = 1 + 1 − 1 2 + 1 2 − 1 3 + · · · + 1 n − 1 − 1 n = 2 − 1 n < 2. Therefore the sequence converges. The limit of the sequence is the sum of the infinite series X∞ n=1 1 n2 = 1 + 1 2 2 + 1 3 2 + · · · + 1 n2 + · · · . We will see that the sum is actually π 2 6 . Exercise 1.3.3. Show the convergence of sequences. 1. xn = 1 1 3 + 1 2 3 + 1 3 3 + · · · + 1 n3 . 2. xn = 1 1 2.4 + 1 2 2.4 + 1 3 2.4 + · · · + 1 n2.4 . 3. xn = 1 1 · 3 + 1 3 · 5 + 1 5 · 7 + · · · + 1 (2n − 1)(2n + 1). 4. xn = 1 1! + 1 2! + · · · + 1 n! . Example 1.3.2. The number q 2 + p 2 + √ 2 + · · · is the limit of the sequence xn inductively given by x1 = √ 2, xn+1 = √ 2 + xn. After trying first couple of terms, we expect the sequence to be increasing. This can be verified by induction. We have x2 = p 2 + √ 2 > x1 = √ 2. Moreover, if we assume xn > xn−1, then xn+1 = √ 2 + xn > p 2 + xn−1 = xn. This proves inductively that xn is indeed increasing. Next we claim that xn is bounded above. For an increasing sequence, we expect its limit to be the upper bound. So we find the hypothetical limit first. Taking the limit on both sides of the equality x 2 n+1 = 2 + xn and applying the arithmetic rule, we get l 2 = 2 + l. The solution is l = 2 or −1. Since xn > 0, by the order rule, we must have l ≥ 0. Therefore we conclude that l = 2
CHAPTER 1. LIMIT The hypothetical limit value suggests that In 2 for all n. Again we verify this by induction. We already have c1=v2< 2. If we assume Tn < 2, then 2+xn<√2+ This proves inductively that n <2 for all n We conclude that In is increasing and bounded above. By Theorem 1.3.2, the sequence converges, and the hypothetical limit value 2 is the real limit value Figure 1.3. 1 suggests that our conclusion actually depends only on the general shape of the graph of the function, and has little to do with the exact formula V2+x. f(x3) Figure 1.3.1: Limit of inductively defined sequence. Exercise 1.3.4. Suppose a sequence Tn satisfies In+1= v2+In 1. Prove that if -2 1< 2, then n is increasing and converges to 2 2. Prove that if 21>2, then In is decreasing and converges to 2 Exercise 1.3.5. For the three functions f()in Figure 1.3.2, study the convergence of the sequences In defined by In+1=f(n). Your answer depends on the initial value a1 Exercise 1.3.6. S 1=5(x2+xn 1. If 1>l, then the sequence is increasing and diverges 2. If0< 1< l, then the sequence is decreasing and converges to 0 3. If-1<.1<0, then the sequence is increasing and converges to O 4. If-2<1<-l, then the sequence is decreasing for n >2 and converges to 0
40 CHAPTER 1. LIMIT The hypothetical limit value suggests that xn < 2 for all n. Again we verify this by induction. We already have x1 = √ 2 < 2. If we assume xn < 2, then xn+1 = √ 2 + xn < √ 2 + 2 = 2. This proves inductively that xn < 2 for all n. We conclude that xn is increasing and bounded above. By Theorem 1.3.2, the sequence converges, and the hypothetical limit value 2 is the real limit value. Figure 1.3.1 suggests that our conclusion actually depends only on the general shape of the graph of the function, and has little to do with the exact formula √ 2 + x. x1 f(x1) x2 f(x2) x3 f(x3) x4 y = x l y = f(x) Figure 1.3.1: Limit of inductively defined sequence. Exercise 1.3.4. Suppose a sequence xn satisfies xn+1 = √ 2 + xn. 1. Prove that if −2 < x1 < 2, then xn is increasing and converges to 2. 2. Prove that if x1 > 2, then xn is decreasing and converges to 2. Exercise 1.3.5. For the three functions f(x) in Figure 1.3.2, study the convergence of the sequences xn defined by xn+1 = f(xn). Your answer depends on the initial value x1. Exercise 1.3.6. Suppose a sequence xn satisfies xn+1 = 1 2 (x 2 n + xn). Prove the following statements. 1. If x1 > 1, then the sequence is increasing and diverges. 2. If 0 < x1 < 1, then the sequence is decreasing and converges to 0. 3. If −1 < x1 < 0, then the sequence is increasing and converges to 0. 4. If −2 < x1 < −1, then the sequence is decreasing for n ≥ 2 and converges to 0
1. 3. CRITERION FOR CONVERGENCE Figure 1.3.2: Three functions 5. If 1<-2, then the sequence is increasing for n >2 and diverges. Exercise 1.3.7. Determine the convergence of inductively defined sequences. Your answer may depend on the initial value I1 +1 2 Exercise 1.3.8. Determine the convergence of inductively defined sequences, a>0. In some cases, the sequence may not be defined after certain number of terms 1 n+1 4.xn+1 atan Exercise 1.3.9. Explain the continued fraction expansion 1+ What if 2 on the right side is changed to some other positive number Exercise 1.3.10. For any a, b>0, define a sequence by b Prove that the Exercise 1.3.11. The arithmetic and the geometric means of a, 6>0 are 2 and vab By repeating the process, we get two sequences defined by 1=a, 91=6, n+1= 2
1.3. CRITERION FOR CONVERGENCE 41 Figure 1.3.2: Three functions 5. If x1 < −2, then the sequence is increasing for n ≥ 2 and diverges. Exercise 1.3.7. Determine the convergence of inductively defined sequences. Your answer may depend on the initial value x1. 1. xn+1 = x 2 n . 2. xn+1 = x 2 n + 1 2 . 3. xn+1 = 2x 2 n − 1. 4. xn+1 = 1 xn . 5. xn+1 = 1 + 1 xn . 6. xn+1 = 2 − 1 xn . Exercise 1.3.8. Determine the convergence of inductively defined sequences, a > 0. In some cases, the sequence may not be defined after certain number of terms. 1. xn+1 = √ a + xn. 2. xn+1 = √ xn − a. 3. xn+1 = √ a − xn. 4. xn+1 = √3 a + xn. 5. xn+1 = √3 xn − a. 6. xn+1 = √3 a − xn. Exercise 1.3.9. Explain the continued fraction expansion √ 2 = 1 + 1 2 + 1 2 + 1 2 + · · · . What if 2 on the right side is changed to some other positive number? Exercise 1.3.10. For any a, b > 0, define a sequence by x1 = a, x2 = b, xn = xn−1 + xn−2 2 . Prove that the sequence converges. Exercise 1.3.11. The arithmetic and the geometric means of a, b > 0 are a + b 2 and √ ab. By repeating the process, we get two sequences defined by x1 = a, y1 = b, xn+1 = xn + yn 2 , yn+1 = √ xnyn