Problems on Sums and Integrals

PROBLEMS ON SUMS AND INTEGRALS Contents 1 Swapping sums 1.1 Finite sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Absolute and conditional convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 2 Riemann integral 2.1 Compactness and improper integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Mesh sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Discretization and inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 5 5 3 Lebesgue integrals 3.1 Advantages of Lebesgue integrals . . . . . . 3.2 Riemann integrals and Lebesgue integrals . 3.3 Swapping double integrals . . . . . . . . . . 3.4 Interchanging limits and Lebesgue integrals 5 5 6 6 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Techniques for introducing more sums 7 4.1 Taylor series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.2 Eliminating fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3 Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1 1.1 Swapping sums Finite sums Here is an example that many of you might already know from high school math contests. Example 1. Let n be a positive integer. Prove that jnk 1 X ϕ(k) = n(n + 1). k 2 k≥1 Proof. The key idea is to rewrite the floor as a sum involving divisors: jnk X X X XX ϕ(k). ϕ(k) = ϕ(k) 1= k k≥1 k≥1 k|m k≤n k≥1 k|m m≤n Thus we’re computing the sum of ϕ(k) over several pairs of integers (k, m) for which k | m, m ≤ n. For example, if n = 6, the possible pairs (k, m) are given be the following table:   (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6)        (2, 2) (2, 4) (2, 6)        (3, 3) (3, 6) (k, m) ∈ (4, 4)           (5, 5)     (6, 6) Nominally, we’re supposed to be summing by the rows of this table (i.e. fix k and run the sum over corresponding m). However, by interchanging the order of summation we can instead consider this as a sum over the rows: if we instead pick the value of m first, we see that XX P d|n ϕ(d) ϕ(k). m=1 k|m k≥1 k|m m≤n Using the famous fact n X X ϕ(k) = = n, we conclude n X X ϕ(k) = m=1 k|m n X m=1 1 m = n(n + 1). 2 Here P one has the idea that one can “swap Pthe order of summation”: even though there is a single initially, by rewriting it as a double and then swapping the order, we are able to solve the problem. The goal of this lecture is to try and push this idea to allow us to do similar calculations over both infinite sums and integrals. Because of the introduction of infinity, things become a little more complicated and some more care is necessary. So, in the first part of the lecture we will address conditions on which rearranging the order of summation or integration is permissible. After that we will see several applications. 1.2 Let Absolute and conditional convergence P n an be an infinite series of complex numbers; then its limit is defined as X n an := lim N →∞ N X ! an . n=1 Note that this depends on the order of the terms: if we permute the sequence, the limit might change! This is weird and bad since we would want “infinite addition” to be commutative, so we want a way to avoid this behavior. This is accomplished by using the so-called notion of absolute convergence. P P Definition 2. If ak converges, we say it converges absolutely if |ak | < ∞, and converges conditionally otherwise. P Theorem 3 (Rearrangement okay iff absolutely convergent). Let an be a convergent series of complex numbers. P (a) If an is absolutely convergent, it is invariant under permutation of the terms (the sum will still converge, and the limit remains the same). P (b) If an is conditionally convergent and an are real numbers, then there exists a permutation of the terms for which the sum converges to 2018. Thus, any time befP ore you try to rearrange the series, you must check first that it’s absolutely convergent. With two signs the statement reads: Theorem 4 (Fubini for doubly-indexed infinite sums). Let am,n ∈ C. If any of the three quantities ! ! X X X X X |am,n | |am,n | , |am,n |, m (m,n)∈N2 n n m are convergent, then ! ! X am,n = X X m (m,n)∈N2 am,n = n X X n am,n m and all three series are convergent. Corollary 5 (Tonelli for doubly-indexed infinite sums). Let am,n ∈ R≥0 . Then ! ! X X X X X am,n am,n = am,n = m (m,n)∈N2 n n m where we allow the possibility all three diverge. Here is the classic example. Example 6 (Putnam 2016 B6). Evaluate ∞ ∞ X (−1)k−1 X k k=1 n=0 1 . +1 k2n Proof. Before anything else, the sum is absolutely convergent since we have X k≥1 n≥0 X X 1 π2 1 −2 < k = · 2 < ∞. k(k · 2n + 1) 2n 6 n≥0 k≥1 Thus we may swap the order of summation freely. We use d = k · 2n + 1 ≥ 2 as the summation variable, so that the sum in question is X1 d≥2 d X k ∃n:d−1=k·2n Now we claim that the inner sum is exactly is 1 d−1 . (−1)k−1 . k Indeed, if d − 1 = 2r m with m odd, then the sum   r (−1)m−1 (−1)2m−1 (−1)2 m−1 1 1 1 1 + + ··· + = − − ··· − r m 2m 2r m m 1 2 2 1 = r 2 m 1 = . d−1 Consequently, the final answer is X d≥2 X 1 = d(d − 1) d≥2  1 1 − d−1 d  = 1. 2 Riemann integral So far all of this is fair-game on high school. We’ll now move into the realm of calculus. Definition 7. A tagged partition P of [a, b] consists of a partition of [a, b] into n intervals, with a point ξi in the nth interval, denoted a ≤ x0 < x1 < x2 < · · · < xn ≤ b ξi ∈ [xi−1 , xi ] ∀ 1 ≤ i ≤ n. and The mesh of P is the width of the longest interval, i.e. maxi (xi − xi−1 ). Theorem 8 (Riemann integral). Let f : [a, b] → C be continuous. Then the definition ! Z b n X f (ξi )(xi − xi−1 ) f (x) dx = lim P tagged partition mesh P →0 a i=1 is well-defined (and finite). There are a bunch of remarks I want to make about this result. 2.1 Compactness and improper integrals We won’t prove the definition of the Riemann integral works out, but we will mention that its proof hinges crucially on: Fact 9. The interval [a, b] is compact, so continuous functions f : [a, b] → C behave well. In particular, f is bounded, and “uniformly continuous”. √ This fact is false for open (or unbounded) intervals: consider the function 1/ x on (0, 1), for example. This gives rise to the notion of “improper integrals”, such as Z 1 1 √ dx. x 0 As written, this does not officially make sense as a Riemann integral, since f (x) = function on [0, 1]. Rather, we implicitly mean 1 Z lim ε→0+ ε √1 x is not a 1 √ dx x since R 1 −1f (x) is well-defined on [ε, 1]. In this case, there is no guarantee the limit exists; for example dx = ∞. 0 x Similarly, it’s possible to set endpoints at ∞ by e.g. Z ∞ Z f (x) := lim −∞ for example. B B→∞ −B f (x) 2.2 Mesh sums Sometimes, you will find that a sum can be written in such a way that it corresponds to the mesh of a Riemann integral. In that case, one is very happy, because then it turns the entire sum into a single integral! Example 10. Evaluate   1 1 1 + + ··· + n+1 n+2 2n lim n→∞ . Proof. Write as n lim n→∞ Then, this is a mesh sum for f (x) = log 2. 2.3 1 1+x 1X 1 n 1+ k=1 ! k n . over [0, 1]. Thus by definition it approaches R1 1 0 1+x dx = Discretization and inequalities If asked to prove an identity or inequality about integrals, it is often possible to revert back to a discrete sum, a technique called discretization. For example, suppose one wishes to prove the Cauchy-Schwarz inequality in the form Z 2 b b Z 2 ≤ f (x)g(x) dx b  Z 2 f (x) dx a  g(x) dx a a for continuous functions f, g : [a, b] → R. By taking meshes, it is sufficient to prove 1X f (ai )g(ai ) dx n !2 ≤ i 1X f (ai )2 dx n i ! ! 1X 2 g(ai ) dx . n i which is of course just the classical Cauchy-Schwarz from high school. In practice, aside from discretization, most integral inequalities on competitions will really just use the following fact: Lemma 11 (The obvious inequality). Let f, g : [a, b] → R be continuous functions. If f (x) ≤ g(x) for all x ∈ [a, b] then Z b Z b f (x) dx ≤ g(x) dx. a 3 3.1 a Lebesgue integrals Advantages of Lebesgue integrals Unfortunately, Riemann integrals are terrible. In order to properly state theorems about interchanging order of summation, it’ll be Rmuch more convenient to proceed with the LebR esgue integral, b which I will generally denote by X to distinguish it from the Riemann integral a . Defining the Lebesgue integral is much more involved, because it involves a bunch of measure theory, so I won’t define what it is (but those of you taking 18.175 will find out really soon). However, I’ll at least mention the following reasons it’s appreciated. • Better theorems P about R b swapping R b P limits and sums. For example, for the Riemann integral, swapping n a fn and a n fn requires uniform convergence, which is a pretty strong condition (although it’ll be true for Taylor series, which is a frequent use case for us). R R • Improper integrals can be handled natively. You can write (0,1) √1x dx and R exp(−x2 ) dx and it makes sense, unlike for the Riemann case where one has to use an improper integral. • More versatile. Although we won’t encounter any, some functions thatRwere previously not Riemann integrable can now be assigned values. The classic example is [0,1] 1Q = 0. 3.2 Riemann integrals and Lebesgue integrals Of course, it’d be really silly if there wasn’t some guarantee that the Riemann integrals and Lebesgue integrals agree. The rules for converting a Riemann and Lebesgue integral are as follows: • For continuous functions f : [a, b] → C, the Riemann integral and Lebesgue integrals coincide. So proper Riemann integrals work out of the box. • For continuous nonnegative functions f : (a, b) → R≥0 on an open (or half-open) interval where one needs improper integrals, the improper Riemann integral and Lebesgue integrals coincide (where we allow the possibility that the integrals are both +∞). Here, a = −∞ and b = +∞ are allowed too. Rd • For general f : (a, b) → C, if the partial integrals c |f | dx are bounded for any [c, d] ⊂ (a, b) then we can also swap as above. On the other hand, if your signs are all over the place, then there isn’t hope in general R ∞ sin xof converting improper Riemann integrals to Lebesgue ones. A famous textbook example is 0 x dx which in fact is not covered by Lebesgue integration. 3.3 Swapping double integrals I’ll state this in the full generality, though we’ll only use it in the cases where the “σ-finite measure spaces” are N (corresponding to infinite sums) or sub-intervals of R (corresponding to Riemann integrals). Theorem 12 (Fubini). Let X and Y be “σ-finit R eR measure spac
es”. LRet fR : X × Y →
C be cRontinuous (or just “measurable”). If any of X Y |f (x, y)| dy dx, Y X |f (x, y)| dx dy, X×Y |f (x, y)| d(x, y) are finite, then we have Z Z  f (x, y) dy X Y Z Z  dx = f (x, y) dx Y X Z dy = f (x, y) d(x, y). X×Y Corollary 13 (Tonelli). Let X and Y be “σ-finite measure spaces”. Let f : X × Y → R≥0 be continuous (or just “measurable”) and nonnegative. Then   Z Z Z Z Z f (x, y) dy dx = f (x, y) dx dy = f (x, y) d(x, y) X Y Y X where we allow the possibility that all three are +∞. X×Y • If X = N and Y = N, then this corresponds to the double sums we stated earlier. RP PR • If X = N and Y ⊂ R is an interval, then this states that and can be swapped. Remark 14. • Note that if X and Y are finite closed intervals and f : X × Y → C is continuous, then hypotheses of Fubini are automatically satisfied, since X ×Y is compact. The situation where X and Y are open/infinite is more slippery, although in most cases we’ll have nonnegativity and then Tonelli will save us. Tonelli’s theorem (together with the result that even improper Riemann integrals are okay with nonnegative functions) means that whenever you have nonnegative functions, you can proceed no holds barred — everything works beautifully. In other words nonnegative =⇒ euphoria. 3.4 Interchanging limits and Lebesgue integrals You can read this off of the results on sums, but we’ll state them here since they have names. Theorem 15 (Dominated convergence theorem). Let fn : I → C be a seqRuence of continuous functions on an interval I ⊆ R. Assume that |fn (x)| ≤ g(x) for all x, where I g(x) < ∞ (i.e. g is integrable). Then limn fn (x) is integrable and Z Z lim fn (x) dx = lim fn (x) dx. n→∞ I I n→∞ Theorem 16 (Monotone convergence theorem). Suppose that fn : I → R≥0 is a sequence of continuous functions on an interval I ⊆ R which are also nonnegative. Assume further that fn (x) ≤ fn+1 (x) for n ∈ N, x ∈ I. Then Z Z lim fn (x) dx lim fn (x) dx = I n→∞ n→∞ I where the value of any of these integrals is allowed to be infinite. 4 4.1 Techniques for introducing more sums Taylor series Some common ones: exp(x) = X xn n≥0 log(1 − x) = − n! =1+x+ X xn n≥1 n = −x − x2 x3 + + ... 2! 3! ∀x∈R x2 x3 − − ... 2 3 ∀ |x| < 1 X 1 = xn = 1 + x + x2 + . . . 1−x ∀ |x| < 1 n≥0 arctan(x) = X (−1)n x2n+1 n≥0 2n + 1 =x− x3 x5 + − ... 3 5 There is a nice theorem about Taylor series in general: ∀ |x| < 1. Theorem 17 (Convergence of Taylor series). Let f be an analytic function. Within its radius of convergence, the Taylor series for f will • converge absolutely for any x as a series of complex numbers, and • converge uniformly on any compact sub-interval, as a series of functions (i.e. it is compactly convergent). I mention uniform convergence here since it’s actually strong enough to allow swapping integration even for the Riemann integral. Here’s the definition: Definition 18. A sequence of functions Fn : [a, b] → C is said to converge uniformly to the function F : [a, b] → C if lim sup |Fn (x) − F (x)| = 0. n→∞ x∈[a,b] A series P n fn converges uniformly if its partial sums Fn = Pn k=1 fk do. But we’ll be mostly using Lebesgue integrals anyways. So, whenever you have an analytic function on a closed interval, all the summation results work fine! Here is a very famous example. Example 19. Compute Z 1 log x log(1 − x) dx. 0 There is some subtlety here since this integral looks like it might be improper! Fortunately, it’s not quite, since limx→0+ log(x) log(1 − x) = 0, and in this way we can actually regarding log(x) log(1 − x) as a proper integral on [0, 1]. Proof. Switch to Lebesgue integration. The integral is then Z X xn I=− log x dx n [0,1] n≥1 X1Z 1 =− xn log x dx n 0 n≥1 x=1 X1 n+1 (n + 1) log x − 1 =− x · (integration by parts) n (n + 1)2 x=0 n≥1 x=1 X1 n+1 (n + 1) log x − 1 =− x · n (n + 1)2 x=0 n≥1 X 1 = n(n + 1)2 n≥1  X1 1 1 = − − . n n + 1 (n + 1)2 (by Tonelli) n≥1 The N th partial sum of this is equal to 1 − 1 N +1 − PN 1 n=1 (n+1)2 which gives 2 − π2 6 as N → ∞. Remark 20 (An application of Feynman’s trick). In my original notes, I had obtained the identity R1 n 1 0 x log x dx = − (n+1)2 using integration by parts. In class it was pointed out that Feynman’s trick, more descriptively called “differentiating under the integral sign”, gives a shorter way to prove this. Start by writing Z 1 1 xn dx = n + 1 0 and then treat n ∈ R as a parameter. This allows one to differentiate both sides with respect to n, yielding Z 1 d n d 1 x dx = dn n + 1 0 dn Z 1 1 xn log x dx = − . =⇒ (n + 1)2 0 See http://www.math.uconn.edu/~kconrad/blurbs/analysis/diffunderint.pdf for more details on this trick. 4.2 Eliminating fractions The following seemingly obvious statement is surprisingly useful. Lemma 21 (Denominator → integral). For any real number s > −1 we have Z 1 = ts ds. s+1 (0,1) P n As a simple use case, let’s suppose we were given n xn for some |x| < 1 and wanted to figure out what function it was (without knowing anything about log in advance). We can write X xn X Z tn−1 dt = xn n [0,1] n n XZ = x(xt)n−1 dt Zn = [0,1] X x(xt)n−1 dt [0,1] n Z = [0,1] x dt 1 − xt = [− log(1 − xt)]1t=0 = [− log(1 − xt)]1t=0 = − log(1 − x). Let’s also see a solution to the earlier double sum. Example 22 (Putnam 2016 B6). Evaluate ∞ ∞ X (−1)k−1 X k=1 k n=0 1 . +1 k2n Proof. Check conditional convergence of the double sum in the same way as before. Thus we apply Fubini freely: ∞ ∞ X (−1)k−1 X k=1 k ∞ ∞ Z X 1 (−1)k−1 X n tk2 dt = n k2 + 1 k n=0 n=0 [0,1] k=1 ! Z n ∞ X ∞ X (−t2 )k = − dt k [0,1] n=0 k=1 Z Z ∞ X n log = log(1 + t2 ) dt = [0,1] n=0 [0,1]  Z = log [0,1] 4.3 1 1−t  ∞ Y ! 2n (1 + t ) dt n=0 Z − log(1 − t) dt = 1. dt = [0,1] Fourier series If f : R → C is continuous with period 1, then f (x) = lim N →∞ The Fourier coefficients am are given by Z am = N X am exp(2πimx). m=−N 1 f (x) exp(−2πimx) dx. 0 We again have convergence results: Theorem 23. Let f : [0, 1] → C be periodic. (a) The Fourier series converges uniformly provided f is continuously differentiable (this can be weakened to “absolutely continuous”, but we won’t need that level of generality). P (b) The Fourier series converges absolutely as long as m∈Z |am | < ∞. Example 24. If f : R → C is continuously differentiable with period 1, and α is an irrational number, then Z 1 f (α) + · · · + f (nα) = f (x) dx. lim n→∞ n 0 P Proof. Just write f (x) = m am exp(2πimx). Then note that for m 6= 0, if we let z = exp(2πimα) then z1 + z2 + · · · + zn z(1 − z n ) = →0 n n(1 − z) as long 6 1, which holds since z is not a root of unity. This leaves just the contribution form R 1 as z = a0 = 0 f (x) dx. In general, Fourier-type sums are good things to keep an eye out for, even if they don’t explicitly come from Fourier series. For example, given a complex polynomial p(z) (or even a series):  2πik  P • The discrete sum n−1 p e n extracts the coefficients with indices divisible by n, k=0 • the integral R 2π it t=0 p(e ) dt = 2π · p(0) extracts the constant term of the polynomial, and so on. This is related to complex analysis, in which it turns complex differentiable functions C → C are exactly the same as complex analytic functions, which means you can go nuts with all sorts of beautiful results such as Cauchy’s theorem. Z Z R XX R R   √ R − + − ··· √ . R Z .