Series and Sequences

Chapter 1 Series and sequences Throughout these notes we’ll keep running into Taylor series and Fourier se­ ries. It’s important to understand what is meant by convergence of series be­ fore getting to numerical analysis proper. These notes are sef-contained, but two good extra references for this chapter are Tao, Analysis I; and Dahlquist and Bjorck, Numerical methods. A sequence is a possibly infinite collection of numbers lined up in some order: a1 , a2 , a3 , . . . A series is a possibly infinite sum: a1 + a2 + a3 + . . . We’ll consider real numbers for the time being, but the generalization to complex numbers is a nice exercise which mostly consists in replacing each occurrence of an absolute value by a modulus. The questions we address in this chapter are: • What is the meaning of an infinite sum? • Is this meaning ever ambiguous? • How can we show convergence vs. divergence? • When can we use the usual rules for finite sums in the infinite case? 1 CHAPTER 1. SERIES AND SEQUENCES 1.1 Convergence vs. divergence We view infinite sums as limits of partial sums. Since partial sums are sequences, let us first review convergence of sequences. Definition 1. A sequence (aj )∞ j=0 is said to be f-close to a number b if there exists a number N ≥ 0 (it can be very large), such that for all n ≥ N , |aj − b| ≤ f. A sequence (aj )∞ j=0 is said to converge to b if it is f-close to b for all f > 0 (however small). We then write aj → b, or limj→∞ aj = b. If a sequence does not converge we say that it diverges. Unbounded sequences, i.e., sequences that contain arbitrarily large numbers, always di­ verge. (So we never say “converges to infinity”, although it’s fine to say “diverges to infinity”.) Examples: • e−n → 0 as n → ∞, and convergence is very fast. • n/(n + 2) → 1 as n → ∞, and convergence is rather slow. • (−1)n is bounded, but does not converge. • log(n) → ∞ as n → ∞, so the sequence diverges. For a proof that log(n) takes on arbitrarily large values, fix any large integer m. Does there exist an n such that log(n) ≥ m? Yes, it suffices to take n ≥ em . Definition 2. Consider a sequence (aj )∞ j=0 . We define the N -th partial sum SN as N N aj . SN = a0 + a1 + . . . + aN = j=0 o of partial sums SN We say that the series j aj converges if the sequence o converges to some number b as N → ∞. We then write ∞ j=0 aj = b. Again, if a series does not converge we say that it diverges. 2 1.1. CONVERGENCE VS. DIVERGENCE Example 1. Consider o∞ j=0 2−j , i.e., 1 1 1 + + + .... 2 4 8 This series converges to the limit 2. To prove this, consider the partial sum 1+ SN = N N 2−j . j=0 Let us show by induction that SN = 2 − 2−N . The base case N = 0 is true since 2−0 = 2 − 2−0 . For the induction case, assume SN = 2 − 2−N . We then write SN +1 = SN + 2−(N +1) = (2 − 2−N ) + 2−(N +1) = 2 − 2−(N +1) , the desired conclusion. Example 2. The previous example was the x = 1/2 special case of the socalled geometric series 1 + x + x2 + x3 + . . . WIth a similar argument, we obtain the limit as ∞ N xj = j=0 1 , 1−x provided the condition |x| < 1 holds. This expression can also be seen as the Taylor expansion of 1/(1−x), centered at zero, and with radius of convergence 1. Example 3. Consider the so-called harmonic series 1 1 1 + + + .... 2 3 4 This series diverges. To see this, let us show that the N partial sum is comparable to log(N ). We use the integral test 1+ SN = N N 1 j=1 j N +1 ≥ 1 1 dx. x (Insert picture here) The latter integral is log(N +1), which diverges as a sequence. The partial sums, which are larger, must therefore also diverge. 3 CHAPTER 1. SERIES AND SEQUENCES Example 4. Consider ∞ N 1 , nq j=1 for some q > 0. As a function of q, this is the Riemann zeta function ζ(q). (A fascinating object for number theorists.) We’ve seen above that q = 1 leads to divergence. A similar integral test would show that the series converges when q > 1, while it diverges when q ≤ 1. We now switch to a finer understanding of convergence: certain series are absolutely convergent, while others are conditionally convergent. This will affect what type of algebraic manipulations can be done on them. o o∞ Definition 3. A series ∞ j=0 aj is said to be absolutely convergent if j=0 |aj | converges. If a series is not absolutely convergent, but nevertheless converges, we say that it is conditionally convergent. The subtlety with conditional convergence is that alternating plus and minus signs may lead to convergence because of cancelations when summing consecutive terms. Example 5. Consider 1− 1 1 1 1 1 + − + − + .... 2 3 4 5 6 This series is not absolutely convergent, because it reduces to the harmonic series when absolute values of the terms are taken. It is nevertheless con­ vergent, hence conditionally convergent, as the following argument shows. Assume N is even, and let SN = N N (−1)j j=1 j . Terms can be grouped 2-by-2 to obtain, for j ≥ 1, 1 1 1 − = . j j+1 j(j + 1) 4 1.1. CONVERGENCE VS. DIVERGENCE A fortiori, 1 j(j+1) ≤ 1 , j2 so SN ≤ N −1 N 1 , 2 j j=1,3,5,... which we know converges. If on the other hand N is odd, then SN = SN −1 + 1 . Both terms SN and 1/(N + 1) are converging sequences, so their sum N +1 converges as well. This proves convergence. Note that the series converges to 1− 1 1 1 1 1 + − + − + . . . = log(2). 2 3 4 5 6 This is the special case x = 1 in the Taylor expansion of log(1 + x) about x = 0. In passing, without proof, here is a useful test to check convergence of alternating series. Theorem 1. (Alternating series test) Consider the series ∞ N (−1)j aj , j=0 where aj > 0. If (aj ) converges to zero (as a sequence), then the series is convergent. The main problem with conditionally convergent series is that if the terms are rearranged, then the series may converge to a different limit. The “safe zone” for handling infinite sums as if they were finite is when convergence is absolute. Theorem 2. Let f : Z+ → Z+ be a bijection, o i.e., f is a rearrangement of the nonnegative integers. Consider a series ∞ j=0 aj . If this series is absolutely convergent, then ∞ ∞ N N af (j) . aj = j=0 j=0 Here is what usually happens when the assumption of absolute conver­ gence is not satisfied. 5 CHAPTER 1. SERIES AND SEQUENCES Example 6. Consider again 1 1 1 1 − + − + ... 3 4 5 6 which as we have seen equals log(2) − (1 − 1/2) = log(2) − 1/2 = .193147 . . .. We can rearrange the terms of the series by assigning two negative terms for each positive term: 1 1 1 1 1 1 1 − − + − − + + ... 3 4 6 5 8 10 7 This series is also convergent, but happens to converge to (log(2) − 1)/2 = −.153426 . . .. Other operations that can be safely performed on absolutely convergent series are passing absolute values inside the sum, and exchanging sums. Again, complications arise if the series is only conditionally convergent. (See Tao, Analysis I, for counter-examples.) Theorem 3. The following operations are legitimate for absolutely conver­ gent series. • Passing absolute values inside sums: | ∞ N aj | ≤ j=0 ∞ N |aj |. j=0 • Swapping sums: ∞ N ∞ N j=0 k=0 aj,k = ∞ N ∞ N aj,k k=0 j=0 Note in passing that the same is true for integrals of unbounded integrands or integrals over unbounded domains: they need to be absolutely convergent (integrability of the absolute value of the function) for the integral swap to be legitimate. This is the content of Fubini’s theorem. Again, there are striking counter-examples when the integrals are not absolutely convergent and the swap doesn’t work (See Tao, Analysis I). 6 1.2. THE BIG-O NOTATION 1.2 The big-O notation Here are a few useful pieces of notation for comparing growth or decay of sequences, used extensively by numerical analysts. They are called the bigO, little-o, and big-Theta notations. Big-O is used much more often than the other two. They occur when comparing decay rates of truncation errors, and runtimes of algorithms. Definition 4. Consider two nonzero sequences fn and gn for n = 0, 1, 2, . . .. We write fn = O(gn ) when there exists C > 0 such that |fn | ≤ C|gn |. We write fn = o(gn ) when fn /gn → 0 as n → ∞. We write fn = Θ(gn ) when fn = O(gn ) and gn = O(fn ). Examples: • fn = n2 and gn = n3 : we have n2 = O(n3 ) and n2 = o(n3 ) but n2 = Θ(n3 ). n • fn = n+2 and gn = fn = o(gn ). n : n−3 we have fn = O(gn ) and fn = Θ(gn ), but • Exponentials always dominate polynomials: na = o(ebn ) whatever a > 0 and b > 0. • Conversely, e−bn = o(n−a ). Out loud, we can read the expression fn = O(gn ) as “fn in on the order of gn ”. The same notations can be used to compare sequences indexed by a pa­ rameter that goes to zero, such as (typically) the grid spacing h. The defini­ tion above is simply adapted by letting h → 0 rather than n → ∞. Examples: • f (h) = h2 and g(h) = h3 : this time we have g(h) = O(f (h)) and g(h) = o(f (h)) when the limit of interest is h → 0. • Powers of h don’t converge to zero nearly as fast as this exponential: ea/h = o(hb ) whatever a > 0 and b > 0. SImilarly, we may wish to compare functions f and g of a continuous variable x as either x → ∞ or x → 0; the definition is again modified in the obvious way. Whenever a O(·) or o(·) is written, some underlying limit is understood. 7