6 RECURRENT PROBLEMS through any of the existing intersection points (hence it intersects them all in different places).The recurrence is therefore L0=1; Ln Ln-1+n, for n>0. (1.4) The known values of L1,L2,and L3 check perfectly here,so we'll buy this. Now we need a closed-form solution.We could play the guessing game again,but 1,2,4,7,11,16,...doesn't look familiar;so let's try another tack.We can often understand a recurrence by "unfolding"or "unwinding" it all the way to the end,as follows: Ln=Ln-1+n =Ln-2+(n-1)+n Unfolding? =Ln-3+(n-2)+(n-1)+n Id call this “pluggingin." =L0+1+2+.+(nm2)+(n-1)+n =1+Sm,where Sn=1+2+3+.,+(n-1)+n. In other words,Ln is one more than the sum Sn of the first n positive integers. The quantity Sn pops up now and again,so it's worth making a table of small values.Then we might recognize such numbers more easily when we see them the next time: n1234567891011121314 Sn13610152128364555667891105 These values are also called the triangular numbers,because Sn is the number of bowling pins in an n-row triangular array.For example,the usual four-row array has S4=10 pins. To evaluate S we can use a trick that Gauss reportedly came up with in 1786,when he was nine years old [73](see also Euler [92,part 1,8415]): It seems a lot of stuff is attributed Sn=1+2+3+..+(n-1)+n to Gauss- either he was really +Sn=n+(n-l)+(n-2)+,+2+1 smart or he had a 2Sn=(n+1)+(n+1)+(n+1)+…+(n+1)+(n+1) great press agent. Maybe he just We merely add Sn to its reversal,so that each of the n columns on the right had a magnetic personality. sums to n 1.Simplifying, Sn =n(n+1) 2, forn≥0. (1.5)
6 RECURRENT PROBLEMS through any of the existing intersection points (hence it intersects them all in different places). The recurrence is therefore Lo = 1; L, = L,-l +n, for n > 0. (1.4) The known values of L1 , Lz, and L3 check perfectly here, so we’ll buy this. Now we need a closed-form solution. We could play the guessing game again, but 1, 2, 4, 7, 11, 16, . . . doesn’t look familiar; so let’s try another tack. We can often understand a recurrence by “unfolding” or “unwinding” it all the way to the end, as follows: L, = L,_j + n = L,-z+(n-l)+n = LnP3 + (n - 2) + (n - 1) + n Unfolding? I’d call this “plugging in.” = Lo+1 +2+... + (n - 2) + (n - 1) + n = 1 + s,, where S, = 1 + 2 + 3 + . . + (n - 1) + n. In other words, L, is one more than the sum S, of the first n positive integers. The quantity S, pops up now and again, so it’s worth making a table of small values. Then we might recognize such numbers more easily when we see them the next time: n 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 S, 1 3 6 1 0 1 5 21 2 8 3 6 4 5 5 5 6 6 7 8 91 105 These values are also called the triangular numbers, because S, is the number of bowling pins in an n-row triangular array. For example, the usual four-row array ‘*:::*’ has Sq = 10 pins. To evaluate S, we can use a trick that Gauss reportedly came up with in 1786, when he was nine years old [73] (see also Euler [92, part 1, $4151): It seems a lot of stuff is attributed s,= 1 + 2 + 3 +...+ (n-l) + n to Gausseither he was really +Sn= n + (n-l) + (n-2) + ... + 2 + 1 smart or he had a 2S, = (n+l) + (n+l) + (n+l) +...+ (n+1) + (n+l) great press agent. Maybe he just We merely add S, to its reversal, so that each of the n columns on the right sums to n + 1. Simplifying, ~~~s~n~,!~etic s _ n(n+l) n- 2 ’ for n 3 0. (1.5)
1.2 LINES IN THE PLANE 7 Actually Gauss is OK,we have our solution: often called the greatest mathe- matician of all time. Ln n(n+1) 3 +1, forn≥0. (1.6) So it's nice to be able to understand at least one of his As experts,we might be satisfied with this derivation and consider it discoveries. a proof,even though we waved our hands a bit when doing the unfolding and reflecting.But students of mathematics should be able to meet stricter standards;so it's a good idea to construct a rigorous proof by induction.The key induction step is Ln=Ln-1+n=(3(n-1)n+1)+n=n(n+1)+1. Now there can be no doubt about the closed form (1.6). When in doubt, Incidentally we've been talking about "closed forms"without explic- look at the words. itly saying what we mean.Usually it's pretty clear.Recurrences like (1.1) Why is it“closed,” as opposed to and (1.4)are not in closed form-they express a quantity in terms of itself; “open"？What but solutions like (1.2)and (1.6)are.Sums like 1 +2 +..n are not in image does it bring closed form-they cheat by using...';but expressions like n(n+1)/2 are. to mind? Answer:The equa We could give a rough definition like this:An expression for a quantity f(n) tion is "closed not is in closed form if we can compute it using at most a fixed number of"well defined in terms of known"standard operations,independent of n.For example,2n-1 and itself-not leading to recurrence.The n(n+1)/2 are closed forms because they involve only addition,subtraction, case is“dosed'”-it multiplication,division,and exponentiation,in explicit ways. won't happen again. The total number of simple closed forms is limited,and there are recur- Metaphors are the rences that don't have simple closed forms.When such recurrences turn out key. to be important,because they arise repeatedly,we add new operations to our repertoire;this can greatly extend the range of problems solvable in "simple" closed form.For example,the product of the first n integers,n!,has proved to be so important that we now consider it a basic operation.The formula n!'is therefore in closed form,although its equivalent '1.2.....n'is not. And now,briefly,a variation of the lines-in-the-plane problem:Suppose that instead of straight lines we use bent lines,each containing one "zig!' s“zig”a technical What is the maximum number Zn of regions determined by n such bent lines term? in the plane?We might expect Zn to be about twice as big as Ln,or maybe three times as big.Let's see: Z1=2 Z2=7
Actually Gauss is often called the greatest mathematician of all time. So it’s nice to be able to understand at least one of his discoveries. When in doubt, look at the words. Why is it Vlosed,” as opposed to L’open”? What image does it bring to mind? Answer: The equation is “closed ” not defined in ter;s of itself-not leading to recurrence. The case is “closed” -it won’t happen again. Metaphors are the key. Is “zig” a technical term? 1.2 LINES IN THE PLANE 7 OK, we have our solution: L n = n(n+‘) $1 2 ) for n 3 0. (1.6) As experts, we might be satisfied with this derivation and consider it a proof, even though we waved our hands a bit when doing the unfolding and reflecting. But students of mathematics should be able to meet stricter standards; so it’s a good idea to construct a rigorous proof by induction. The key induction step is L, = L,-lfn = (t(n-l)n+l)+n = tn(n+l)+l. Now there can be no doubt about the,closed form (1.6). Incidentally we’ve been talking about “closed forms” without explicitly saying what we mean. Usually it’s pretty clear. Recurrences like (1.1) and (1.4) are not in closed form- they express a quantity in terms of itself; but solutions like (1.2) and (1.6) are. Sums like 1 + 2 + . . . + n are not in closed form- they cheat by using ’ . . . ‘; but expressions like n(n + 1)/2 are. We could give a rough definition like this: An expression for a quantity f(n) is in closed form if we can compute it using at most a fixed number of “well known” standard operations, independent of n. For example, 2” - 1 and n(n + 1)/2 are closed forms because they involve only addition, subtraction, multiplication, division, and exponentiation, in explicit ways. The total number of simple closed forms is limited, and there are recurrences that don’t have simple closed forms. When such recurrences turn out to be important, because they arise repeatedly, we add new operations to our repertoire; this can greatly extend the range of problems solvable in “simple” closed form. For example, the product of the first n integers, n!, has proved to be so important that we now consider it a basic operation. The formula ‘n!’ is therefore in closed form, although its equivalent ‘1 .2.. . . .n’ is not. And now, briefly, a variation of the lines-in-the-plane problem: Suppose that instead of straight lines we use bent lines, each containing one “zig!’ What is the maximum number Z, of regions determined by n such bent lines in the plane? We might expect Z, to be about twice as big as L,, or maybe three times as big. Let’s see: < 2 1
8 RECURRENT PROBLEMS From these small cases,and after a little thought,we realize that a bent .and a little line is like two straight lines except that regions merge when the"two"lines afterthought... don't extend past their intersection point. Regions 2,3,and 4,which would be distinct with two lines,become a single region when there's a bent line;we lose two regions.However,if we arrange things properly-the zig point must lie "beyond"the intersections with the other lines-that's all we lose;that is,we lose only two regions per line.Thus Exercise 18 has the details. Zn=L2m-2n=2n(2n+1)/2+1-2n =2n2-n+1,forn≥0. (1.7) Comparing the closed forms (1.6)and (1.7),we find that for large n, Ln心n2, Zn 2n2; so we get about four times as many regions with bent lines as with straight lines.(In later chapters we'll be discussing how to analyze the approximate behavior of integer functions when n is large.) 1.3 THE JOSEPHUS PROBLEM Our final introductory example is a variant of an ancient problem (Ahrens 5,vol. named for Flavius Josephus,a famous historian of the first century.Legend and Herstein and Kaplansky (156] has it that Josephus wouldn't have lived to become famous without his math- discuss the interest- ematical talents.During the Jewish-Roman war,he was among a band of 41 ing history of this Jewish rebels trapped in a cave by the Romans.Preferring suicide to capture, problem.Josephus the rebels decided to form a circle and,proceeding around it,to kill every himself(166]is a bit vague.) third remaining person until no one was left.But Josephus,along with an unindicted co-conspirator,wanted none of this suicide nonsense,so he quickly calculated where he and his friend should stand in the vicious circle. thereby saving In our variation,we start with n people numbered I to n around a circle, his tale for us to hear. and we eliminate every second remaining person until only one survives.For
8 RECURRENT PROBLEMS From these small cases, and after a little thought, we realize that a bent . . and a little line is like two straight lines except that regions merge when the “two” lines afterthought... don’t extend past their intersection point. . 4 ’ . . 3 .::: 1 . . . . . (=: 2 Regions 2, 3, and 4, which would be distinct with two lines, become a single region when there’s a bent line; we lose two regions. However, if we arrange things properly-the zig point must lie “beyond” the intersections with the other lines-that’s all we lose; that is, we lose only two regions per line. Thus Exercise 18 has the details. Z, = Lz,-2n = 2n(2n+1)/2+1-2n = 2n2-n+l, for n 3 0. (1.7) Comparing the closed forms (1.6) and (1.7), we find that for large n, L, N in’, Z, - 2n2; so we get about four times as many regions with bent lines as with straight lines. (In later chapters we’ll be discussing how to analyze the approximate behavior of integer functions when n is large.) 1.3 THE JOSEPHUS PROBLEM Our final introductory example is a variant of an ancient problem named for Flavius Josephus, a famous historian of the first century. Legend has it that Josephus wouldn’t have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle. In our variation, we start with n people numbered 1 to n around a circle, and we eliminate every second remaining person until only one survives. For (Ahrens 15, vol. 2 1 and Herstein and Kaplansky 11561 discuss the interesting history of this problem. Josephus himself [ISS] is a bit vague.) . thereby saving his tale for us to hear
1.3 THE JOSEPHUS PROBLEM 9 example,here's the starting configuration for n 10: 6 The elimination order is 2,4,6,8,10,3,7,1,9,so 5 survives.The problem: Here's a case where Determine the survivor's number,J(n). n=0 makes no We just saw that J(10)=5.We might conjecture that J(n)=n/2 when sense. n is even;and the case n =2 supports the conjecture:J(2)=1.But a few other small cases dissuade us-the conjecture fails for n =4 and n =6. n123456 J(m)113135 Even so,a bad It's back to the drawing board;let's try to make a better guess.Hmmm... guess isn't a waste J(n)always seems to be odd.And in fact,there's a good reason for this:The of time,because it gets us involved in first trip around the circle eliminates all the even numbers.Furthermore,if the problem. n itself is an even number,we arrive at a situation similar to what we began with,except that there are only half as many people,and their numbers have changed. So let's suppose that we have 2n people originally.After the first go- round,we're left with 2n-1 2n-3 5 and 3 will be the next to go.This is just like starting out with n people,except This is the tricky that each person's number has been doubled and decreased by 1.That is, part:We have J〔2m)= 2n)=2Jn)-1, forn≥1 newnumber(J(n)), where newnumber(k)= We can now go quickly to large n.For example,we know that J(10)=5,so 2k-1. J20)=2J10)1=2.5-1=9 Similarly J(40)=17,and we can deduce that J(5.2m)=2m+1+1
1.3 THE JOSEPHUS PROBLEM 9 Here’s a case where n = 0 makes no sense. Even so, a bad guess isn’t a waste of time, because it gets us involved in the problem. This is the tricky part: We have J(2n) = newnumber(J(n)), where newnumber( k) = 2k-1. example, here’s the starting configuration for n = 10: 9 3 8 4 The elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9, so 5 survives. The problem: Determine the survivor’s number, J(n). We just saw that J(l0) = 5. We might conjecture that J(n) = n/2 when n is even; and the case n = 2 supports the conjecture: J(2) = 1. But a few other small cases dissuade us-the conjecture fails for n = 4 and n = 6. n 123456 J(n) 1 1 3 1 3 5 It’s back to the drawing board; let’s try to make a better guess. Hmmm . . . J(n) always seems to be odd. And in fact, there’s a good reason for this: The first trip around the circle eliminates all the even numbers. Furthermore, if n itself is an even number, we arrive at a situation similar to what we began with, except that there are only half as many people, and their numbers have changed. So let’s suppose that we have 2n people originally. After the first goround, we’re left with 2n-1 '3 2n-3 0 t 5 7 and 3 will be the next to go. This is just like starting out with n people, except that each person’s number has been doubled and decreased by 1. That is, JVn) = 2J(n) - 1 , for n 3 1 We can now go quickly to large n. For example, we know that J( 10) = 5, so J(20) = 2J(lO) - 1 = 2.5- 1 = 9 Similarly J(40) = 17, and we can deduce that J(5.2”‘) = 2m+’ + 1
10 RECURRENT PROBLEMS But what about the odd case?With 2n 1 people,it turns out that Odd case?Hey, person number I is wiped out just after person number 2n,and we're left with leave my brother out of it. 2n+1 35 2n-1 Again we almost have the original situation with n people,but this time their numbers are doubled and increased by 1.Thus J(2m+1)=2Jn)+1, forn≥1. Combining these equations with J(1)=1 gives us a recurrence that defines J in all cases: (1)=1; J(2n)=2Jn)-1 forn≥l (1.8) J(2m+1)=2Jn)+1, forn≥l. Instead of getting J(n)from J(n-1),this recurrence is much more"efficient," because it reduces n by a factor of 2 or more each time it's applied.We could compute J(1000000),say,with only 19 applications of (1.8).But still,we seck a closed form,because that will be even quicker and more informative.After all,this is a matter of life or death. Our recurrence makes it possible to build a table of small values very quickly.Perhaps we'll be able to spot a pattern and guess the answer. n12356791011121314156 Jm131357135791113151 Voila!It seems we can group by powers of 2 (marked by vertical lines in the table);J(n is always 1 at the beginning of a group and it increases by 2 within a group.So if we write n in the form n =2"+1,where 2m is the largest power of 2 not exceeding n and where t is what's left,the solution to our recumence seems to be J2m+l)=2L+1,form≥0and0≤l<2m. (1.9 Notice that if2”≤n<2m+l,the remainder=nw2”satisfies0≤L< 2m+1-2m=2m) We must now prove(1.9).As in the past we use induction,but this time the induction is on m.When m =0 we must have l=0;thus the basis of
10 RECURRENT PROBLEMS But what about the odd case? With 2n + 1 people, it turns out that Odd case? Hey, person number 1 is wiped out just after person number 2n, and we’re left with leave mY brother out of it. 2n+l 3 5 2n-1 0 t 7 9 Again we almost have the original situation with n people, but this time their numbers are doubled and increased by 1. Thus J(2n-t 1) = 2J(n) + 1 , for n > 1. Combining these equations with J( 1) = 1 gives us a recurrence that defines J in all cases: J(1) = 1 ; J(2n) = 2J(n) - 1 , for n > 1; (1.8) J(2n + 1) = 2J(n) + 1 , for n 3 1 . Instead of getting J(n) from J(n- l), this recurrence is much more “efficient,” because it reduces n by a factor of 2 or more each time it’s applied. We could compute J( lOOOOOO), say, with only 19 applications of (1.8). But still, we seek a closed form, because that will be even quicker and more informative. After all, this is a matter of life or death. Our recurrence makes it possible to build a table of small values very quickly. Perhaps we’ll be able to spot a pattern and guess the answer. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 Voild! It seems we can group by powers of 2 (marked by vertical lines in the table); J( n is always ) 1 at the beginning of a group and it increases by 2 within a group. So if we write n in the form n = 2” + 1, where 2m is the largest power of 2 not exceeding n and where 1 is what’s left, the solution to our recurrence seems to be J(2” + L) = 2Lf 1 , for m 3 0 and 0 6 1< 2m. (1.9) (Notice that if 2” 6 n < 2 mt’ , the remainder 1 = n - 2 ” satisfies 0 6 1 < 2m+’ - 2m = I”.) We must now prove (1.9). As in the past we use induction, but this time the induction is on m. When m = 0 we must have 1 = 0; thus the basis of