[ Pobierz całość w formacie PDF ]
.3 MANIPULATION OF SUMS Not to be confusedwith finance.The key to success with sums is an ability to change one intoanother that is simpler or closer to some goal.And it s easy to do this bylearning a few basic rules of transformation and by practicing their use.Let K be any finite set of integers.Sums over the elements of K can betransformed by using three simple rules:(distributive law)(2.15)(associative law) (2.16)=(commutative law)(2.17)The distributive law allows us to move constants in and out of a Theassociative law allows us to break a into two parts, or to combine twointo one.The commutative law says that we can reorder the terms in any waywe please; here p(k) is any permutation of the set of all integers.For example, Why not call itpermutative insteadif K = (-1 and if p(k) = these three laws tell us respectively thatof commutative?+ + = (distributive law)(associative law)(commutative law)+ a0 = + a0 +.Gauss s trick in Chapter 1 can be viewed an application of these threebasic laws.Suppose we want to compute the general sum of an arithmeticprogression,S =This is somethingBy the commutative law we can replace k by n k, obtaininglike changing vari-ables inside anS = ( a + b ( n - k ) ) = ( a + b n - b k ).integral, but easier.These two equations can be added by using the associative law:= ( ( a + b k ) + ( a + b n - b k ) ) =2.3 MANIPULATION OF SUMS 31And we can now apply the distributive law and evaluate a trivial sum: What s oneand one and oneand one and one= 1 =and one and oneand one and oneand one?Dividing by 2, we have proved thatdon t know,said Alice.lost count.(2.18)a+bk) = She can t doAddition.-Lewis CarrollThe right-hand side can be remembered as the average of the first and lastterms, namely (a + (a + bn)), times the number of terms, namely (n + 1).It s important to bear in mind that the function p(k) in the generalcommutative law (2.17) is supposed to be a permutation of all the integers.Inother words, for every integer n there should be exactly one integer k such thatp(k) n.Otherwise the commutative law might fail; exercise 3 illustratesthis with a vengeance.Transformations like p(k) = k + c or p(k) = c k,where c is an integer constant, are always permutations, so they always work.On the other hand, we can relax the permutation restriction a little bit:We need to require only that there be exactly one integer k with p(k) = nwhen n is an element of the index set K.If n K (that is, if n is not in K),it doesn t matter how often p(k) = n occurs, because such k don t take partin the sum.Thus, for example, we can argue thatevenk even 2k evensince there s exactly one k such that 2k = n when n K and n is even.Iverson s convention, which allows us to obtain the values 0 or 1 fromlogical statements in the middle of a formula, can be used together with theAdditional, eh? distributive, associative, and commutative laws to deduce additional proper-ties of sums.For example, here is an important rule for combining differentsets of indices: If K and K are any sets of integers, then(2.20)This follows from the general formulas(2.21)kand(2.22)=32 SUMSTypically we use rule (2.20) either to combine two almost-disjoint index sets,as infor 1 m n;akor to split off a single term from a sum, as infor n 0.ak ,This operation of splitting off a term is the basis of a perturbationmethod that often allows us to evaluate a sum in closed form.The ideais to start with an unknown sum and call it S,:(Name and conquer.) Then we rewrite in two ways, by splitting off bothits last term and its first term:ak a0a k1=ak+l.(2.24)Now we can work on this last sum and try to express it in terms of S,.If wesucceed, we obtain an equation whose solution is the sum we seek.For example, let s use this approach to find the sum of a general geomet- If it s geometric,there should be aric progression,geometric proof.=The general perturbation scheme in (2.24) tells us that+ = + ,and the sum on the right is = by the distributive law.Therefore = a and we can solve for to obtain= f o r x # l(2.25 )k = O2.3 MANIPULATION OF SUMS 33(When x 1, the sum is of course simply (n 1 )a.) The right-hand sideAh yes, this formula can be remembered as the first term included in the sum minus the first termwas drilled into meexcluded (the term after the last), divided by 1 minus the term ratio.in high school.That was almost too easy [ Pobierz całość w formacie PDF ]