282 Math PreviewChris BrownSeptember 8, 2005Contents1 Why This? 22 Logarithms 22.1 Basic Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Basic Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Sums of Series 33.1 Arithmetic Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33.2 Polynomial Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.3 Geometric Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.4 Harmonic Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.5 Arithmetic-Geometric Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.6 Using Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.7 Who Knew? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Bounds 84.1 Big Bounds by Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.2 Putting Limits to Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.3 Little Bounds by Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Simple Recurrence Techniques 105.1 Brute Force Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115.2 Telescoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115.3 The Master Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1311 Why This?I’ve noticed that often the only math in an algorithms bo ok is presented in one or two chaptersand then is referred to for the next 1100 or s o pages. So it’s good to get this material naileddown early.This is mostly reiteration of content from CLRS chapters 3 and 4, but I’ve used materialfrom a couple of other Algorithms textbooks. This is meant to fill in some CLRS gaps, butI’m not sure the gaps are really there – maybe it’s just been useful for me to pull this stufftogether in one spot. If it helps anyone else, great, but it’s certainly not meant to be any sortof self-contained tutorial.Still, please report typos, bugs, thinkos, and unclarities, as well as suggestions for morecontent, to [email protected] and maybe we can improve its chances of being useful.2 Logarithms2.1 Basic IdentitiesDefinition: For b > 1, x > 0, logb(x) is real L such that bL= x.Properties: (following easily from the definition)• logbis a strictly increasing function: x > y ⇒ logb(x) > logb(y)• logbis one-to-one: logb(x) = logb(y) ⇒ x = y.• logb(1) = 0 for any b since b0= 1.• logb(ba) = a (pretty much restates the definition).• logb(xy) = logb(x) + logb(y). If bL= x and bM= y, then bLbM= b(L+M)= xy and by theprevious result logb(xy) = L + M = logb(x) + logb(y).• logb(xa) = a logb(x). Use previous result a times with y = x.• xlogb(y)= ylogb(x). Use 2nd property above to justify taking logs on both sides: logb(x) logb(y) =logb(y) logb(x).• logc(x) = logb(x)/ logb(c). This important base-changing identity that establishes t hatlogs to two different bases are related by a constant multiple. Let L = logc(x), M = logb(x),N = logb(c). Then cL= x, bM= x, and bN= c. But if c = bNthen x = cL= (bN)L, andalso x = bM, so bM= bNL⇒ M = NL ⇒ L = M/N.22.2 Basic ConsequencesThere are a number of little corollaries and techniques flowing from these identities that mightcause some head-scratching when first seen. They are useful if you want to compare functionsthat are written using different bases. For ins tance, one can rewrite an exponentiation to adifferent base by first taking logs and then exponentiating to the base of the log, comme ¸ca:nx= 2x lg(n),or the more excitingnlg(n)= 2lg lg(n).ornlg(n) = 2lg(n)+lg lg(n)= 21+lg lg(n)lg(n),which if you’re normal isn’t obvious at first blush.These examples do not address the complications introduced by arbitrary bases (e.g. e, 10,3 ...) that would force the use of the base-changing identity, thus introducing a base-changingmultiplier into the picture.3 Sums of Series3.1 Arithmetic SeriesFor instancenXi=1i =n(n + 1)2.Why? Draw n × (n + 1) rectangle and a jaggy diagonal and count the squares in one half.Or think of numbers 1 to n and pair them up first to last, 2nd to penultimate, etc. You getn/2 sums each equal to n + 1. Questions: what if n is odd? Does this trick work for othersummation limits?These questions should lead you to think that maybe you can use the above counting tricksfor linear variants on the sum. Indeed. Consider 2 + 5 + 8 + . . . + (3k − 1). Rewritten as 3( 1+ 2 + 3+ . . . + k) - (1 + 1 + 1 + . . . + 1) the sum is obviously 3(k(k −1)/2) −k. OR you canagain add the first and last, 2nd and next-last, etc. to get k/2 pairs …