[ Pobierz całość w formacie PDF ]
.But it s still not really what we re seeking.All ofthe other sums we have evaluated so far in this chapter have been conqueredwithout induction; we should likewise be able to determine a sum likefrom scratch.Flashes of inspiration should not be necessary.We should beable to do sums even on our less creative days.Method 2: Perturb the sum.So let s go back to the perturbation method that worked so well for thegeometric progression (2.25).We extract the first and last terms of in 44 SUMSorder to get an equation for,+(n+l) = == k+ 12 kOops- the cancel each other.Occasionally, despite our best efforts, theperturbation method produces something like = so we lose.Seems more like aOn the other hand, this derivation is not a total loss; it does reveal a wayto sum the first n integers in closed form,2 k =even though we d hoped to discover the sum of first integers squared.Couldit be that if we start with the sum of the integers cubed, which we mightcall we will get an expression for the integers squared? Let s try it.= =Sure enough, the cancel, and we have enough information to determineMethod 2 :Perturb your TA.without relying on induction:= n - l ) =Method 3: Build a repertoire.A slight generalization of the recurrence (2.7) will also suffice formands involving The solution to=for n 0,=will be of the general formand we have already determined A(n), B(n), and C(n), because (2.41) is thesame as (2.7) when 6 = 0.If we now plug in = we find that is the 2.5 GENERAL METHODS 45=-3, 6=3.Hencesolution when a = 0, =+ B(n) =this determines D(n).We re interested in the sum which equals -1 + thus we get= if we set a = = = 0 and 6 = 1 in (2.41).ConsequentlyEl, = D(n).We needn t do the algebra to compute D(n) from B(n) andC(n), since we already know what the answer will be; but doubters among usshould be reassured to find thatMethod 4: Replace sums by integrals.People who have been raised on calculus instead of discrete mathematicstend to be more familiar with than with so they find it natural to trychanging to One of our goals in this book is to become so comfortablewith that we ll think is more difficult than (at least for exact results).But still, it s a good idea to explore the relation between and sincesummation and integration are based on very similar ideas.In calculus, an integral can be regarded as the area under a curve, and wecan approximate this area by adding up the areas of long, skinny rectanglesthat touch the curve.We can also go the other way if a collection of long,skinny rectangles is given: Since is the sum of the areas of rectangleswhose sizes are 1 x 1 x 4,.,1 x it is approximately equal to the areaunder the curve f(x) = between 0 and n.The horizontal scalehere is ten times thevertical scale.123 n XThe area under this curve is dx = therefore we know that isapproximately 46 SUMSOne way to use this fact is to examine the error in the approximation,Since satisfies the recurrence = we findthat satisfies the simpler recurrence==Another way to pursue the integral approach is to find a formula for bysumming the areas of the wedge-shaped error terms.We have=This is for peopleaddicted to calculus.(k-=3k=lEither way, we could find and thenMethod 5: Expand and contract.Yet another way to discover a closed form for Cl, is to replace the orig-inal sum by a seemingly more complicated double sum that can actually besimplified if we massage it properly:[The last step hereis something like=the last step ofthe perturbationmethod, because= =1we get an equationwith the unknownGoing from a single sum to a double sum may appear at first to be a backwardquantity on bothstep, but it s actually progress, because it produces sums that are easier tosides.)work with.We can t expect to solve every problem by continually simplifying,simplifying, and simplifying: You can t scale the highest mountain peaks byclimbing only uphill!Method 6: Use finite calculus.Method 7: Use generating functions.Stay tuned for still more exciting calculations of = as welearn further techniques in the next section and in later chapters. 2.6 FINITE AND INFINITE CALCULUS 472.6 FINITE AND INFINITE CALCULUSWe ve learned a variety of ways to deal with sums directly.Now it stime to acquire a broader perspective, by looking at the problem of summa-tion from a higher level
[ Pobierz całość w formacie PDF ]