2 Sums SUMS ARE EVERYWHERE in mathematics,so we need basic tools to handle them.This chapter develops the notation and general techniques that make summation user-friendly. 2.1 NOTATION In Chapter 1 we encountered the sum of the first n integers,which we wrote out as 1+2+3+...+(n-1)+n.The'...'in such formulas tells us to complete the pattern established by the surrounding terms.Of course we have to watch out for sums like 1 +7 +...+41.7,which are meaningless without a mitigating context.On the other hand,the inclusion of terms like 3 and(n 1)was a bit of overkill;the pattern would presumably have been clear if we had written simply 1 +2+...+n.Sometimes we might even be so bold as to write just 1 +...+n. We'll be working with sums of the general form a1+a2+十a,, (2.1) where each ak is a number that has been defined somehow.This notation has the advantage that we can "see"the whole sum,almost as if it were written out in full,if we have a good enough imagination. A term is how long Each element ak of a sum is called a term.The terms are often specified this course lasts. implicitly as formulas that follow a readily perceived pattem,and in such cases we must sometimes write them in an expanded form so that the meaning is clear.For example,if 1+2+..+2n-l is supposed to denote a sum of n terms,not of 2-,we should write it more explicitly as 20+2+..+2n-1 21
2 Sums SUMS ARE EVERYWHERE in mathematics, so we need basic tools to handle them. This chapter develops the notation and general techniques that make summation user-friendly. 2.1 NOTATION In Chapter 1 we encountered the sum of the first n integers, which wewroteoutas1+2+3+...+(n-1)fn. The‘...‘insuchformulastells us to complete the pattern established by the surrounding terms. Of course we have to watch out for sums like 1 + 7 + . . . + 41.7, which are meaningless without a mitigating context. On the other hand, the inclusion of terms like 3 and (n - 1) was a bit of overkill; the pattern would presumably have been clear if we had written simply 1 + 2 + . . . + n. Sometimes we might even be so bold as to write just 1 f.. . + n. We’ll be working with sums of the general form al + a2 + ... + a,, (2.1) where each ok is a number that has been defined somehow. This notation has the advantage that we can “see” the whole sum, almost as if it were written out in full, if we have a good enough imagination. A term is how long Each element ok of a sum is called a term. The terms are often specified this course lasts. implicitly as formulas that follow a readily perceived pattern, and in such cases we must sometimes write them in an expanded form so that the meaning is clear. For example, if 1 +2+ . . . +2+' is supposed to denote a sum of n terms, not of 2”-‘, we should write it more explicitly as 2O + 2' +. . . + 2n-'. 21
22 SUMS The three-dots notation has many uses,but it can be ambiguous and a “Le signe bit long-winded.Other alternatives are available,notably the delimited form indique que I'on doit donner n au nombre entier i ak, (2.2) toutes ses valeurs 与 1,2,3,,t prendre la somme which is called Sigma-notation because it uses the Greek letter >(upper- des termes.” case sigma).This notation tells us to include in the sum precisely those J.Fourier [10 terms ak whose index k is an integer that lies between the lower and upper limits 1 and n,inclusive.In words,we "sum over k,from I to n."Joseph Fourier introduced this delimited t-notation in 1820,and it soon took the mathematical world by storm. Incidentally,the quantity after>(here ax)is called the summand. The index variable k is said to be bound to the >sign in (2.2),because the k in ok is unrelated to appearances of k outside the Sigma-notation.Any other letter could be substituted for k here without changing the meaning of Well,I wouldn't (22.The letter i is often used (perhaps because it stands for "index"),but want to use a or n we'll generally sum on k since it's wise to keep i for v-. as the index vari- able instead of k in It turns out that a generalized Sigma-notation is even more useful than (2.2);those letters the delimited form:We simply write one or more conditions under the > to specify the set of indices over which summation should take place.For 孺t6ia6益 example,the sums in (21)and (22)can also be written as ing outside the here. ∑ak (23) 1≤k≤n In this particular example there isn't much difference between the new form and (2.2),but the general form allows us to take sums over index sets that aren't restricted to consecutive integers.Fbr example,we can express the sum of the squares of all odd positive integers below 100 as follows: ∑k2 1≤k<00 k odd The delimited equivalent of this sum, 49 (2k+1)2, k=0 is more cumbersome and less clear.Similarly,the sum of reciprocals of all prime numbers between 1 and N is p≤N p prime
22 SUMS The three-dots notation has many uses, but it can be ambiguous and a “Le signe ,T~~~ bit long-winded. Other alternatives are available, notably the delimited form indique Ve /‘on doit dormer k=l au nombre entier i (2.2) to&es ses valeurs 1,2,3,..., et prendre la somme which is called Sigma-notation because it uses the Greek letter t (upper- des termes.” case sigma). This notation tells us to include in the sum precisely those - J. Fourier I1021 terms ok whose index k is an integer that lies between the lower and upper limits 1 and n, inclusive. In words, we “sum over k, from 1 to n.” Joseph Fourier introduced this delimited t-notation in 1820, and it soon took the mathematical world by storm. Incidentally, the quantity after x (here ok) is called the summa&. The index variable k is said to be bound to the x sign in (2.2),because the k in ok is unrelated to appearances of k outside the Sigma-notation. Any other letter could be substituted for k here without changing the meaning of Well, I wouldn’t (2.2). The letter i is often used (perhaps because it stands for “index”), but want to use a Or n we’ll generally sum on k since it’s wise to keep i for &i. as the index variable instead of k in It turns out that a generalized Sigma-notation is even more useful than (2.2); those letters the delimited form: We simply write one or more conditions under the x., are “free variables” to specify the set of indices over which summation should take place. For that do have meanexample, the sums in (2.1) and (2.2) can also be written as mg outside the 2 here. ix ak . (2.3) l<k<n In this particular example there isn’t much difference between the new form and (2.2), but the general form allows us to take sums over index sets that aren’t restricted to consecutive integers. Fbr example, we can express the sum of the squares of all odd positive integers below 100 as follows: l<k<lOO k odd The delimited equivalent of this sum, 2k + 1)’ , k=O is more cumbersome and less clear. Similarly, the sum of reciprocals of all prime numbers between 1 and N is x ;; P<N p prime
2.1 NOTATION 23 the delimited form would require us to write N)1 where pk denotes the kth prime and n(N)is the number of primes N. (Incidentally,this sum gives the approximate average number of distinct prime factors of a random integer near N,since about 1 /p of those integers are divisible by p.Its value for large N is approximately Inln N+0.261972128; In x stands for the natural logarithm of x,and InIn x stands for In(In x). The biggest advantage of general Sigma-notation is that we can manip- The summation ulate it more easily than the delimited form.For example,suppose we want symbol looks like to change the index variable k to k +1.With the general form,we have a distorted pacman. ∑ak=∑ak+i ≤k≤n 1sk+】≤n it's easy to see what's going on,and we can do the substitution almost without thinking.But with the delimited form,we have n--l ∑ak= ak+1i k=1 k=0 it's harder to see what's happened,and we're more likely to make a mistake. On the other hand,the delimited form isn't completely useless.It's A tidy sum. nice and tidy,and we can write it quickly because (2.2)has seven symbols compared with (2.3)'s eight.Therefore we'll often use with upper and lower delimiters when we state a problem or present a result,but we'll prefer to work with relations-under-x when we're manipulating a sum whose index variables need to be transformed. That's nothing. The sign occurs more than 1000 times in this book,so we should be You should see how sure that we know exactly what it means.Formally,we write many times∑ap pears in The Iliad. ∑ak (2.4) P( as an abbreviation for the sum of all terms ak such that k is an integer satisfying a given property P(k).(A "property P(k)"is any statement about k that can be either true or false.)For the time being,we'll assume that only finitely many integers k satisfying P(k)have ak0;otherwise infinitely many nonzero numbers are being added together,and things can get a bit tricky.At the other extreme,if P(k)is false for all integers k,we have an "empty"sum;the value of an empty sum is defined to be zero
2.1 NOTATION 23 the delimited form would require us to write The summation where pk denotes the kth prime and n(N) is the number of primes < N. (Incidentally, this sum gives the approximate average number of distinct prime factors of a random integer near N, since about 1 /p of those integers are divisible by p. Its value for large N is approximately lnln N + 0.261972128; In x stands for the natural logarithm of x, and In In x stands for ln( In x) .) The biggest advantage of general Sigma-notation is that we can manipulate it more easily than the delimited form. For example, suppose we want symbol looks like a distorted pacman. to change the index variable k to k + 1. With the general form, we have ak = ak+l ; l<k<n l<k+l<n it’s easy to see what’s going on, and we can do the substitution almost without thinking. But with the delimited form, we have n--l $ ak = tak+1; k=l k=O A tidy sum. it’s harder to see what’s happened, and we’re more likely to make a mistake. On the other hand, the delimited form isn’t completely useless. It’s nice and tidy, and we can write it quickly because (2.2) has seven symbols compared with (2.3)‘s eight. Therefore we’ll often use 1 with upper and lower delimiters when we state a problem or present a result, but we’ll prefer to work with relations-under-x when we’re manipulating a sum whose index variables need to be transformed. That’s nothing. The t sign occurs more than 1000 times in this book, so we should be You should see how many times C apsure that we know exactly what it means. Formally, we write pears in The Iliad. h (2.4) Pikl as an abbreviation for the sum of all terms ok such that k is an integer satisfying a given property P(k). (A “property P(k)” is any statement about k that can be either true or false.) For the time being, we’ll assume that only finitely many integers k satisfying P(k) have ok # 0; otherwise infinitely many nonzero numbers are being added together, and things can get a bit tricky. At the other extreme, if P(k) is false for all integers k, we have an “empty” sum; the value of an empty sum is defined to be zero
24 SUMS A slightly modified form of(2.4)is used when a sum appears within the text of a paragraph rather than in a displayed equation:We write)ak attaching property P(k)as a subscript of >so that the formula won't stick out too much.Similarly,akis a convenient alterative to(when we want to confine the notation to a single line. People are often tempted to write (k-1)in-k) instead of k(k-1)(n-k) k k=0 because the terms for k =0,1,and n in this sum are zero.Somehow it seems more efficient to add up n-2 terms instead of n +1 terms.But such temptations should be resisted;efficiency of computation is not the same as efficiency of understanding!We will find it advantageous to keep upper and lower bounds on an index of summation as simple as possible,because sums can be manipulated much more easily when the bounds are simple.Indeed, the formcan even be dangerously ambiguous,because its meaning is not at all clear when n=0 or n=1 (see exercise 1).Zero-valued terms cause no harm,and they often save a lot of trouble. So far the notations we've been discussing are quite standard,but now we are about to make a radical departure from tradition.Kenneth Iverson introduced a wonderful idea in his programming language APL 161,page 11], and we'll see that it greatly simplifies many of the things we want to do in this book.The idea is simply to enclose a true-or-false statement in brackets, and to say that the result is I if the statement is true.0 if the statement is Hey The“Kro false.For example, necker delta”that I've seen in other 了1， books (I mean [p prime] if p is a prime number, δkn,which is1if 10, if p is not a prime number. k =n,0 oth- erwise)is just a Iverson's convention allows us to express sums with no constraints whatever special case of on the index of summation,because we can rewrite(2.4)in the form Iverson 's conben- tion:We can write ∑aPk. k n instead. (2.5) If P(k)is false,the term akP(k)is zero,so we can safely include it among the terms being summed.This makes it easy to manipulate the index of summation,because we don't have to fuss with boundary conditions. A slight technicality needs to be mentioned:Sometimes ak isn't defined for all integers k.We get around this difficulty by assuming that [P(k)]is "very strongly zero"when P(k)is false,it's so much zero,it makes ok [P(k)] equal to zero even when ak is undefined.For example,if we use Iverson's
24 SUMS A slightly modified form of (2.4) is used when a sum appears within the text of a paragraph rather than in a displayed equation: We write ‘x.pCkl ak’, attaching property P(k) as a subscript of 1, so that the formula won’t stick out too much. Similarly, ‘xF=, ak’ is a convenient alternative to (2.2) when we want to confine the notation to a single line. People are often tempted to write n-1 z k(k- l)(n- k) instead of f k(k- l)(n- k) k=2 k=O because the terms for k = 0, 1, and n in this sum are zero. Somehow it seems more efficient to add up n - 2 terms instead of n + 1 terms. But such temptations should be resisted; efficiency of computation is not the same as efficiency of understanding! We will find it advantageous to keep upper and lower bounds on an index of summation as simple as possible, because sums can be manipulated much more easily when the bounds are simple. Indeed, the form EL!; can even be dangerously ambiguous, because its meaning is not at all clear when n = 0 or n = 1 (see exercise 1). Zero-valued terms cause no harm, and they often save a lot of trouble. So far the notations we’ve been discussing are quite standard, but now we are about to make a radical departure from tradition. Kenneth Iverson introduced a wonderful idea in his programming language APL [161, page 111, and we’ll see that it greatly simplifies many of the things we want to do in this book. The idea is simply to enclose a true-or-false statement in brackets, and to sav that the result is 1 if the statement is true. 0 if the statement is Hev: The “Kro- I false. For example, neiker delta” that I’ve seen in other 1, if p is a prime number; books (I mean [p prime] = 0 , if p is not a prime number. 6k,, , which is 1 if k=n, Ootherwise) is just a Iverson’s convention allows us to express sums with no constraints whatever special case of on the index of summation, because we can rewrite (2.4) in the form lverson ‘s convention: We can write x ak [P(k)] . k (2.5) [ k = n ] instead. If P(k) is false, the term ok[P(k)] is zero, so we can safely include it among the terms being summed. This makes it easy to manipulate the index of summation, because we don’t have to fuss with boundary conditions. A slight technicality needs to be mentioned: Sometimes ok isn’t defined for all integers k. We get around this difficulty by assuming that [P(k)] is “very strongly zero” when P(k) is false; it’s so much zero, it makes ok [P(k)] equal to zero even when ok is undefined. For example, if we use Iverson’s
2.1 NOTATION 25 convention to write the sum of reciprocal primes s N as ∑[p primep<Nl/p, there's no problem of division by zero when p =0,because our convention tells us that [0 prime][0<N1/0=0. Let's sum up what we've discussed so far about sums.There are two good ways to express a sum of terms:One way uses ...'the other uses 'The three-dots form often suggests useful manipulations,particularly the combination of adjacent terms,since we might be able to spot a simplifying pattern if we let the whole sum hang out before our eyes.But too much detail can also be overwhelming.Sigma-notation is compact,impressive to family and it's less and friends,and often suggestive of manipulations that are not obvious in likely to lose points three-dots form.When we work with Sigma-notation,zero terms are not on an exam for "lack of rigor..” generally harmful;in fact,zeros often make t-manipulation easier. 2.2 SUMS AND RECURRENCES OK,we understand now how to express sums with fancy notation. But how does a person actually go about finding the value of a sum?One way is to observe that there's an intimate relation between sums and recurrences. The sum Sn k=0 (Think of Sn as is equivalent to the recurrence not just a single number,but as a sequence defined for S0=a0; (2.6) aln≥0.) Sn=Sn-1+a,, for n >0. Therefore we can evaluate sums in closed form by using the methods we learned in Chapter 1 to solve recurrences in closed form. For example,if a,,is equal to a constant plus a multiple of n,the sum- recurrence (2.6)takes the following general form: R0=0X; (2.7) Rn =Rn-1+B+Yn,for n >0. Proceeding as in Chapter 1,we find R1=+B+Y,R2=+28+3y,and so on;in general the solution can be written in the form Rn=A(n)+B(n)B+C(n)Y, (2.8)
2.1 NOTATION 25 convention to write the sum of reciprocal primes $ N as x[p prime1 [P < N 1 /P , P there’s no problem of division by zero when p = 0, because our convention tells us that [O prime] [O < Nl/O = 0. Let’s sum up what we’ve discussed so far about sums. There are two good ways to express a sum of terms: One way uses ‘. . .‘, the other uses ‘ t ‘. The three-dots form often suggests useful manipulations, particularly the combination of adjacent terms, since we might be able to spot a simplifying pattern if we let the whole sum hang out before our eyes. But too much detail can also be overwhelming. Sigma-notation is compact, impressive to family . . and it’s less and friends, and often suggestive of manipulations that are not obvious in likely to lose points on an exam for three-dots form. When we work with Sigma-notation, zero terms are not “lack of rigor.” generally harmful; in fact, zeros often make t-manipulation easier. 2.2 SUMS AND RECURRENCES OK, we understand now how to express sums with fancy notation. But how does a person actually go about finding the value of a sum? One way is to observe that there’s an intimate relation between sums and recurrences. The sum (Think of S, as is equivalent to the recurrence not just a single number, but as a sequence defined for SO = ao; all n 3 0 .) S, = S-1 + a,, for n > 0. (2.6) Therefore we can evaluate sums in closed form by using the methods we learned in Chapter 1 to solve recurrences in closed form. For example, if a,, is equal to a constant plus a multiple of n, the sumrecurrence (2.6) takes the following general form: Ro=cx; R,=R,-l+B+yn, for n > 0. Proceeding as in Chapter 1, we find RI = a + fi + y, Rz = OL + 26 + 37, and so on; in general the solution can be written in the form R, = A(n) OL + B(n) S + C(n)y , (2.8)