6.042/18.062] Mathematics for Computer Science March 11. 2005 Srini devadas and Eric Lehman Notes for Recitation 10 1+z+z 1+2+x2+…=12 1+2+3+...+n= n(n+1) 12+2+32+,+2n(n+3)(n+1) 13+23+33+..+n3 n2(n+1)2 4 Theorem(Taylor's theorem). Suppose that f R-R is n+ 1 times differentiable on the interval 0, c]. Then ()=10)+r(0x+r"0y2+…+-O) (n+1) (n+1)! for some z∈[0.,x
6.042/18.062J Mathematics for Computer Science March 11, 2005 Srini Devadas and Eric Lehman Notes for Recitation 10 n 1 + z + z2 + . . . + zn−1 = 1 − z (z = 1) 1 − z � 1 1 + z + x2 + . . . = 1 − z (|z| < 1) n(n + 1) 1 + 2 + 3 + . . . + n = 2 2 1 12 + 22 + 32 + . . . + n = n(n + 2 )(n + 1) 3 2 n (n + 1)2 3 13 + 23 + 33 + . . . + n = 4 Theorem (Taylor’s theorem). Suppose that f : R R is n + 1 times differentiable on the interval [0, x]. Then → 2 n f(n+1)(z)xn+1 f��(0)x f(n) (0)x f(x) = f(0) + f� (0)x + + . . . + + for some z ∈ [0, x]. 2! n! (n + 1)!
Recitation 10 1 Sums and approximations Problem 1. Evaluate the following sums Solution. The formula for the sum of an infinite geometric series with ratio 1 /2 (b) 111 Solution. The formula for the sum of an infinite geometric series with ratio -1/2 gl 2/3 1+2+4+8+...+2 Solution. The formula for the sum of a( finite) geometric series with ratio 2 gives 1-2n (d) k=n Solution ∑k2-∑k2 2n(2n+)2n+1)n(n+)(n+1)
� � � � �� Recitation 10 2 1 Sums and Approximations Problem 1. Evaluate the following sums. (a) 1 1 1 1 + + + + . . . 22 23 2 Solution. The formula for the sum of an infinite geometric series with ratio 1/2 gives: 1 = 2 1 1 − 2 (b) 1 1 1 1 − + . . . 2 + 22 − 23 Solution. The formula for the sum of an infinite geometric series with ratio −1/2 gives: 1 � � = 2/3 1 1 − −2 (c) 1 + 2 + 4 + 8 + . . . + 2n−1 Solution. The formula for the sum of a (finite) geometric series with ratio 2 gives: n 1 − 2 = 2n − 1 1 − 2 (d) 2n k2 k=n Solution. 2n 2n n k2 = k2 − k2 k=n+1 k=1 k=1 1 1 2n(2n + 2 )(2n + 1) n(n + 2 )(n + 1) = 3 − 3 (e) n m 3i+j i=0 j=0
Recitation 10 Solution 3 32 ()(C) n+1
Recitation 10 3 Solution. � � �n �m �n �m 3 i + j = 3 i · 3 j i=0 j=0 i=0 � j=0 � � � �m �n = 3 j · 3 i j=0 i=0 = � 3 m+1 − 1 2 � · � 3 n+1 − 1 2 �
Recitation 10 Problem 2. You've seen this neat trick for evaluating a geometric sum S=z+z2+..+zn+ s-2S=1 Use the same approach to find a closed-form expression for this sum T=1z+2z2+323+..+nzn Solution zT=1z2+223+324+..+ -1-nz
Recitation 10 4 Problem 2. You’ve seen this neat trick for evaluating a geometric sum: n S = 1 + z + z2 + . . . + z n n+1 zS = z + z2 + . . . + z + z S − zS = 1 − zn+1 1 − zn+1 S = 1 − z Use the same approach to find a closedform expression for this sum: 3 T = 1z + 2z2 + 3z + . . . + nzn Solution. 4 n+1 zT = 1z2 + 2z3 + 3z + . . . + nz 3 T − zT = z + z2 + z + . . . + zn − nzn+1 1 − zn+1 − 1 − nzn+1 = 1 − z 1 − zn+1 1 + nzn+1 T = (1 − z)2 − 1 − z
Recitation 10 Problem 3. Here is a nasty product 1+ Remarkably, an expression similar to this one comes up in analyzing the distribution of birthdays. Let' s make sense of it (a) give a two-term Taylor approximation for e. forget about the error term.) Solution e≈1+x (b) This is probably the most wide-used approximation in computer science. The fact that x appears at ground level"in the approximation and in the exponent of ef lets us translate sums into products and vice-versa. Rewrite the product using this Solution el/n. e2/n.e3/m (c) Now use a standard summation formula to simplify the exponent Solution. The formula 1+2+3+.+n=n(n+1)/2 gives (n+1)/(2n2)1/2+1/2n (d)What constant does this approach for large n Solution. ve
Recitation 10 5 Problem 3. Here is a nasty product: � � � � � � � � 1 2 3 n 1 + 1 + 1 + 1 + n n n 2 2 2 2 · · · n Remarkably, an expression similar to this one comes up in analyzing the distribution of birthdays. Let’s make sense of it. (a) Give a twoterm Taylor approximation for ex. (Forget about the error term.) Solution. xe ≈ 1 + x (b) This is probably the most wideused approximation in computer science. Thex fact that x appears at “ground level” in the approximation and in the exponent of e lets us translate sums into products and viceversa. Rewrite the product using this approximation. Solution. n/n2 1+2+...+n 1/n2 2/n2 3/n2 e e e e = e n2 · · · · · · (c) Now use a standard summation formula to simplify the exponent. Solution. The formula 1 + 2 + 3 + . . . + n = n(n + 1)/2 gives: n(n+1)/(2n2) 1/2+1/2n e = e (d) What constant does this approach for large n? Solution. √e
Recitation 10 Problem 4. Let's use Taylor's Theorem to find some approximations for the function /1+x (a)Give a three-term Taylor approximation for v1+I Solution. First, we compute two derivatives 21+x 4(1+x)3/2 Now we plug into Taylor's theorem f(x)≈f(0)+xf(0) 1+ (b)Sketch the function vI+r and your approximation. How good is the approxi- mation when x= 8? Solution. The approximation is pretty bad when r=8. The actual value is 3, but the approximation is-3 (c)Using this approximation and the fact that vi+r=vv1+1/a, give an ap proximation for v1+r that is accurate for large r Solution 1+x=√1+1/x 1 (d) Estimate 1,000,00 to a dozen places beyond the decimal point. You can try to check your answer with a calculator, but you'd better use a good one! Solution 1,0001≈1000·(1+ 2.1068·101 1000.000500000125
� � � � � Recitation 10 6 Problem 4. Let’s use Taylor’s Theorem to find some approximations for the function √1 + x. (a) Give a threeterm Taylor approximation for √1 + x. Solution. First, we compute two derivatives: 1 f� (x) = 2 √1 + x 1 f��(x) = −4(1 + x)3/2 Now we plug into Taylor’s theorem: f(x) ≈ f(0) + xf� (0) 2 x x 1 + 2 − 8 (b) Sketch the function √1 + x and your approximation. How good is the approximation when x = 8? Solution. The approximation is pretty bad when x = 8. The actual value is 3, but the approximation is 3. (c) Using this approximation and the fact that √1 + x = √x �1 + 1/x, give an approximation for √1 + x that is accurate for large x Solution. √ 1 + x = √x �1 + 1/x 1 1 ≈ x 1 + + √ 2x 8x2 (d) Estimate: 1, 000, 001 to a dozen places beyond the decimal point. You can try to check your answer with a calculator, but you’d better use a good one! Solution. � 1 1 1, 000, 001 ≈ 1000 · 1 + + 106 1012 2 · 8 · = 1000.000500000125