1 Recurrent Problems THIS CHAPTER EXPLORES three sample problems that give a feel for what's to come.They have two traits in common:They've all been investi- gated repeatedly by mathematicians;and their solutions all use the idea of recurrence,in which the solution to each problem depends on the solutions to smaller instances of the same problem. 1.1 THE TOWER OF HANOI Let's look first at a neat little puzzle called the Tower of Hanoi, invented by the French mathematician Edouard Lucas in 1883.We are given Raise your hand a tower of eight disks,initially stacked in decreasing size on one of three pegs: if you've never seen this OK,the rest of you can cut to equation (1.1). The objective is to transfer the entire tower to one of the other pegs,moving only one disk at a time and never moving a larger one onto a smaller. Lucas 208furnished his toy with a romantic legend about a much larger Gold-wow. Tower of Brahma,which supposedly has 64 disks of pure gold resting on three Are our disks made diamond needles.At the beginning of time,he said,God placed these golden of concrete? disks on the first needle and ordained that a group of priests should transfer them to the third,according to the rules above.The priests reportedly work day and night at their task.When they finish,the Tower will crumble and the world will end
Recurrent Problems THIS CHAPTER EXPLORES three sample problems that give a feel for what’s to come. They have two traits in common: They’ve all been investigated repeatedly by mathematicians; and their solutions all use the idea of recuvexe, in which the solution to each problem depends on the solutions to smaller instances of the same problem. Raise your hand if you’ve never seen this. OK, the rest of you can cut to equation (1.1). 1.1 THE TOWER OF HANOI Let’s look first at a neat little puzzle called the Tower of Hanoi, invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs: The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller. Lucas [208] furnished his toy with a romantic legend about a much larger Gold -wow. Tower of Brahma, which supposedly has 64 disks of pure gold resting on three Are our disks made of concrete? diamond needles. At the beginning of time, he said, God placed these golden disks on the first needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end. 1
2 RECURRENT PROBLEMS It's not immediately obvious that the puzzle has a solution,but a little thought (or having seen the problem before)convinces us that it does.Now the question arises:What's the best we can do?That is,how many moves are necessary and sufficient to perform the task? The best way to tackle a question like this is to generalize it a bit.The Tower of Brahma has 64 disks and the Tower of Hanoi has 8;let's consider what happens if there are n disks. One advantage of this generalization is that we can scale the problem down even more.In fact,we'll see repeatedly in this book that it's advanta- geous to Loox ar sMLL cases first.It's easy to see how to transfer a tower that contains only one or two disks.And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation: NAME AND coNQueR.Let's say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucas's rules.Then T is obviously 1,and T2=3. We can also get another piece of data for free,by considering the smallest case of all:Clearly To =0,because no moves at all are needed to transfer a tower of n =0 disks!Smart mathematicians are not ashamed to think small, because general patterns are easier to perceive when the extreme cases are well understood (even when they are trivial). But now let's change our perspective and try to think big;how can we transfer a large tower?Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg,then move the third, then bring the other two onto it.This gives us a clue for transferring n disks in general:We first transfer the n -1 smallest to a different peg (requiring Tn-1 moves),then move the largest (requiring one move),and finally transfer the n-1 smallest back onto the largest (requiring another Tn-1 moves).Thus we can transfer n disks (for n >0)in at most 2Tn-1+1 moves: Tn 6 2Tn-1+1 for n 0. This formula usesinstead of(='because our construction proves only that 2Tn-1+1 moves suffice;we haven't shown that 2Tn-1+1 moves are necessary.A clever person might be able to think of a shortcut. But is there a better way?Actually no.At some point we must move the Most of the pub- largest disk.When we do,the n-1 smallest must be on a single peg,and it lished“solutions" has taken at least In-1 moves to put them there.We might move the largest to Lucas's problem, like the early one disk more than once,if we're not too alert.But after moving the largest disk of Allardice and for the last time,we must transfer the n-I smallest disks (which must again Fraser fail to ex- be on a single peg)back onto the largest;this too requires Tn-1moves.Hence plain why Tn must be≥2Tn1+1. Tn 3 2Tn-1+1,for n 0
2 RECURRENT PROBLEMS It’s not immediately obvious that the puzzle has a solution, but a little thought (or having seen the problem before) convinces us that it does. Now the question arises: What’s the best we can do? That is, how many moves are necessary and sufficient to perform the task? The best way to tackle a question like this is to generalize it a bit. The Tower of Brahma has 64 disks and the Tower of Hanoi has 8; let’s consider what happens if there are n disks. One advantage of this generalization is that we can scale the problem down even more. In fact, we’ll see repeatedly in this book that it’s advantageous to LOOK AT SMALL CASES first. It’s easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation: NAME AND CONQUER. Let’s say that T,, is the minimum number of moves that will transfer n disks from one peg to another under Lucas’s rules. Then Tl is obviously 1, and T2 = 3. We can also get another piece of data for free, by considering the smallest case of all: Clearly TO = 0, because no moves at all are needed to transfer a tower of n = 0 disks! Smart mathematicians are not ashamed to think small, because general patterns are easier to perceive when the extreme cases are well understood (even when they are trivial). But now let’s change our perspective and try to think big; how can we transfer a large tower? Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg, then move the third, then bring the other two onto it. This gives us a clue for transferring n disks in general: We first transfer the n - 1 smallest to a different peg (requiring T,-l moves), then move the largest (requiring one move), and finally transfer the n- 1 smallest back onto the largest (requiring another Tn..1 moves). Thus we can transfer n disks (for n > 0) in at most 2T,-, + 1 moves: T, 6 2Tn-1 + 1 , for n > 0. This formula uses ‘ < ’ instead of ‘ = ’ because our construction proves only that 2T+1 + 1 moves suffice; we haven’t shown that 2T,_, + 1 moves are necessary. A clever person might be able to think of a shortcut. But is there a better way? Actually no. At some point we must move the largest disk. When we do, the n - 1 smallest must be on a single peg, and it has taken at least T,_, moves to put them there. We might move the largest disk more than once, if we’re not too alert. But after moving the largest disk for the last time, we must transfer the n- 1 smallest disks (which must again be on a single peg) back onto the largest; this too requires T,- 1 moves. Hence Most of the published “solutions” to Lucas’s problem, like the early one of Allardice and Fraser [?I, fail to explain why T,, must be 3 2T,, 1+ 1. Tn 3 2Tn-1 + 1 , for n > 0
1.1 THE TOWER OF HANOI 3 These two inequalities,together with the trivial solution for n =0,yield To=0; (1.1) Tn=2Tn-1+1, for n>0. (Notice that these formulas are consistent with the known values 1=1 and T2 =3.Our experience with small cases has not only helped us to discover a general formula,it has also provided a convenient way to check that we haven't made a foolish error.Such checks will be especially valuable when we get into more complicated maneuvers in later chapters.) Yeah,yeah. A set of equalities like (1.1)is called a recurrence (a.k.a.recurrence I seen that word relation or recursion relation).It gives a boundary value and an equation for before. the general value in terms of earlier ones.Sometimes we refer to the general equation alone as a recurrence,although technically it needs a boundary value to be complete. The recurrence allows us to compute Tn for any n we like.But nobody really likes to compute from a recurrence,when n is large;it takes too long. The recurrence only gives indirect,"local"information.A solution to the recurrence would make us much happier.That is,we'd like a nice,neat, "closed form"for Tn that lets us compute it quickly,even for large n.With a closed form,we can understand what In really is. So how do we solve a recurrence?One way is to guess the correct solution, then to prove that our guess is correct.And our best hope for guessing the solution is to look (again)at small cases.So we compute,successively, T3=23+1=7;T4=27+1=15;T5=215+1=31;T6=2.31+1=63 Aha!It certainly looks as if Tn=2n-1,forn≥0. (1.2) At least this works for n s 6. Mathematical induction is a general way to prove that some statement about the integer n is true for all n>no.First we prove the statement when n has its smallest value,no;this is called the basis.Then we prove the statement for n no,assuming that it has already been proved for all values Mathematical in- between no and n-1,inclusive;this is called the induction.Such a proof duction proves that we can clinb as gives infinitely many results with only a finite amount of work. high as we like on Recurrences are ideally set up for mathematical induction.In our case, a ladder,by proving for example,(1.2)follows easily from (1.1):The basis is trivial,since To that we can clinb 20-1 =0.And the induction follows for n>0 if we assume that (1.)holds onto the bottom rung (the basis) when n is replaced by n1: and that from each rung we can climb Tm=2Tm,+1=2(2"1-1)+1=2"-1. up to the next one (the induction). Hence (1.2)holds for n as well.Good!Our quest for In has ended successfully
Yeah, yeah. lseen that word before. Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the induction). 1.1 THE TOWER OF HANOI 3 These two inequalities, together with the trivial solution for n = 0, yield To =O; T, = 2T+1 +l , for n > 0. (1.1) (Notice that these formulas are consistent with the known values TI = 1 and Tz = 3. Our experience with small cases has not only helped us to discover a general formula, it has also provided a convenient way to check that we haven’t made a foolish error. Such checks will be especially valuable when we get into more complicated maneuvers in later chapters.) A set of equalities like (1.1) is called a recurrence (a.k.a. recurrence relation or recursion relation). It gives a boundary value and an equation for the general value in terms of earlier ones. Sometimes we refer to the general equation alone as a recurrence, although technically it needs a boundary value to be complete. The recurrence allows us to compute T,, for any n we like. But nobody really likes to compute from a recurrence, when n is large; it takes too long. The recurrence only gives indirect, “local” information. A solution to the recurrence would make us much happier. That is, we’d like a nice, neat, “closed form” for T,, that lets us compute it quickly, even for large n. With a closed form, we can understand what T,, really is. So how do we solve a recurrence? One way is to guess the correct solution, then to prove that our guess is correct. And our best hope for guessing the solution is to look (again) at small cases. So we compute, successively, T~=2~3+1=7;T~=2~7+1=15;T~=2~15+1=31;T~=2~31+1=63. Aha! It certainly looks as if T, = 2n-1, for n 3 0. (1.2) At least this works for n < 6. Mathematical induction is a general way to prove that some statement about the integer n is true for all n 3 no. First we prove the statement when n has its smallest value, no; this is called the basis. Then we prove the statement for n > no, assuming that it has already been proved for all values between no and n - 1, inclusive; this is called the induction. Such a proof gives infinitely many results with only a finite amount of work. Recurrences are ideally set up for mathematical induction. In our case, for example, (1.2) follows easily from (1.1): The basis is trivial, since TO = 2’ - 1 = 0. And the induction follows for n > 0 if we assume that (1.2) holds when n is replaced by n - 1: T,, = 2T,, , $1 = 2(2 n l -l)+l = 2n-l. Hence (1.2) holds for n as well. Good! Our quest for T,, has ended successfully
4 RECURRENT PROBLEMS Of course the priests'task hasn't ended;they're still dutifully moving disks,and will be for a while,because for n =64 there are 264-1 moves (about 18 quintillion).Even at the impossible rate of one move per microsecond,they will need more than 5000 centuries to transfer the Tower of Brahma.Lucas's original puzzle is a bit more practical,It requires 28-1=255 moves,which takes about four minutes for the quick of hand. The Tower of Hanoi recurrence is typical of many that arise in applica- tions of all kinds.In finding a closed-form expression for some quantity of interest like Tn we go through three stages: 1 Look at small cases.This gives us insight into the problem and helps us in stages 2 and 3. 2 Find and prove a mathematical expression for the quantity of interest. What is a proof? For the Tower of Hanoi,this is the recurrence (1.1)that allows us,given "One half of one percent pure alco- the inclination,to compute Tn for any n. hol. 3 Find and prove a closed form for our mathematical expression.For the Tower of Hanoi,this is the recurrence solution(1.2). The third stage is the one we will concentrate on throughout this book.In fact,we'll frequently skip stages 1 and 2 entirely,because a mathematical expression will be given to us as a starting point.But even then,we'll be getting into subproblems whose solutions will take us through all three stages. Our analysis of the Tower of Hanoi led to the correct answer,but it required an "inductive leap";we relied on a lucky guess about the answer. One of the main objectives of this book is to explain how a person can solve recurrences without being clairvoyant.For example,we'll see that recurrence (1.1)can be simplified by adding 1 to both sides of the equations: To+1=1 Tn+1=2Tn-1+2, for n>0. Now if we let Un Tn +1,we have Interesting:We get rid of the +1in u0=1; (1.1）by adding,not (13）by subtracting Un 2Un-1, for n>0. It doesn't take genius to discover that the solution to this recurrence is just Un=2";hence Tn=2"-1.Even a computer could discover this. 1.2 LINES IN THE PLANE Our second sample problem has a more geometric flavor.How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?Or,more academically:What is the maximum number Ln of regions
4 RECURRENT PROBLEMS Of course the priests’ task hasn’t ended; they’re still dutifully moving disks, and will be for a while, because for n = 64 there are 264-l moves (about 18 quintillion). Even at the impossible rate of one move per microsecond, they will need more than 5000 centuries to transfer the Tower of Brahma. Lucas’s original puzzle is a bit more practical, It requires 28 - 1 = 255 moves, which takes about four minutes for the quick of hand. The Tower of Hanoi recurrence is typical of many that arise in applications of all kinds. In finding a closed-form expression for some quantity of interest like T,, we go through three stages: 1 Look at small cases. This gives us insight into the problem and helps us in stages 2 and 3. 2 Find and prove a mathematical expression for the quantity of interest. What is a proof? For the Tower of Hanoi, this is the recurrence (1.1) that allows us, given “One ha’fofone the inclination, to compute T,, for any n. percent pure alcohol. ” 3 Find and prove a closed form for our mathematical expression. For the Tower of Hanoi, this is the recurrence solution (1.2). The third stage is the one we will concentrate on throughout this book. In fact, we’ll frequently skip stages 1 and 2 entirely, because a mathematical expression will be given to us as a starting point. But even then, we’ll be getting into subproblems whose solutions will take us through all three stages. Our analysis of the Tower of Hanoi led to the correct answer, but it required an “inductive leap”; we relied on a lucky guess about the answer. One of the main objectives of this book is to explain how a person can solve recurrences without being clairvoyant. For example, we’ll see that recurrence (1.1) can be simplified by adding 1 to both sides of the equations: To + 1 = 1; Lsl =2T,-, +2, for n > 0. Now if we let U, = T,, + 1, we have uo = 1 ; u, = 2&-l, for n > 0. Interesting: We get rid of the +l in (1.1) by adding, not (1.3) by subtracting. It doesn’t take genius to discover that the solution to this recurrence is just U, = 2”; hence T, = 2” - 1. Even a computer could discover this. 1.2 LINES IN THE PLANE Our second sample problem has a more geometric flavor: How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? Or, more academically: What is the maximum number L, of regions
1.2 LINES IN THE PLANE 5 defined by n lines in the plane?This problem was first solved in 1826,by the (A pizza with Swiss Swiss mathematician Jacob Steiner 278]. cheese?) Again we start by looking at small cases,remembering to begin with the smallest of all.The plane with no lines has one region;with one line it has two regions;and with two lines it has four regions: 1 Lo=1 L1=2 L2=4 (Each line extends infinitely in both directions.) Sure,we think,Ln =2";of course!Adding a new line simply doubles the number of regions.Unfortunately this is wrong.We could achieve the doubling if the nth line would split each old region in two;certainly it can A region is convex split an old region in at most two pieces,since each old region is convex.(A if it includes all straight line can split a convex region into at most two new regions,which line segments be- tween any two of its will also be convex.)But when we add the third line-the thick one in the points.(That's not diagram below-we soon find that it can split at most three of the old regions, what my dictionary no matter how we've placed the first two lines: says,but it's what mathematicians believe.) 4a/ 1b 3a 4673b Thus L3=4 +3 =7 is the best we can do. And after some thought we realize the appropriate generalization.The nth line (for n >0)increases the number of regions by k if and only if it splits k of the old regions,and it splits k old regions if and only if it hits the previous lines in k-1 different places.Two lines can intersect in at most one point.Therefore the new line can intersect the n-1 old lines in at most n-1 different points,and we must have k <n.We have established the upper bound Ln≤Ln-1+n,forn>0. Furthermore it's easy to show by induction that we can achieve equality in this formula.We simply place the nth line in such a way that it's not parallel to any of the others (hence it intersects them all),and such that it doesn't go
1.2 LINES IN THE PLANE 5 (A pizza with Swiss cheese?) A region is convex if it includes all line segments between any two of its points. (That’s not what my dictionary says, but it’s what mathematicians believe.) defined by n lines in the plane? This problem was first solved in 1826, by the Swiss mathematician Jacob Steiner [278]. Again we start by looking at small cases, remembering to begin with the smallest of all. The plane with no lines has one region; with one line it has two regions; and with two lines it has four regions: (Each line extends infinitely in both directions.) Sure, we think, L, = 2”; of course! Adding a new line simply doubles the number of regions. Unfortunately this is wrong. We could achieve the doubling if the nth line would split each old region in two; certainly it can split an old region in at most two pieces, since each old region is convex. (A straight line can split a convex region into at most two new regions, which will also be convex.) But when we add the third line-the thick one in the diagram below- we soon find that it can split at most three of the old regions, no matter how we’ve placed the first two lines: Thus L3 = 4 + 3 = 7 is the best we can do. And after some thought we realize the appropriate generalization. The nth line (for n > 0) increases the number of regions by k if and only if it splits k of the old regions, and it splits k old regions if and only if it hits the previous lines in k- 1 different places. Two lines can intersect in at most one point. Therefore the new line can intersect the n- 1 old lines in at most n- 1 different points, and we must have k 6 n. We have established the upper bound L 6 L-1 +n, for n > 0. Furthermore it’s easy to show by induction that we can achieve equality in this formula. We simply place the nth line in such a way that it’s not parallel to any of the others (hence it intersects them all), and such that it doesn’t go