Lecture 20 Asymptotics

Lecture 20: Asymptotics 24 October 2011 1 Introduction As we have seen, whether or not a series converges does not depend on the detailed behavior of the terms, but only on their general rate of decay. We have frequently made use of informal reasoning about the general shape of terms of a series to make an initial conjecture about whether it converges or not. Establishing the truth of these conjectures was usually done by the comparison test, or some other test. In this lecture, we consider some methods to make this type of reasoning precise. This sort of analysis is usually called asymptotics. The goal is to take some series, and “simplify” it by devising another series that is different, but has the same sort of long-term behavior. This is called asymptotic simplification. This is useful because asymptotic simplification, while it may significantly alter the series, does not alter whether or not it converges; this makes it a convenient way to study the convergence or divergence of complicated series. There are two main bits of notation when studying asymptotics: we will denote by an ∼ bn the statement that “an resembles bn eventually,” and we will denote by an  bn the statement that “an grows more slowly than bn eventually.” These will be given precise definitions in section 3. Intuitively, you should think of ∼ as corresponding to an asymptotic version of =, and  as corresponding to an asymptotic version of <.1 One of the main benefits of studying asymptotics is that it develops the habit of always having a “back of the envelope” understanding of functions under consideration. In the real world, you will frequently not need (or have the time to) actually do careful computations; what is most important is having a general sense for shape. The reading for today is the handout titled “Asymptotics,” listed under “Reading for the course.” The homework is problem set 19 (which includes weekly problems 18 and 19) and a topic outline. You should begin working on weekly problems 23 and 24. Due to the midterm tomorrow evening, the homework assigned today is not due until Friday. Note that the homework assigned on Wednesday will also be due on Friday as originally planned. 2 Examples of asymptotic simplification Here are some examples from recent homework assignments, illustrating the sort of simplification that we wish to be able to do. The purpose of these examples is to illustrate the ways in which we want to be able to use the symbols ∼ and . In particular, an  bn should mean that an can safely be neglected compared to bn , and an ∼ bn should mean that an and bn can safely be taken interchangeably when considering long-term behavior. These examples should fairly intuitively illustrate the sort of thing that these symbols should mean. The next section will give precise definitions that will justify this reasoning. 1 The symbol  is also sometimes used informally to mean “much less than,” but for our purposed it will mean “asymptotically less than.” 1 Example 2.1 (PSet 16, problem 4(c)). Consider the series ∞ X k=1 1 . Since k  5, we can safely neglect the k+5 5 term. 1 1 ∼ k+5 k Thus since the harmonic series diverges, this series should diverge as well. Note that in this case, the direct P∞ 1 , although the asymptotic comparison test worked well. It would have worked less well, though, for k=6 k−5 comparison test works just as well on this series as on the given series. ∞ X 2k + 1 Example 2.2 (PSet 16, problem 1(e) and PSet 17, problem 2(i)). Consider the series . Since 3k + 1 k=2 2k  1 and 3k  1, to study the long-term behavior, we can safely ignore the 1 terms. 2k 2k + 1 ∼ k k 3 +1 3 P 2k Now, is a geometric series with ratio less than 1, so it converges. Thus we expect the original series 3k to converge as well (indeed, it does, as the asymptotic comparison test will show). Note that it is not true k k ≤ 23k , so we can’t quite apply the comparison test in the most naive way; asymptotic comparison that 23k +1 +1 helps a lot here. ∞ X 2k + 1 Example 2.3 (PSet 18, problem 2(b)). Consider the series . Since 2k  1, this simplifies as follows. k 3/2 k=1 2k + 1 2k 2 ∼ 3/2 = 1/2 3/2 k k k Since this is a p-series with p < 1, it diverges. So we expect the given series to diverge as well (again, the asymptotic comparison test will show that it diverges). ∞ X 5 Example 2.4 (PSet 18, problem 2(c)). Consider the series . Since 4k  1, this simplifies as k 4 +7 k=10 follows. 4k Now, a geometric series with common ratio the given series converges. 3 1 4 5 5 ∼ k +7 4 converges. The asymptotic comparison test will show that Definition of ∼ and  The definition of the notation an ∼ bn is designed to mean that an ≈ bn for large n, where the fit gets better and better as n gets larger. Another way to say this is that abnn ≈ 1, where the approximation gets better and better as n gets larger. Fortunately, this last statement is something that we have a mathematical description of: the notion of a limit. We use it to make the definition. Definition 3.1. The notation an ∼ bn means that lim n→∞ are asymptotic. an = 1. In this case, we shall say that an and bn bn Similarly, we want the notation an  bn to mean, roughly, that an can be neglected compared to bn , as n becomes large. One way to say this is that the ratio abnn should be very close to 0 for large n, and get closer and closer as n grows to infinity. This, again, can be formalized using the language of limits. 2 Definition 3.2. The notation an  bn means that lim n→∞ faster than an . an = 0. In this case, we shall say that bn grows bn Observe that there is another way to thinking of the notation . It should mean that we are allowed to neglect an when compared with bn . In fact, it is not hard to show that the following is true (and could be used as a definition of  if desired). Fact. For two sequences an and bn , bn grows faster than an if and only if an + bn is asymptotic to bn . In symbols, an  bn if and only if an + bn ∼ bn . 4 Asymptotic comparison of some common functions In order to do asymptotic simplification, we need to understand which functions grow faster than others. This section summarizes some main facts about various families of functions. Note that in this section, I will be considering asymptotics of functions f (x) rather than sequences an . The definitions are the same, as are the sorts of arguments. First consider polynomials. Any polynomial is asymptotic to its leading term, as in the following examples. x2 + x + 1 ∼ x2 2 5x + 1000x + 1 ∼ 5x3 x+7 ∼ x 3 This works because for any two exponent p1 , p2 , we have xp1  xp2 if and only if p1 < p2 . So terms with smaller exponents can safely be ignored. Next, consider exponential functions. Observe that ex grows faster than any polynomial. This can be seen by consider the Taylor series of x, by by applying l’Hôpital’s rule repeatedly, as in the following example. x2 + 2x + 3 x→∞ ex 2x + 2x ex 2 = lim x x→∞ e = 0 = lim lim x→∞ This computation, which applies l’Hôpital’s rule twice in a row, shows that x2 + 3x + 3  ex . In fact, the same technique will work to show that any polynomial grows less quickly than ex . What about comparing different exponential functions, say comparing ex to 2x ? In this case, the limit as x → ∞ of 2x /ex = (2/e)x is 0, since 2 < e. This shows that 2x  ex . The same sort of reasoning shows that ax  bx if and only if a < b. What about logarithms? In fact, logarithms grow more slowly than any polynomial. This, again, can be seen using l’Hôpital’s rule. For example: lim x→∞ ln x +1 x2 1/x 2x 1 = lim x→∞ 2x2 = 0 = lim x→∞ It follows from this that ln x  x2 + 1. The same sort of argument would show that ln x  p(x) for any polynomial p(x). To illustrate how to use facts like these, consider the following example. 3 x 2 +x 2  ex and ln x  x2 , we can safely neglect Example 4.1. Consider the function f (x) = lne x+x 2 . Because x 2 the x in the numerator and the ln x in the denominator. Therefore we obtain the following asymptotic simplification. ex ex + x2 ∼ 2. 2 ln x + x x This is a simplification, since this new function is somewhat easier to study. 5 The asymptotic comparison test The main benefit of asymptotic analysis and asymptotic simplification, for our purposes, is that it makes convergence questions much easier to study. Two asymptotic sequences have the same convergence properties. This is expressed in the following. Theorem 5.1 (Asymptotic comparison test). Suppose that ∞ X an and n=1 ∞ X bn are two series such that n=1 an ∼ bn and such that all terms bn are nonnegative2 . Then either both series converge or both series diverge. The restriction that bn ≥ 0 is necessary because, behind the scenes, the asymptotic comparison test invokes the direct comparison test. Notice that the asymptotic comparison test is, in some sense, just a restatement of the limit comparison test stated several lectures ago. There are a couple other, similar, statements that are sometimes included in the asymptotic comparison tests, which may sometimes be useful. These are stated below. • If an  bn , all bn ≥ 0, and ∞ X bn converges, then ∞ X an converges as well. n=1 n=1 • If an  bn , all an ≥ 0, and ∞ X an diverges, then ∞ X bn diverges as well. n=1 n=1 All three of these statements are essentially just souped-up versions of the direct comparison test. 6 Examples Here are some examples of asymptotic simplification and asymptotic comparison in action. ∞ X (n2 + 1)(3n3 + n) Example 6.1. Does the series converge? (n2 + 1)2 (7n3 + n2 ) n=1 First, asymptotically simplify the numerator and the denominator. (n2 + 1)(3n3 + n) ∼ (n2 + 1)2 (7n3 + n2 ) ∼ n2 · 3n3 = 3n5 (n2 )2 · 7n3 = 7n7 From this it follows that 3n5 3 1 (n2 + 1)(3n3 + n) ∼ 7 = · 2 2 2 3 2 (n + 1) (7n + n ) 7n 7 n P 1 Now, since n2 is a p-series with p > 1, it converges. So in fact the series in question converges, by the asymptotic comparison test. 2 Actually, it suffices to only consider terms bn for n sufficiently large. 4 Example 6.2. Does the series e−n +n n=1 e−n +n2 P∞ converge or diverge? Again, we can asymptotically simplify this. Using the fact that e−x  n and e−x  n2 , the following holds. e−n + n n 1 ∼ 2 = −n 2 e +n n n Since the harmonic series diverges, this series also diverges by the asymptotic comparison test. Note. Do not confuse e−n with en . While en grows faster than any polynomial, e−n goes to 0 as n → ∞. In particular, it grows more slowly than any function that does not go to 0 as n goes to infinity. 5