26 SUMS where A(n),B(n),and C(n)are the coefficients of dependence on the general parameters a,B,and y. The repertoire method tells us to try plugging in simple functions of n for Rn,hoping to find constant parameters a,B,and y where the solution is especially simple.Setting Rn=1 implies =1,B=0,Y=0;hence A(n)-1 Setting Rn =n implies a =0,B=1,Y=0;hence B(n)=n. Setting Rn=n2 implies a =0,B=-1,y=2;hence 2C(n)-B(n)-n2 and we have C(n)=(n2 +n)/2.Easy as pie. Actually easier; Therefore if we wish to evaluate ∑0n+ian+T ∑(a+bk), k= the sum-recurrence (2.6)boils down to (2.7)with a B=a,y b,and the answer is aA(n)+aB(n)+bC(n)=a(n 1)+b(n+1)n/2. Conversely,many recurrences can be reduced to sums;therefore the spe- cial methods for evaluating sums that we'll be learning later in this chapter will help us solve recurrences that might otherwise be difficult.The Tower of Hanoi recurrence is a case in point: To=0; Tn 2Tn-1+1,for n>0. It can be put into the special form(2.6)if we divide both sides by 2n: To/20=0: Tn/2m=Tn-1/2n-1+1/2", for n>0. Now we can set Sn=Tn/2",and we have s0=0: Sn=Sn-1+2-n, for n>0. It follows that Sn= 2-k k=1
26 SUMS where A(n), B(n), and C(n) are the coefficients of dependence on the general parameters 01, B, and y. The repertoire method tells us to try plugging in simple functions of n for R,, hoping to find constant parameters 01, (3, and y where the solution is especially simple. Setting R, = 1 implies LX = 1, (3 = 0, y = 0; hence A(n) = 1. Setting R, = n implies a = 0, (3 = 1, y = 0; hence B(n) = n. Setting R, = n2 implies a = 0, (3 = -1, y = 2; hence 2C(n) -B(n) = n2 and we have C(n) = (n2 +n)/2. Easy as pie. Therefore if we wish to evaluate n E(a + bk) , k=O the sum-recurrence (2.6) boils down to (2.7) with a = (3 = a, y = b, and the answer is aA + aB(n) + bC(n) = a(n + 1) + b(n + l)n/2. Conversely, many recurrences can be reduced to sums; therefore the special methods for evaluating sums that we’ll be learning later in this chapter will help us solve recurrences that might otherwise be difficult. The Tower of Hanoi recurrence is a case in point: To = 0; T,, = 2T,_, +l , for n > 0. It can be put into the special form (2.6) if we divide both sides by 2”: To/2' = 0; TJ2" = T,-,/2-' +l/2n, for n > 0. Now we can set S, = T,/2n, and we have so = 0; s, = s,~-’ +2-n) for n > 0. Actually easier; n = x nx 14n+1)14n+3) 8 . It follows that s, = t2-k k=l
2.2 SUMS AND RECURRENCES 27 (Notice that we've left the term for k =0 out of this sum.)The sum of the geometric series -1+2-2+.+=(+()++()"will be derived later in this chapter;it turns out to be 1 ()"Hence Tn=2nSn=2"1. We have converted Tn to Sn in this derivation by noticing that the re- currence could be divided by 2n.This trick is a special case of a general technique that can reduce virtually any recurrence of the form anTn bnTn-1+Cn (2.9) to a sum.The idea is to multiply both sides by a summation factor,Sn: SnanTn SnDnTn-1+SnCn. This factor sn is cleverly chosen to make snbn Sn-1 an-1 Then if we write Sn=SnanTn we have a sum-recurrence, Sn Sn-1+Sncn. Hence Sn=s0a0+∑5kck=s1b1T6+∑5xck, k=1 k- and the solution to the original recurrence (2.9)is (2.10) Snan k=1 The value of s1 For example,when n=1 we get T1=(s1b1 To +s1c1)/s1a=(b1 To+c1)/ar. cancels out,so it But how can we be clever enough to find the right s,?No problem:The can be anything but zero.) relation Sn=Sn-1an-1/bn can be unfolded to tell us that the fraction an-1an-2…a1 Sn =bnbn-1...b2 (2.11) or any convenient constant multiple of this value,will be a suitable summation factor.For example,the Tower of Hanoi recurrence has a,,1 and bn=2; the general method we've just derived says that Sn=2-nis a good thing to multiply by,if we want to reduce the recurrence to a sum.We don't need a brilliant flash of inspiration to discover this multiplier. We must be careful,as always,not to divide by zero.The summation- factor method works whenever all the a's and all the b's are nonzero
2.2 SUMS AND RECURRENCES 27 (Notice that we’ve left the term for k = 0 out of this sum.) The sum of the geometricseries2~‘+2~2+~~~+2~“=(~)’+(~)2+~~~+(~)nwillbederived later in this chapter; it turns out to be 1 - (i )“. Hence T,, = 2”S, = 2” - 1. We have converted T, to S, in this derivation by noticing that the recurrence could be divided by 2n. This trick is a special case of a general technique that can reduce virtually any recurrence of the form a,T,, = bnTn-1 + cn (2.9) to a sum. The idea is to multiply both sides by a summation factor, s,: s,a,T,, = s,,bnTn-1 + snc,, . This factor s, is cleverly chosen to make s bn n = h-1 an-l s Then if we write S, = s,a,T,, we have a sum-recurrence, Sn = Sn-1 +SnCn. Hence %I = socuT + t skck = s.lblTo + c skck , k=l k=l and the solution to the original recurrence (2.9) is 1 n T, = - ha, s,b,To + &Ck k=l (2.10) [The value of s1 cancels out, so it can be anything but zero.) For example, when n = 1 we get T, = (s~b,To +slcl)/slal = (b,To +cl)/al. But how can we be clever enough to find the right s,? No problem: The relation s,, = snPl anPI /b, can be unfolded to tell us that the fraction a,- 1a,-2.. . al S n = b,bnp,...bz ’ (2.11) or any convenient constant multiple of this value, will be a suitable summation factor. For example, the Tower of Hanoi recurrence has a,, = 1 and b, = 2; the general method we’ve just derived says that sn = 2-” is a good thing to multiply by, if we want to reduce the recurrence to a sum. We don’t need a brilliant flash of inspiration to discover this multiplier. We must be careful, as always, not to divide by zero. The summationfactor method works whenever all the a’s and all the b’s are nonzero
28 SUMS Let's apply these ideas to a recurrence that arises in the study of"quick- sort,"one of the most important methods for sorting data inside a computer. (Quicksort was The average number of comparison steps made by quicksort when it is applied invented by Hoare to n items in random order satisfies the recurrence in1962158.) C0=0; 2c (2.12) Cn=n+1+ for n>0. n k=0 Hmmm.This looks much scarier than the recurrences we've seen before;it includes a sum over all previous values,and a division by n.Trying small cases gives us some data (C1=2,C2=5,C3=2)but doesn't do anything to quell our fears. We can,however,reduce the complexity of (2.12)systematically,by first getting rid of the division and then getting rid of the sign.The idea is to multiply both sides by n,obtaining the relation n-1 nCn=n2+n+2)∑Ck, for n>0; k=0 hence,if we replace n by n-1, n-2 (n-1)Cn-1=(n-1)2+(n-1)+2〉Cx, for n -1>0. k=0 We can now subtract the second equation from the first,and the >sign disappears: nCn-(m-1)Cn-1=2n+2Cn-1, for n 1. It turns out that this relation also holds when n=1,because C1=2.There- fore the original recurrence for Cn reduces to a much simpler one: c0=0: nCn (n+1)Cn-1+2n,for n>0. Progress.We're now in a position to apply a summation factor,since this recurrence has the form of (2.9)with a,n,bn=n+1,and cn =2n. The general method described on the preceding page tells us to multiply the recurrence through by some multiple of an-1an-2…a1n-1n-2)·..…1 2 sn bnbn-1..b2=(n+1).n.....3 :三n+1n
28 SUMS Let’s apply these ideas to a recurrence that arises in the study of “quicksort,” one of the most important methods for sorting data inside a computer. (Quicksort was The average number of comparison steps made by quicksort when it is applied invented b Y H0arc to n items in random order satisfies the recurrence in 1962 [158].) k=O for n > 0. (2.12) Hmmm. This looks much scarier than the recurrences we’ve seen before; it includes a sum over all previous values, and a division by n. Trying small cases gives us some data (Cl = 2, Cl = 5, CX = T) but doesn’t do anything to quell our fears. We can, however, reduce the complexity of (2.12) systematically, by first getting rid of the division and then getting rid of the 1 sign. The idea is to multiply both sides by n, obtaining the relation n-1 nC, = n2+n+2xCk, for n > 0; k=O hence, if we replace n by n - 1, n-2 (n-l)cnpj = (n-1)2+(n-1)+2xck, forn-1 >O. k=O We can now subtract the second equation from the first, and the 1 sign disappears: nC, - (n - 1)&l = 2n + 2C,-1 , for n > 1. It turns out that this relation also holds when n = 1, because Cl = 2. Therefore the original recurrence for C, reduces to a much simpler one: co = 0; nC, = (n + 1 )C,-I + 2n, for n > 0. Progress. We’re now in a position to apply a summation factor, since this recurrence has the form of (2.9) with a, = n, b, = n + 1, and c, = 2n. The general method described on the preceding page tells us to multiply the recurrence through by some multiple of a,._1 an-l. . . a1 (n-l).(n-2).....1 2 S n = b,b,-, . . b2 = (n+l).n...:3 = (n+l)n
2.2 SUMS AND RECURRENCES 29 We started with a The solution,according to (2.10),is therefore ∑in the recur- rence,and worked hard to get rid of it. But then after ap- plying a summation factor,we came up with another∑· The sum that remains is very similar to a quantity that arises frequently Are sums good,or bad,or what? in applications.It arises so often,in fact,that we give it a special name and a special notation: 1 Hn=1+2++=} k1 (2.13) The letter H stands for "harmonic";Hn is a harmonic number,so called because the kth harmonic produced by a violin string is the fundamental tone produced by a string that is l/k times as long. We can complete our study of the quicksort recurrence (2.12)by putting Cn into closed form;this will be possible if we can express Cn in terms of H,. The sum in our formula for Cn is 1≤k≤n We can relate this to Hn without much difficulty by changing k to k-1 and revising the boundary conditions: ≤k≤n l≤k-1≤n = 2≤k≤n+1 But your spelling is Alright!We have found the sum needed to complete the solution to (2.12): a/wrong. The average number of comparisons made by quicksort when it is applied to n randomly ordered items of data is Cm=2(n+1)Hn-2n. (2.14） As usual,we check that small cases are correct:Co=0,C1=2,C2=5
2.2 SUMS AND RECURRENCES 29 We started with a t in the recurrence, and worked hard to get rid of it. But then after applying a summation factor, we came up with another t. Are sums good, or bad, or what? But your spelling is a/wrong. The solution, according to (2.10), is therefore C, = 2(n + 1) f1. k=l k+l The sum that remains is very similar to a quantity that arises frequently in applications. It arises so often, in fact, that we give it a special name and a special notation: H, = ,+;+...+; r f;. k=l (2.13) The letter H stands for “harmonic”; H, is a harmonic number, so called because the kth harmonic produced by a violin string is the fundamental tone produced by a string that is l/k times as long. We can complete our study of the quicksort recurrence (2.12) by putting C, into closed form; this will be possible if we can express C, in terms of H,. The sum in our formula for C, is We can relate this to H, without much difficulty by changing k to k - 1 and revising the boundary conditions: = ( t >-- 1 1 1 i 1+nSi= H,-5. l<k<n nfl Alright! We have found the sum needed to complete the solution to (2.12): The average number of comparisons made by quicksort when it is applied to n randomly ordered items of data is C, = 2(n+l)H,-2n. (2.14) As usual, we check that small cases are correct: Cc = 0, Cl = 2, C2 = 5
30 SUMS 2.3 MANIPULATION OF SUMS Not to be confused with finance. The key to success with sums is an ability to change one into another that is simpler or closer to some goal.And it's easy to do this by learning 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 be transformed by using three simple rules: ∑cak=c∑ak; (distributive law) (2.15) kEK ∑(ak+bk)∑ak+∑t (associative law) (2.16 kEK kEK 。 k=∑ 0p(k)· (commutative law) (2.17 kEK p(k)EK The distributive law allows us to move constants in and out of a The associative law allows us to break a into two parts,or to combine two >'s into one.The commutative law says that we can reorder the terms in any way we please;here p(k)is any permutation of the set of all integers.For example, Why not call it if K=(-1,0,+1)and if p(k)=-k,these three laws tell us respectively that permutative instead of commutatioe? ca-1+Ca0+ca1=c(a-1+a0+a1); (distributive law) (a-1+b-1)+(ao+bo)+(a1+b1) =(a-1+ag+a1)+(b-1+b0+b,); (associative law) a-1+a0+Q1=a1+a0+a-1, (commutative law) Gauss's trick in Chapter 1 can be viewed as an application of these three basic laws.Suppose we want to compute the general sum of an aritluuetic progression, =∑(a+bk). 0≤k≤n By the commutative law we can replace k by n-k,obtaining This is something like changing vari- S=∑(a+b(n-k)=∑(a+bn-bk) ables inside an integral,but easier. 0≤n-k≤n 0≤k≤n These two equations can be added by using the associative law: 2S-∑(a+bk)+(a+bn-bk)=∑(2a+bn). 0≤k≤n 0≤k≤n
30 SUMS 2.3 MANIPULATION OF SUMS Not to be confused with finance. The key to success with sums is an ability to change one t into another that is simpler or closer to some goal. And it’s easy to do this by learning 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 be transformed by using three simple rules: x cak = c pk; (distributive law) (2.15) kEK kEK ~iak+bk) = &+~bk; (associative law) (2.16) kEK kEK UK x ak = x %(k) * (commutative law) (2.17) kEK p(k)EK The distributive law allows us to move constants in and out of a t. The associative law allows us to break a x into two parts, or to combine two x’s into one. The commutative law says that we can reorder the terms in any way we please; here p(k) is any permutation of the set of all integers. For example, Why not call it if K = (-1 (0, +l} and if p(k) = -k, these three laws tell us respectively that permutative instead of commutative? ca-1 + cao + cal = c(a-j faofal); (distributive law) (a-1 Sb-1) + (ao+b) + (al +bl) = (a-l+ao+al)+(b-l+bo+bl); (associative law) a-1 + a0 + al = al + a0 + a-1 . (commutative law) Gauss’s trick in Chapter 1 can be viewed as an application of these three basic laws. Suppose we want to compute the general sum of an arithmetic progression, S = x (afbk). O<k$n By the commutative law we can replace k by n - k, obtaining S = x (a+b(n-k)) = x (a+bn-bk). O<n-k<n O<k<n These two equations can be added by using the associative law: This is something like changing variables inside an integral, but easier. 2S = x ((a+bk)+(a+bn-bk)) = x (2afbn). O<k<n O<k$n