《Mathematics for Computer》Lecture 10 sums 1

6.042/18.] Mathematics for Computer Science March 10. 2005 Srini devadas and Eric Lehman Lecture notes Sums and Approximations When you analyze the running time of an algorithm, the probability some procedure succeeds, or the behavior of a load-balancing or communications scheme, you'll rarely get a simple answer. The world is not so kind. More likely, you'll end up with a complicated sum 1+ Or you might get an answer that is just tad too complicated to grasp intuitively And these examples are relatively benign! So the ability to cope with such messy mathematical expressions is an important skill in computer science-and in many other areas of science and engineering. This might not seem glorious, but people who can cut monstrous expressions down to size in moments can seem pretty amazing to the uninitiated. This week, we'll equip you with the most seful tricks of the trade 1 The value of an annuity Would you prefer a million dollars today or $20,000 a year for the next fifty years? This is a question about the value of an annuity, a financial instrument that pays out a fixed amount of money at the beginning of every year for some specified number of years In particular, an n-year, Sm-payment annuity pays m dollars at the start of each year for n years. In some cases, n is finite, but not always. Examples include lottery payouts student loans, and home mortgages. There are even Wall Street people who specialize in trading annuities For many reasons, $20,000 a year for 50 years is worth much less than a million dollars ght now. For example, consider the last $20,000 installment. If you had that $20,000 right now, then you could start earning interest, invest the money in the stock market

� � 6.042/18.062J Mathematics for Computer Science March 10, 2005 Srini Devadas and Eric Lehman Lecture Notes Sums and Approximations When you analyze the running time of an algorithm, the probability some procedure succeeds, or the behavior of a load­balancing or communications scheme, you’ll rarely get a simple answer. The world is not so kind. More likely, you’ll end up with a complicated sum: �n 1 k + √ k k=1 Or a nasty product: � � � � � � � � 1 2 3 n 1 + 1 + 1 + 1 + n n n 2 2 2 2 · · · n Or you might get an answer that is just tad too complicated to grasp intuitively: 72/n n 1 + 100 And these examples are relatively benign! So the ability to cope with such messy mathematical expressions is an important skill in computer science— and in many other areas of science and engineering. This might not seem glorious, but people who can cut monstrous expressions down to size in moments can seem pretty amazing to the uninitiated. This week, we’ll equip you with the most useful tricks of the trade. 1 The Value of an Annuity Would you prefer a million dollars today or $20,000 a year for the next fifty years? This is a question about the value of an annuity, a financial instrument that pays out a fixed amount of money at the beginning of every year for some specified number of years. In particular, an n­year, $m­payment annuity pays m dollars at the start of each year for n years. In some cases, n is finite, but not always. Examples include lottery payouts, student loans, and home mortgages. There are even Wall Street people who specialize in trading annuities. For many reasons, $20,000 a year for 50 years is worth much less than a million dollars right now. For example, consider the last $20,000 installment. If you had that $20,000 right now, then you could start earning interest, invest the money in the stock market

2 Sums and Approximations or just buy something fun. However, if you don't get the $20,000 for another 50 years then someone else is earning all the interest or investment profit. Furthermore, prices are likely to gradually rise over the next 50 years, so you when you finally get the money, you won't be able to buy as much. Finally, people only live so long, if you were 60 years old, a payout 50 years in the future would be worth next to nothing! But what if your choice were between $40,000 a year for 50 years and a million dollars today? Now which is better? What is an annuity is actually worth? 1.1 The Future value of Money In order to address such questions, we have to make an assumption about the future value of money. Let's put most of the complications aside and think about this from a simple-minded perspective. The average rate of inflation in the United States from 1980 to 2004 was about p= 3.5% per year. This means that the price of a selection of basic goods increases by about 3.5% each year. If this trend continues, then goods costing $100 today will cost 81001+p)=810350in1year 1001+p)2=81072in2year S100(1+p) in k years Looked at another way, k years from now, $100 will have the buying power of just 100/(1+ p) dollars today. Now we can work out the value of an annuity that pays m dollars at the start of each ear for the next n years payments current value Sm today y Sm in 1 vear t p Sm in 2 years Sm in n- l years (1+p)n- Total current value: V (1+p)

2 Sums and Approximations or just buy something fun. However, if you don’t get the $20,000 for another 50 years, then someone else is earning all the interest or investment profit. Furthermore, prices are likely to gradually rise over the next 50 years, so you when you finally get the money, you won’t be able to buy as much. Finally, people only live so long; if you were 60 years old, a payout 50 years in the future would be worth next to nothing! But what if your choice were between $40,000 a year for 50 years and a million dollars today? Now which is better? What is an annuity is actually worth? 1.1 The Future Value of Money In order to address such questions, we have to make an assumption about the future value of money. Let’s put most of the complications aside and think about this from a simple­minded perspective. The average rate of inflation in the United States from 1980 to 2004 was about p = 3.5% per year. This means that the price of a selection of basic goods increases by about 3.5% each year. If this trend continues, then goods costing $100 today will cost: $100(1 + p) = $103.50 in 1 year $100(1 + p) 2 = $107.12 in 2 year . . . $100(1 + p) k in k years Looked at another way, k years from now, $100 will have the buying power of just 100/(1+ p)k dollars today. Now we can work out the value of an annuity that pays m dollars at the start of each year for the next n years: payments current value $m today m $m in 1 year m 1 + p $m in 2 years m (1 + p)2 · · · · · · $m in n − 1 years m (1 + p)n−1 �n−1 m Total current value: V = (1 + p)k k=0

Sums and Approximations So to compute the value of the annuity we need only evaluate this sum. We could plug in values for m, n, and p, compute each term explicitly, and then add them all up However, this particular sum has an equivalent"closed form"that makes the job easier. In general, a closed form is a mathematical expression that can be evaluated with a fixed number of basic operations(addition, multiplication, exponentiation, etc. )In contrast, evaluating the sum above requires a number of operations proportional to n 1.2 A Geometric sum Our goal is to find a closed form equivalent to the summation V m+ 1+p) 1+p(1+p)2 ...+ (1+p)k-1 This is a geometric sum, which means that consecutive terms all have the same ratio. In particular, the second term is 1/(1+p) times the first, the third is 1/(1+ p)times the second, and so forth. And weve already encountered a theorem about geometric sums Theorem 1. For all n> 1 and all z+1 This theorem can be proved by induction, but that proof gives no hint how the for- mula might be found in the first place. Here is a more insightful derivation based on the perturbation method. First, we let S equal the value of the sum and then"perturb"it by multiplying by a + 2+ + The difference between the original sum and the perturbed sum is not so great, because here is massive cancellation on the right side s-2S=1 Now solving for S gives the expression in Theorem 1 You can derive a passable number of summation formulas by mimicking the approach used above. Well look at some other methods for evaluting sums shortly

� Sums and Approximations 3 So to compute the value of the annuity, we need only evaluate this sum. We could plug in values for m, n, and p, compute each term explicitly, and then add them all up. However, this particular sum has an equivalent “closed form” that makes the job easier. In general, a closed form is a mathematical expression that can be evaluated with a fixed number of basic operations (addition, multiplication, exponentiation, etc.) In contrast, evaluating the sum above requires a number of operations proportional to n. 1.2 A Geometric Sum Our goal is to find a closed form equivalent to the summation: �n−1 m m m m V = = m + + + . . . + (1 + p)k 1 + p (1 + p)2 (1 + p)k−1 k=0 This is a geometric sum, which means that consecutive terms all have the same ratio. In particular, the second term is 1/(1 + p) times the first, the third is 1/(1 + p) times the second, and so forth. And we’ve already encountered a theorem about geometric sums: Theorem 1. For all n ≥ 1 and all z = 1: �n−1 n k 1 − z z = 1 − z k=0 This theorem can be proved by induction, but that proof gives no hint how the for￾mula might be found in the first place. Here is a more insightful derivation based on the perturbation method. First, we let S equal the value of the sum and then “perturb” it by multiplying by z. S = 1 + z + z2 + . . . + zn−1 zS = z + z2 + . . . + zn−1 + zn The difference between the original sum and the perturbed sum is not so great, because there is massive cancellation on the right side: S − zS = 1 − z n Now solving for S gives the expression in Theorem 1: n 1 − z S = 1 − z You can derive a passable number of summation formulas by mimicking the approach used above. We’ll look at some other methods for evaluting sums shortly

Sums and Approximations 1.3 Return of the annuity problem Now we can solve the annuity pricing problem! The value of an annuity that pays m dollars at the start of each year for n years is (1+k) = m> 2 (where z 1+p We apply Theorem 1 on the second line, and undo the the earlier substitution z= 1/(1+p) on the last line The last expression is a closed form; it can be evaluated with a fixed number of ba- sic operations. For example, what is the real value of a winning lottery ticket that pays $40,000 per year for 50 years? Plugging in m =$40, 000, n= 50, and p=0.035 gives Va S971, 063. Youd be better off taking the million dollars today 1.4 Infinite Sums All right, would you prefer a million dollars today or $40,000 a year forever? This might seem like an easy choice- when infinite money is on offer, why worry about inflation? This is a question about an infinite sum. In general, the value of an infinite sum is defined as the limit of a finite sum as the number of terms goes to infinity means lim>Zk n→ So the value of an annuity with an infinite number of payments is given by our previ- ous answer in the limit as n goes to infinity 1 1+p m:一

� � � � � � 4 Sums and Approximations 1.3 Return of the Annuity Problem Now we can solve the annuity pricing problem! The value of an annuity that pays m dollars at the start of each year for n years is: �n−1 m V = (1 + k)p k=0 �n−1 1 k = m z (where z = ) 1 + p k=0 n 1 − z = m · 1 − z n 1 1 − 1+p = m · � � 1 1 − 1+p We apply Theorem 1 on the second line, and undo the the earlier substitution z = 1/(1+p) on the last line. The last expression is a closed form; it can be evaluated with a fixed number of ba￾sic operations. For example, what is the real value of a winning lottery ticket that pays $40, 000 per year for 50 years? Plugging in m = $40, 000, n = 50, and p = 0.035 gives V ≈ $971, 063. You’d be better off taking the million dollars today! 1.4 Infinite Sums All right, would you prefer a million dollars today or $40,000 a year forever? This might seem like an easy choice— when infinite money is on offer, why worry about inflation? This is a question about an infinite sum. In general, the value of an infinite sum is defined as the limit of a finite sum as the number of terms goes to infinity: ∞ n zk means lim zk k=0 n→∞ k=0 So the value of an annuity with an infinite number of payments is given by our previ￾ous answer in the limit as n goes to infinity: n 1 1 − 1+p V = lim m · � � n→∞ 1 1 − 1+p 1 = m · � � 1 1 − 1+p 1 + p = m · p

Sums and Approximations In the second step, notice that the 1/(1+p) term in the numerator goes to zero in the limit. The third equation follows by simplifying Plugging in m=$40, 000 and p=0.035 into this formula gives V a $1, 182, 857. The value of money drops off so fast that even an infinite number of payments are worth on a bit over a million dollars. In fact, the total value of all payments beyond the 50th is only about$200,000! More generally, we can get a closed form for infinite geometric sums from Theorem 1 by taking a limit Corollary 2. If 2<1, then Pr lim lim 1 The first equation uses the definition of an infinite limit, and the second uses Theorem 1 In the limit, the term antl in the numerator vanishes since z<1 We now have closed forms for both finite and infinite geometric series. Some example are given below. In each case, the solution follows immediately from either Theorem 1 (for finite series)or Corollary 2(for infinite series) 248 ∑(1/2) (1/ 11 1/2)2 2 2+4-8 1+2+4+8 22 1+3+9+27+…+3-=∑3 Here is a good rule of thumb: the sum of a geometric series is approximately equal to the term with greatest absolute value. In the first two examples, the largest term is equal to 1 and the sums are 2 and 2/3, which are both relatively close to 1. In the third example, the sum is about twice the largest term. In the final example, the largest term is 3"- and the sum is(3n-1)/2, which is 1.5 times greater

� � Sums and Approximations 5 In the second step, notice that the 1/(1 + p)n term in the numerator goes to zero in the limit. The third equation follows by simplifying. Plugging in m = $40, 000 and p = 0.035 into this formula gives V ≈ $1, 182, 857. The value of money drops off so fast that even an infinite number of payments are worth on a bit over a million dollars. In fact, the total value of all payments beyond the 50th is only about $200,000! More generally, we can get a closed form for infinite geometric sums from Theorem 1 by taking a limit. Corollary 2. If |z| < 1, then: � 1 ∞ i z = 1 − z i=0 Proof. ∞ n−1 i z = lim z i i=0 n→∞ i=0 n 1 − z = lim n→∞ 1 − z 1 = 1 − z The first equation uses the definition of an infinite limit, and the second uses Theorem 1. In the limit, the term zn+1 in the numerator vanishes since |z| < 1. We now have closed forms for both finite and infinite geometric series. Some examples are given below. In each case, the solution follows immediately from either Theorem 1 (for finite series) or Corollary 2 (for infinite series). ∞ 1 1 1 � 1 1 + + + + . . . = (1/2)i = = 2 2 4 8 1 − (1/2) i=0 ∞ 1 1 1 � 1 2 1 − + . . . = (−1/2)i = 1 − (−1/2) = 2 3 + 4 − 8 i=0 n−1 1 + 2 + 4 + 8 + . . . + 2n−1 = �2i = 1 − 2n = 2n − 1 1 − 2 i=0 n−1 3n 1 + 3 + 9 + 27 + . . . + 3n−1 = �3i = 1 − 3n = − 1 1 − 3 2 i=0 Here is a good rule of thumb: the sum of a geometric series is approximately equal to the term with greatest absolute value. In the first two examples, the largest term is equal to 1 and the sums are 2 and 2/3, which are both relatively close to 1. In the third example, the sum is about twice the largest term. In the final example, the largest term is 3n−1 and the sum is (3n − 1)/2, which is 1.5 times greater

ums and Approximations 2 Sums of powers Pharaoh Aha I decides to build a"pyramid "in his own honor consisting of a single block His successor, Aha Il, trumps him by building a larger pyramid Not to be outdone, Aha Ill builds a still-larger pyramid If this madness continues, how many blocks will Pharoah Aha n require? Lets break the problem down by chopping the n-th pyramid into n horizontal slabs Therefore, we have # blocks in n-th pyramid=># blocks in k-th slab Similarly, we can slice each slab into columns

� 6 Sums and Approximations 2 Sums of Powers Pharaoh Aha I decides to build a “pyramid” in his own honor consisting of a single block: His successor, Aha II, trumps him by building a larger pyramid: Not to be outdone, Aha III builds a still­larger pyramid: If this madness continues, how many blocks will Pharoah Aha n require? Let’s break the problem down by chopping the n­th pyramid into n horizontal slabs: Etc. Therefore, we have: n # blocks in n­th pyramid = # blocks in k­th slab k=1 Similarly, we can slice each slab into columns:

Sums and Approximations 5 5 2k-1 So the number of blocks in the k-th slab is +3+5+…+(2k-1)+….+5+3+1=(2k-1)+2.∑2i Plugging this into the previous sum gives the total number of blocks required by Pharaoh Aha blocks in n-th pyramid ∑ (2k-1)+ This sum is pretty nasty. And the bad news is that similar sums arise when analyzing the running time of a program with nested loops 2.1 Evaluating the Sum Sums of small powers are actually easy to handle, because there are simple closed-form equivalents Lemma 3(Sums of Powers) m(m+ 1+2+3+...+m 12+22+32+.+m2 m(m+o)(m+ m2(m+1) These formulas can all be proved by routine induction arguments. For now, let's apply hem toto find a closed-form expression for the number of blocks in a pyramid. First

� � � � � Sums and Approximations 7 . . . . . . 3 5 2k−1 5 3 1 1 So the number of blocks in the k­th slab is: k−1 1 + 3 + 5 + . . . + (2k − 1) + . . . + 5 + 3 + 1 = (2k − 1) + 2 · 2j − 1 j=1 Plugging this into the previous sum gives the total number of blocks required by Pharaoh Aha­n: n k−1 # blocks in n­th pyramid = (2k − 1) + 2 · 2j − 1 k=1 j=1 This sum is pretty nasty. And the bad news is that similar sums arise when analyzing the running time of a program with nested loops. 2.1 Evaluating the Sum Sums of small powers are actually easy to handle, because there are simple closed­form equivalents: Lemma 3 (Sums of Powers). m(m + 1) 1 + 2 + 3 + . . . + m = 2 1 2 2 12 + 22 + 3 + . . . + m = m(m + 2 )(m + 1) 3 m2 2 (m + 1) 3 3 13 + 23 + 3 + . . . + m = 4 These formulas can all be proved by routine induction arguments. For now, let’s apply them to to find a closed­form expression for the number of blocks in a pyramid. First

Sums and approximation lets tackle the inner sum: 2j-1= 2 (k-1)k (k-1) (k-1) On the first line, were using a standard maneuver: break up the sum of a polynomial into one sum for each term. In this case, we break the sum of 2j-1 into one sum involving j and one sum for the constant. This allows us to apply the standard formulas above, and the rest is simplification. Well use the same trick to finish off the whole pyramid problem, though now we have to sum values of a quadratic polynomial # blocks n+ h pyramid=∑(2k-1)+2∑2j-1 k=1 k-1)+2(k-1) k=1 k2-2>k+ k=1 n(m+5)(m+1 n+ Were done! But let's check a couple easy cases to make sure we made no algebra mis- takes. This formula says that a pyramid of size 1 contains(2. 15+1)/3= 1 block and a pyramid of size 2 contains 2)/3=6 blocks-both of which are correct 2.2 Where do the formulas come from? Sure, we can prove all the summation formulas in Lemma 3 by induction, but where did the expressions on the right come from? How on earth would we even guess an analogous summation formula for, say, fourth powers? Here is systematic way to generate a good guess. Remember that sums are the discrete cousins of integrals. So we might guess that the sum of a degree-k polynomial is a degree (k+ 1) polynomial, just as if we were integrating. Based on this observation, we might

� � � � � � � � � � � � � � � � 8 Sums and Approximations let’s tackle the inner sum: k−1 k−1 k−1 2j − 1 = 2 j − 1 j=1 j=1 j=1 (k − 1)k = 2 · − (k − 1) 2 = (k − 1)2 On the first line, we’re using a standard maneuver: break up the sum of a polynomial into one sum for each term. In this case, we break the sum of 2j − 1 into one sum involving j and one sum for the constant. This allows us to apply the standard formulas above, and the rest is simplification. We’ll use the same trick to finish off the whole pyramid problem, though now we have to sum values of a quadratic polynomial: n k−1 # blocks in n­th pyramid = (2k − 1) + 2 · 2j − 1 k=1 j=1 n = (2k − 1) + 2(k − 1)2 k=1 n = 2k2 − 2k + 1 k=1 n n n = 2 k2 − 2 k + 1 k=1 k=1 k=1 1 n(n + 2 )(n + 1) n(n + 1) = 2 · − 2 · + n 3 2 2n3 + n = 3 We’re done! But let’s check a couple easy cases to make sure we made no algebra mis￾takes. This formula says that a pyramid of size 1 contains (2 · 13 + 1)/3 = 1 block and a pyramid of size 2 contains (2 · 23 + 2)/3 = 6 blocks— both of which are correct. 2.2 Where Do the Formulas Come From? Sure, we can prove all the summation formulas in Lemma 3 by induction, but where did the expressions on the right come from? How on earth would we even guess an analogous summation formula for, say, fourth powers? Here is systematic way to generate a good guess. Remember that sums are the discrete cousins of integrals. So we might guess that the sum of a degree­k polynomial is a degree­ (k + 1) polynomial, just as if we were integrating. Based on this observation, we might

Approxi guess that +d for some constants a, b c, and d. all that remains is to determine these constants. We can do this by plugging a few values for n into the equation above. Each value gives a linear equation in a, b, c, and d. For example n=1 1=a+b+c+d 5=8a+4b+2c+d n=3→14=27a+9b+3c+d We now have four equations in four unknowns. Solving this system gives a= 1/ 3, b=1/2, c=1/6, and d=0, so it is tempting to conclude that 3+2+6 (n+)(mn+ But be careful! This equation is valid only if we were correct in our initial guess at the form of the solution. If we were wrong, then this equation might not hold for any n other than 0, 1, 2, and 3! So be sure to verify that such guesses are correct by giving an induction 3 Approximating Functions When you ask about the weather, you probably want to hear something like"hot","cold or"raining", not a lengthly discourse on convection currents, radiative heat transfer, and dew points. Something similar is true about the analysis of computer algorithms and systems: a simple, approximate answer is often more useful than an exact, complicated answer So techniques for replacing complicated expressions with simple approximations can be extremely useful 3.1 Taylor's Theorem A wonderful way to get approximations is to dredge up Taylor's Theorem from the dark, murky regions of calculus. Unfortuantely, the theorem looks like something dredged from a dark, murky place. So let's start with some intuition ple approximation for the function In(1+a) that is fairly accu- rate when a is a small number. Here's what the function actually looks like

� Sums and Approximations 9 guess that n 3 i 2 = an + bn2 + cn + d i=1 for some constants a, b, c, and d. All that remains is to determine these constants. We can do this by plugging a few values for n into the equation above. Each value gives a linear equation in a, b, c, and d. For example: n = 0 0 = ⇒ d n = 1 1 = ⇒ a + b + c + d n = 2 5 = 8 ⇒ a + 4b + 2c + d n = 3 14 = 27 ⇒ a + 9b + 3c + d We now have four equations in four unknowns. Solving this system gives a = 1/3, b = 1/2, c = 1/6, and d = 0, so it is tempting to conclude that: �n 3 2 i 2 n n n = + + 3 2 6 i=1 1 n(n + 2 )(n + 1) = 3 But be careful! This equation is valid only if we were correct in our initial guess at the form of the solution. If we were wrong, then this equation might not hold for any n other than 0, 1, 2, and 3! So be sure to verify that such guesses are correct by giving an induction proof. 3 Approximating Functions When you ask about the weather, you probably want to hear something like “hot”, “cold”, or “raining”, not a lengthly discourse on convection currents, radiative heat transfer, and dew points. Something similar is true about the analysis of computer algorithms and systems: a simple, approximate answer is often more useful than an exact, complicated answer. So techniques for replacing complicated expressions with simple approximations can be extremely useful. 3.1 Taylor’s Theorem A wonderful way to get approximations is to dredge up Taylor’s Theorem from the dark, murky regions of calculus. Unfortuantely, the theorem looks like something dredged from a dark, murky place. So let’s start with some intuition. Suppose we want a simple approximation for the function ln(1 + x) that is fairly accu￾rate when x is a small number. Here’s what the function actually looks like:

Sums and Approximations 1.5 In(1+a) The curve goes through the origin, so a trivial approximation is In(1+a)0 when c is small. In general f(a)a f(o) when r is small Sometimes this crude approximation is good enough, but not often. A line tangent to the curve at =0 provides a better approximation. The slope of tangent is given by the derivativ evaluated at r =0, which is 1/(1+0)=1. This gives the approximation In(1+r)Na, which is a significant improvement 1.5 0.5 In general ≈ This approximation is accurate enough in many situations. This is great, because linear functions are very simple and easy to manipulate This linear approximation has both the correct value at a =0 and the correct first derivative. We can go one more step and get an approximation with the correct second f(x)≈f(0)+xf(0)+。f"(0) when x is small

10 Sums and Approximations 6 1.5 y = ln(1 + x) 1 0.5 0 - 0 1 2 3 The curve goes through the origin, so a trivial approximation is ln(1 + x) ≈ 0 when x is small. In general: f(x) ≈ f(0) when x is small Sometimes this crude approximation is good enough, but not often. A line tangent to the curve at x = 0 provides a better approximation. The slope of the tangent is given by the derivative d 1 ln(1 + x) = dx 1 + x evaluated at x = 0, which is 1/(1 + 0) = 1. This gives the approximation ln(1 + x) ≈ x, which is a significant improvement: 6 1.5 y = x y = ln(1 + x) 1 0.5 0 - 0 1 2 3 In general: f(x) ≈ f(0) + xf � (0) when x is small This approximation is accurate enough in many situations. This is great, because linear functions are very simple and easy to manipulate. This linear approximation has both the correct value at x = 0 and the correct first derivative. We can go one more step and get an approximation with the correct second derivative: 2 x f(x) ≈ f(0) + xf � (0) + f��(0) when x is small 2