BSc EFDS Maths Foundations Lecture Notes PDF

Chapter 4 Sequences, Series, and Convergence 4.1 What is a Sequence? Definition 15 (Sequence). A sequence is, formally, a function a : N ! R. We write an instead of a(n). Instead of a, we usually write it as (an ) , (an )1 1...

Chapter 4 Sequences, Series, and Convergence 4.1 What is a Sequence? Definition 15 (Sequence). A sequence is, formally, a function a : N ! R. We write an instead of a(n). Instead of a, we usually write it as (an ) , (an )1 1 1 or (an )n=1 , sometimes replacing brackets with curly braces, to indicate it is a sequence. Example 14. Here are some sequences 1. an = n1 , 1+n 2. an = n , 3. an = 2n xn +1 4. x1 = 2 and xn+1 = 2. 4.2 What is Convergence? Definition 16 (Convergence of sequence). Let (an ) be a sequence and ` 2 R. Then an converges to `, tends to `, or an ! `, if for all " > 0, there is some N 2 N such that whenever n > N , we have |an `| < ". In symbols, this says (8" > 0)(9N 2 N)(8n N ) |an `| < ". We say ` is the limit of (an ). 43 44 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE In an e↵ort to decipher this complicated definition, it helps first to consider the meaning of |an a| < ✏. Definition 17. Given a real number a 2 R and a positive number ✏ > 0, the set V✏ (a) = {x 2 R : |x a| < ✏} is called the ✏-neighborhood of a. V✏ (a) a ✏ a a+✏ Notice that V✏ (a) consists of all of those points whose distance from a is less than ✏. Said another way, V✏ (a) is an interval, centered at a, with radius ✏. Recasting the definition of convergence in terms of ✏-neighborhoods gives a more geometric impression of what is being described. Definition 18 (Convergence of a Sequence: Topological Version). A sequence (an ) converges to a if, given any ✏-neighborhood V✏ (a) of a, there exists a point in the se- quence after which all of the terms are in V✏ (a). In other words, every ✏-neighborhood contains all but a finite number of the terms of (an ). In symbols (8" > 0)(9N 2 N)(8n N )xn 2 V✏ (a). Our two definitions for convergence say precisely the same thing; the natural number N in the original version of the definition is the point where the sequence (an ) enters V✏ (a), never to leave. It should be apparent that the value of N depends on the choice of ✏. The smaller the ✏-neighborhood, the larger N may have to be. A nice way to understand what is meant by an ! a is: the sequence (an ) will eventually get trapped inside every ✏-neighbourhood of a. Lemma 7 (Archimedean property v2). 1/n ! 0. R (1, 1) (2, 12 ) 1 (10, 10 ) N 1 1 1 1 1 0 6 5 4 3 2 1 R 4.2. WHAT IS CONVERGENCE? 45 Proof. The natural numbers are unbounded 1 )(8✏ > 0)(9N 2 N)N > ✏ 1 () (8✏ > 0)(9N 2 N) 0)(9N 2 N) 0 0)(9N 2 N)(8n N) 0 0 be arbitrary. 2. Demonstrate a choice for N 2 N. This step usually requires the most work, almost all of which is done prior to actually writing the formal proof. 3. Now, show that N actually works. 4. Assume n N. 5. With N well chosen, it should be possible to derive the inequality |xn x| < ✏. Example 15. We are now going to use the definition of convergence to prove that p1 ! 0. n We shall start by by start playing around with the definition by choosing ✏ = 0.1. How large does N have to be so that p1N 0 < 0.1. We can see that N = 100 is not quite large enough, but N = 101 is large enough. Proof. In general, for every ✏ > 0, we can pick N > ✏12 (because the natural numbers are unbounded) , and so p1N < ✏ and (8n N ) p1n < ✏. Therefore, 1 (8✏ > 0)(9N 2 N)(8n N) p 0 < ✏. n 46 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE Example 16. Show ✓ ◆ n+1 !1 n We need to consider the inequality n+1 1 1, we have n+1 n+1 1 1 1 < ✏ () 1 < ✏ () 1 + 1 < ✏ () n > n n n ✏ Define an = n+1 n and we know we can pick N 2 N such N > 1 ✏ Therefore, (8✏ > 0)(9N 2 N)(8n N )|an 1| < ✏. We are also interested in proving non-convergence. We do this using proof by contradiction. Example 17. Prove that the sequence an = ( 1)n does not converge. Proof. Assume for the sake of contradiction that the sequence converges to some limit L 2 R. Therefore, (8✏ > 0)(9N 2 N)(8n N )|( 1)n L| < ✏. Hence, we have ( 1)N L < ✏. Now, n N ) |( 1)n L| < ✏. When n is even, 1 ✏ < L < 1 + ✏. However, when n is odd, |( 1)n L| = | 1 L| < ✏ ) 1 ✏ 0)(9N 2 N)(8n N )|an a| < ✏ ) (9L, U 2 R)(8n 2 N)L  an  U. (8✏ > 0)(9N 2 N)(8n N )|an a| () (8✏ > 0)(9N 2 N)(8n N )a ✏ < an < a + ✏ Let us set ✏ = 1. Denote the associated N by N1 (8n N1 )a 1 < an < a + 1. Now for n < N1 we need to consider {a1 ,... , aN1 1 }, which will have a maximum element, denoted by M and a minimum element, denoted by m. Therefore, (8n  N1 1)m  an  M. Hence, (8n N1 )a 1 < an < a + 1 ^ (9m, M 2 R)(8n  N1 1)m  an  M )(8n 2 N)(9m, M 2 R) min{a 1, m}  an  max{a + 1, M } )(8n 2 N)(9L, U 2 R)L  an  U. 4.4 Sequence Algebra The following theorem illustrates illustrate that sequences behave extremely well with respect to the operations of addition, multiplication, division, and order. Theorem 2 (Algebraic Limit Theorem). Let lim an = a, and lim bn = b. Then, 1. (8c 2 R) lim (can ) = ca; 2. lim (an + bn ) = a + b; 3. lim (an bn ) = ab; 4. lim (an /bn ) = a/b, provided b 6= 0. 4.4. SEQUENCE ALGEBRA 49 Proof. 1. We know that (8✏ > 0)(9N 2 N)(8n N )|an a| < ✏. Now we exploit the power of the fact that above statement works 8✏ > 0. ✓ ◆ ✏ ✏ 8 > 0 (9N 2 N)(8n N )|an a| < |c| |c| ) (8✏ > 0)(9N 2 N)(8n N )|c||an a| < ✏ Now we note that |c||an a| = |c(an a)|, because the product of two real numbers, ignoring signs before multiplication is the same as when we ignore the signs after multiplication. (8✏ > 0)(9N 2 N)(8n N )|c||an a| < ✏ () (8✏ > 0)(9N 2 N)(8n N )|c(an a)| < ✏ () (8✏ > 0)(9N 2 N)(8n N )|can ca| < ✏ () can ! ca 2. We know that ✏ (8✏ > 0)(9Na 2 N)(8n Na )|an a| < 2 ✏ ^(8✏ > 0)(9Nb 2 N)(8n Nb )|bn b| <. 2 Setting M = max(Na , Nb ), we see that ✏ ✏ (8✏ > 0)(9M 2 N)(8n M )|an a| < ^ |bn b| < 2 2 )(8✏ > 0)(9M 2 N)(8n M )|an a| + |bn b| < ✏ Now, we know from the Triangle Inequality, we have |an + bn (a + b)| = |an a + bn b|  |an a| + |bn b|. Therefore (8✏ > 0)(9M 2 N)(8n M )|an + bn (a + b)| < ✏ () an + bn ! a + b. 50 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE 3. lim (an bn ) = ab; We have (8✏a > 0)(9Na 2 N)(8n Na )|an a| < ✏a ^(8✏b > 0)(9Nb 2 N)(8n Nb )|bn b| < ✏b We note that |an bn ab| = |an bn abn + abn ab|  |an bn abn | + |abn ab| = |bn ||an a| + |a||bn b|, where the last step follows from the triangle inequality. We also know that if bn is convergent, then it is bounded, i.e. (9C 2 R)(8n 2 N)|bn |  C. Therefore, |an bn ab|  C|an a| + |a||bn b|. Therefore, setting M = max{Na , Nb }, we see that (8✏a > 0)(8✏b > 0)(9M 2 N)(8n M )|an bn ab| < C✏a + |a|✏b. We now choose 1 1 ✏a = ✏< ✏ 2C + 1 2C and 1 ✏b = ✏. 2|a| + d where d > 0 and 2|a|+d > 0 to ensure that 2|a|+d 6= 0 and ✏b > 0 () ✏ > 0. Therefore, 1 1 ✏ ✏ (8✏ > 0)(9M 2 N)(8n M )|an bn ab| < C ✏ + |a| ✏< + , 2C + 1 2|a| + d 2 2 and so (8✏ > 0)(9M 2 N)(8n M )|an bn ab| < ✏. 4.4. SEQUENCE ALGEBRA 51 4. lim (an /bn ) = a/b, provided b 6= 0. We just need to prove that ✓ ◆ 1 1 (8b 6= 0) bn ! b ) ! , bn b and then use 3. We assume that (8✏ > 0)(9Nb 2 N)(8n Nb )|bn b| < ✏. Now 1 1 |b bn | = bn b |b||bn | From the fact that bn ! b, we have (9N1 2 N)(8n N1 )|bn b| < c, where 0 < c < |b|. Now |bn b| < c ) |bn | > |b| c > 0. Therefore, 1 1 (8c 2 (0, |b|))(9N1 2 N) <. |bn | |b| c Also, from the fact that bn ! b we have (8✏ > 0)(9N2 2 N)(8n 6= N2 )|bn b| < |b|(|b| c)✏. By setting N = max{N1 , N2 }, we see that |b bn | 1 (8✏ > 0)(9N 2 N)(8n N) < (|b| c)✏ = ✏, |b||bn | |b| c and so 1 1 (8✏ > 0)(9N 2 N)(8n N) < ✏. bn b Theorem 3 (Sequence Squeeze Theorem). ((8n 2 N) an  xn  bn ) ^ an ! L ^ bn ! L ) xn ! L. 52 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE Proof. We know that (8✏ > 0)(9Na 2 N)(8n Na )|an L| < ✏ ^(8✏ > 0)(9Nb 2 N)(8n Nb )|bn L| < ✏ () (8✏ > 0)(9Na 2 N)(8n Na )L ✏ < an < L + ✏ ^(8✏ > 0)(9Nb 2 N)(8n Nb )L ✏ < bn < L + ✏ Setting N = max{Na , Nb }, and noting that (8n 2 N) an  xn  bn we see that (8✏ > 0)(9N 2 N)(8n N )L ✏ < an  x n  b n < L + ✏ )(8✏ > 0)(9N 2 N)(8n N )L ✏ < xn < L + ✏ () (8✏ > 0)(9N 2 N)(8n N )|xn L| < ✏ () xn ! L. Example 18. We can use the Sequence Squeeze Theorem to prove that 1 p ! 0. n3 + n+⇡ Proof. (8n 2 N)0  n3 +p1 n+⇡  n1 Define the sequences an = 0 and bn = n1. Now (8n 2 N)|an 0| = 0 ) an ! 0. The natural numbers are unbounded, so 8✏ > 0, we can pick N > 1✏. Now N > 1✏ () N1 < ✏. Hence, 8✏ > 0, we can pick N > 1✏ and 8n N , we have bn 0 = |bn 0| < ✏. Therefore, bn ! 0. Now, by applying Sequence Squeeze Theorem, we see that 1 p ! 0. n3 + n+⇡ 4.5 Sequences and Ordering The limiting process is also well-behaved with respect to the order operation. 4.5. SEQUENCES AND ORDERING 53 Theorem 4. Order Limit Theorem Assume lim an = a and lim bn = b. 1. ((8n 2 N)an 0) ) a 0. 2. ((8n 2 N)an  bn ) ) a  b. 3. ((9c 2 R)(8n 2 N)c  bn ) ) c  b. Similarly, (8n 2 N)an  c ) a  c. Proof. 1. We shall use proof by contradiction, and so we assume a < 0. We have the definition of convergence (8✏)(9N 2 N)(8n N )|an a| < ✏. Now we draw the real line with a < 0 and 0 2a a 0 |a| |a| When ✏ = |a|, the definition of convergence tells that the exists N|a| 2 N such that for all n N|a| , |an a| < |a|. From the above Figure, we can see that this means that for all N|a| , an < 0. This contradicts the assumption that (8n 2 N)an 0. Using symbols, we have (8✏)(9N 2 N)(8n N )|an a| < ✏ )(9N|a| 2 N)(8n N|a| )|an a| < ✏ )(9N|a| 2 N)(8n N|a| )an < 0. 54 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE Note that without the Figure, you might struggle with the last step. We can now see that we must have a 0. 4.6 The Monotone Convergence Theorem and Infinite Series Definition 20. A sequence (an ) is monotone increasing if (8n 2 N)an  an+1. A sequence (an ) is strictly monotone increasing if (8n 2 N)an an+1. A sequence is monotone if it is either increasing or decreasing. A sequence is strictly monotone if it is either strictly increasing or strictly decreasing. 1 Example 19. Show that the sequence an = n is strictly monotone increasing and converges to 0. Proof. (8n 2 N)an+1 = 1 n+1 > 1 n = an. Therefore (an ) strictly monotone increasing. 8✏ > 0 we can pick N 2 N such that N > 1 ✏ () 8✏ > 0 we can pick N 2 N such that N1 < ✏. Therefore, 1 (8✏ > 0)(9N 2 N) < ✏. n 1 So, we have proved that n ! 0. Theorem 5. Monotone Convergence Theorem If a sequence is monotone and bounded, then it converges. Proof. A monotone sequence is either monotone increasing or monotone de- creasing. 4.6. THE MONOTONE CONVERGENCE THEOREM AND INFINITE SERIES55 (a) We assume (an )n is monotone increasing and bounded. We exploit the boundedness of the sequence, which means it has a supre- mum, i.e. least upper bound, which we label as s: s = sup{an : n 2 N}. We draw a picture of monotone increasing and bounded sequence with supremum s. This picture guides the proof, but the proof we write down must be based on logic. s ✏ aN aN +1 s s+✏ R aN +2 Using the definition of a supremum, we know that for all ✏ > 0, s ✏ is not an upper bound of the sequence (an )n. Therefore, there exists N 2 N such that aN > s ✏. Symbolically, we have (9s 2 R)s = sup{an : n 2 N} ) (8✏ > 0)(9N 2 N)s ✏ < aN Now, we know that because (an )n is monotone increasing, for all n N , aN  an. We also know that an must be less than or equal to the supremum s, and so aN  an  s < s + ✏. Putting this all together, we have (an )n is a bounded and monotone increasing sequence ) (9s 2 R)s = sup{an : n 2 N} ) (8✏ > 0)(9N 2 N)s ✏ < aN , and (an )n is a bounded and monotone increasing sequence )(8✏ > 0)(9N 2 N)(8n N )s ✏ < an < s + ✏ () (8✏ > 0)(9N 2 N)(8n N )|an s| < ✏, which tell us that lim an = s. A monotone increasing and bounded se- quence converges to its supremum. 56 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE (b) We assume (an )n is monotone decreasing and bounded. We exploit the boundedness of the sequence, which means it has a infi- mum, i.e. greatest lower bound, which we label as b: b = inf{an : n 2 N}. 1 Using the definition of an infimum, we know that for all ✏ > 0, b + ✏ is not a lower bound of the sequence (an )n. Therefore, there exists N 2 N such that aN < b + ✏. Symbolically, we have (9b 2 R)b = inf{an : n 2 N} ) (8✏ > 0)(9N 2 N)aN < b + ✏. Now, we know that because (an )n is monotone decreasing, for all n N , an  aN. We also know that an must be greater than or equal to the infimum b, and so b  an  aN < b + ✏. We also know that b ✏ < b. Putting this all together, we have (an )n is a bounded and monotone decreasing sequence ) (9b 2 R)b = inf{an : n 2 N} ) (8✏ > 0)(9N 2 N)aN < b + ✏, and (an )n is a bounded and monotone decreasing sequence )(8✏ > 0)(9N 2 N)(8n N )b ✏ < an < b + ✏ () (8✏ > 0)(9N 2 N)(8n N )|an b| < ✏, which tell us that lim an = b. A monotone decreasing and bounded se- quence converges to its infimum. Definition 21. Partial Sums and Series The m’th partial sum of the sequence (bn ) is given by m X sm = bn , n=1 and the sequences of partial sums (sm ) is a series. P We say that the series 1 n=1Pbn converges to B if the sequence (sm ) converges to B. In this case, we write 1 n=1 bn = B. 4.6. THE MONOTONE CONVERGENCE THEOREM AND INFINITE SERIES57 P1 1 Example 20. Prove that the series n=1 n2 converges. Proof. Define the partial sum Xm 1 sm = n=1 n2 We can see that (8m 2 N)sm+1 > sm , and so (sm ) is strictly monotone increas- ing. If we Pcan show (sm ) is bounded, then the Monotone Convergence Theorem tells us 1 1 n=1 n 2 converges. We now prove that (sm ) is bounded above (It is obvious that (sm ) is bounded below by 1). 1 1 1 1 sm = 1 + + + +... + 2·2 3·3 4·4 m·m 1 1 1 1 N. Therefore, (8✏ > 0)(9M 2 N)(8n M )|a(m(n)) a| < ✏. Hence, amn ! a. Now suppose that for every m : N ! N such that m(n + 1) m(n), (8✏ > 0)(9N 2 N)(8n N )|a(m(n)) a| < ✏. 4.7. SUBSEQUENCES AND THE BOLZANO-WEIERSTRASS THEOREM 59 If this is true for every m : N ! N such that m(n + 1) m(n), we can just choose m(n) = n, so that (8✏ > 0)(9N 2 N)(8n N )|an a| < ✏. For bounded sequences, it turns out that it is always possible to find at least one such convergent subsequence. This result is known as the Bolzano-Weierstrass Theorem. We shall prove it in two stages. Firstly, we shall prove that every sequence contains a monotonic subsequence. Secondly, we just have to apply the Monotone Convergence Theorem. Lemma 8. Every sequence contains a monotone subsequence. To prove this lemma, we shall first define what is mean by the peak of a sequence. Definition 23. Peak am is a peak of the sequence (an ) if (8n > m)am an. Proof of Lemma ??. A sequence will either have a fixed number of peaks, say N 2 N or the number of peaks, like the natural numbers, will never end. If the number of peaks never ends, let ank be the k’th peak. Then for every k 2 N, we have ank ank+1. Hence, (ank ) is a monotone decreasing subsequence. Now, we consider the case where there are fixed numbers of peaks. Without loss of generality, ket aK be the final peak. Now, (8n K)an  aK. Define an1 = aK+1 and let an2 the the next term in the sequence which is greater than or equal to an1. Such a term must exist, because an1 is not a peak. Similarly, let an3 the the next term in the sequence which is greater than or equal to an2 , which must exist, because an2 is not a peak. Continuing in this way, we construct a monotone increasing subsequence. Theorem 6. Bolzano-Weierstrass Theorem Every bounded sequence contains a convergent subsequence. Proof. From Lemma ??, we know that every bounded sequence contains a bounded and monotone subsequence, which by the Monotone Convergence Theorem, must converge. 60 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE 4.8 The Cauchy Criterion This section is non-examinable. Definition 24. A sequence (an ) is called a Cauchy sequence if, (8✏ > 0)(9N 2 N)(8m, n N )|an am | < ✏. Theorem 7. Every convergent sequence is a Cauchy sequence. Proof. Assume (xn ) converges to x. We want to prove that (8✏ > 0)(9N 2 N)(8m, n N )|xn xm | < ✏. We know that (8✏ > 0)(9N 2 N)(8n N )|xn x| < ✏. Now we note that ✏ (8✏ > 0)(9N 2 N)(8n N )|xn x| < 2 ✏ ✏ )(8✏ > 0)(9N 2 N)(8n, m N )|xn x| < ^ |xm x| < 2 2 )(8✏ > 0)(9N 2 N)(8n, m N )|xn x| + |xm x| < ✏ Now, from the Triangle Inequality, |xn xm |  |xn x| + |xm x|. Hence, (8✏ > 0)(9N 2 N)(8n, m N )|xn xm | < ✏. Lemma 9. Cauchy sequences are bounded. 4.8. THE CAUCHY CRITERION 61 Proof. Suppose (xn ) is a Cauchy sequence, i.e. (8✏ > 0)(9N 2 N)(8n, m N )|xn xm | < ✏. Setting ✏ = 1, we obtain (9N 2 N)(8n, m N )|xn xm | < 1 We now set m = N , and so, (9N 2 N)(8n N )|xn xN | < 1 )(9N 2 N)(8n N )xN 1 < xn < xN + 1. Therefore, (8n 2 N)L  xn  U, where L = min({x1 ,... , xN 1 , xN 1}) U = max({x1 ,... , xN 1 , xN + 1}). Theorem 8. Cauchy Criterion A sequence converges if and only if it is a Cauchy sequence. (8✏ > 0)(9N 2 N)(8n N )|xn x| < ✏ () (8✏ > 0)(9N 2 N)(8n, m N )|xn xm | < ✏. Proof. We already know that if a sequence is convergent, then it is a Cauchy sequence. It remains to prove that if a sequence is a Cauchy sequence, then it converges. Suppose (xn ) is a Cauchy sequence. We know every Cauchy sequence is bounded, so by the Monotone Convergence Theorem, we see that every Cauchy sequence has a convergent subsequence, i.e. there is a subsequence of (xn ), de- noted by (xnk ) such that (9x 2 R) lim xnk = x. 62 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE We know that ✏ (8✏ > 0)(9N 2 N)(8n, m N )|xn xm | <. 2 and ✏ (8✏ > 0)(9M 2 N)(8nk M )|xnk x| <. 2 Therefore, by setting K = max(N, M ) we know ✏ ✏ (8✏ > 0)(9K 2 N)(8n, nk K)|xn xnk | < ^ |xnk x| < 2 2 (8✏ > 0)(9K 2 N)(8n, nk K)|xn xnk | + |xnk x| < ✏. From the Triangle Inequality, |xn x|  |xn xnk | + |xnk x|, and so (8✏ > 0)(9K 2 N)(8n K)|xn x| < ✏. 4.9 Exercises (a) (Calculating Square Roots). Let x1 = 2, and define ✓ ◆ 1 2 xn+1 = xn +. 2 xn i. Show that x2n is always greater than 2, and p then use this to prove that xn xn+1 0. Conclude that lim xn = 2. p ii. Modify the sequence (xn ) so that it converges to c. (b) Show that the constant sequence (a, a, a, a,...) converges to a. (c) Let xn 0 for all n 2 N. p i. If (xn ) ! 0, show that xn ! 0. p p ii. If (xn ) ! x, show that xn ! x. (d) Show that if xn  yn  zn for all n 2 N, and if lim xn = lim zn = l, then lim yn = l as well. (e) Show that limits, if they exist, must be unique. In other words, assume lim an = l1 and lim an = l2 , and prove that l1 = l2. 4.9. EXERCISES 63 (f) Suppose (an ) , (bn ) are two sequences of real numbers. Prove that if an ! a and bn ! b then an + bn ! a + b. (g) (Harmonic Series) Consider the so-called harmonic series X1 1 n=1 n and show that it does not converge. P (h) Prove that the series 1 p n=1 1/n converges if and only if p > 1. (i) Write computer code to investigate the convergence of q r q p p p 2, 2 + 2, 2 + 2 + 2,... Prove either convergence or non-convergence and if the series converges, find it limit. (j) Write computer code to investigate the convergence of q r q p p p 2, 2 2, 2 2 2,... Prove either convergence or non-convergence and if the series converges, find it limit. (k) Sketch the graphs of y = x and y = (x4 + 1) /3, and thereby illustrate the behaviour of the real sequence an where an+1 = (a4n + 1) /3. For which of the three starting cases a1 = 0, a1 = 1 and a1 = 2 does the sequence converge? Now prove your assertion. (l) The Fibonacci sequence (Fn ) is defined by F1 = F2 = 1 and Fn+1 = Fn + Fn 1 , n 2. i. Write R or Python code to generate the Fibonacci sequence. ii. Experiment with your code to investigate what happens to FFn+1n as n gets large. iii. Prove that FFn+1 n converges to a limit and find an expression for that limit. (m) The Padovan sequence (Pn ) is defined by P0 = P1 = P2 and Pn = Pn 2 + Pn 3 , n 3. 64 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE i. Write R or Python code to generate the Padovan sequence. ii. Experiment with your code to investigate what happens to PPn+1 n as n gets large. iii. Do you think PPn+1 n converges to a limit? If so, prove it and derive an expression for the limit. If you think PPn+1 n does not converge, prove it. (n) Let a1 > b1 > 0 and let an+1 = (an + bn ) /2, bn+1 = 2an bn / (an + bn ) for n > 1. Show that an > an+1 > bn+1 > bn and deduce that the two sequences converge to a common limit. What limit? (o) (Arithmetic-Geometric Mean) p i. Explain why xy  (x+y)/2 for any two positive real numbers x and y. (The geometric mean is always less than the arithmetic mean.) ii. Now let 0  x1  y1 and define p xn + yn xn+1 = xn yn and yn+1 =. 2 Show lim xn and lim yn both exist and are equal. (p) (Limit Superior). Let (an ) be a bounded sequence. i. Prove that the sequence defined by yn = sup {ak : k n} converges. ii. The limit superior of (an ), or lim sup an , is defined by lim sup an = lim yn where yn is the sequence from part (a) of this exercise. Provide a reasonable definition for lim inf an and briefly explain why it always exists for any bounded sequence. iii. Prove that lim inf an  lim sup an for every bounded sequence, and give an example of a sequence for which the inequality is strict. iv. Show that lim inf an = lim sup an if and only if lim an exists. In this case, all three share the same value. (q) For each series, find an explicit formula for the sequence of partial sums and determine if the series converges. P1 1 i. 2n Pn=1 1 1 ii. n=1 n(n+1) P1 n+1 iii. n=1 ln n 4.9. EXERCISES 65 (r) Assume (an ) is a bounded sequence with the property that every conver- gent subsequence of (an ) converges to the same limit a 2 R. Show that (an ) must converge to a. (s) Let (an ) and (bn ) be Cauchy sequences. Decide whether each of the fol- lowing sequences is a Cauchy sequence, justifying each conclusion. i. cn = |an bn | ii. cn = ( 1)n an iii. cn = [[an ]], where [[x]] refers to the greatest integer less than or equal to x. (t) (Cesaro Means) i. Show that if (xn ) is a convergent sequence, then the sequence given by the averages x1 + x2 + · · · + xn yn = n also converges to the same limit. ii. Give an example to show that it is possible for the sequence (yn ) of averages to converge even if (xn ) does not. 66 CHAPTER 4. SEQUENCES, SERIES, AND CONVERGENCE