6.042/18.] Mathematics for Computer Science March 17.2005 Srini devadas and Eric Lehman Lecture notes Recurrences Recursion-- breaking an object down into smaller objects of the same type-is a ma jor theme in mathematics and computer science. For example, in an induction proof we establish the truth of a statement P(n) from the truth of the statement P(n-1). In pro- gramming, a recursive algorithm solves a problem by applying itself to smaller instances of the problem. back on the mathematical side a recurrence equation describes the value of a function in terms of its value for smaller arguments. These various incarnations of re- cursion work together nicely. For example one might prove a recursive algorithm correct sing induction or analyze its running time using a recurrence equation In this lecture, well learn how to solve a family of recurrence equations, called"linear recurrences", that frequently arise in computer science and other disciplines 1 The Towers of hano In the Towers of Hanoi problem, there are three posts and seven disks of different sizes Each disk has a hole through the center so that it fits on a post at the start all seven disks are on post #1 as shown below. The disks are arranged by size so that the smallest is on top and the largest is on the bottom. The goal is to end up with all seven disks in the same order, but on a different post. This is not trivial because of two restrictions. First, the only ermitted action is removing the top disk from a post and dropping it onto another post Second, a larger disk can never lie above a smaller disk on any post. (These rules imply, for example, that it is no fair to pick up the whole stack of disks at once and then to drop them all on another post Post #1 Post #2 Post #3 It is not immediately clear that a solution to this problem exists; maybe the rules are so stringent that the disks cannot all be moved to another post!
6.042/18.062J Mathematics for Computer Science March 17, 2005 Srini Devadas and Eric Lehman Lecture Notes Recurrences Recursion— breaking an object down into smaller objects of the same type— is a major theme in mathematics and computer science. For example, in an induction proof we establish the truth of a statement P(n) from the truth of the statement P(n − 1). In programming, a recursive algorithm solves a problem by applying itself to smaller instances of the problem. Back on the mathematical side, a recurrence equation describes the value of a function in terms of its value for smaller arguments. These various incarnations of recursion work together nicely. For example one might prove a recursive algorithm correct using induction or analyze its running time using a recurrence equation. In this lecture, we’ll learn how to solve a family of recurrence equations, called “linear recurrences”, that frequently arise in computer science and other disciplines. 1 The Towers of Hanoi In the Towers of Hanoi problem, there are three posts and seven disks of different sizes. Each disk has a hole through the center so that it fits on a post. At the start, all seven disks are on post #1 as shown below. The disks are arranged by size so that the smallest is on top and the largest is on the bottom. The goal is to end up with all seven disks in the same order, but on a different post. This is not trivial because of two restrictions. First, the only permitted action is removing the top disk from a post and dropping it onto another post. Second, a larger disk can never lie above a smaller disk on any post. (These rules imply, for example, that it is no fair to pick up the whole stack of disks at once and then to drop them all on another post!) Post #1 Post #2 Post #3 It is not immediately clear that a solution to this problem exists; maybe the rules are so stringent that the disks cannot all be moved to another post!
Recurrences One approach to this problem is to consider a simpler variant with only three disks We can quickly exhaust the possibilities of this simpler puzzle and find a 7-move solution such as the one shown below. (The disks on each post are indicated by the numbers immediately to the right. Larger numbers correspond to larger disks. 2 31 This problem was invented in 1883 by the French mathematician Edouard Lucas. In his original account, there were 64 disks of solid gold. At the beginning of time, all 64 were placed on a single post, and monks were assigned the task of moving them to another post according to the rules described above. According to legend, when the monks complete their task the Tower will crumble and the world will end The questions we must answer are, Given sufficient time, can the monks succeed? and if so, How long until the world ends? and, most importantly, "Will this happer before the 6.042 final? 1.1 Finding a Recurrence The Towers of Hanoi problem can be solved recursively as follows. Let Tn be the min imum number of steps needed to move an n-disk tower from one post to another. For example, a bit of experimentation shows that Ti= l and T2=3. For 3 disks, the solution given above proves that T3 <7. We can generalize the approach used for 3 disks to the following recursive algorithm for n disks. Step 1. Apply this strategy recursively to move the top n- 1 disks from the first post to the third post This can be done in Tn-1
2 Recurrences One approach to this problem is to consider a simpler variant with only three disks. We can quickly exhaust the possibilities of this simpler puzzle and find a 7move solution such as the one shown below. (The disks on each post are indicated by the numbers immediately to the right. Larger numbers correspond to larger disks.) 1 2 3 ⇒ 2 3 1 ⇒ 3 1 2 ⇒ 3 1 2 ⇒ 3 1 2 ⇒ 1 3 2 ⇒ 1 2 3 ⇒ 1 2 3 This problem was invented in 1883 by the French mathematician Edouard Lucas. In his original account, there were 64 disks of solid gold. At the beginning of time, all 64 were placed on a single post, and monks were assigned the task of moving them to another post according to the rules described above. According to legend, when the monks complete their task, the Tower will crumble and the world will end! The questions we must answer are, “Given sufficient time, can the monks succeed?” and if so, “How long until the world ends?” and, most importantly, “Will this happen before the 6.042 final?” 1.1 Finding a Recurrence The Towers of Hanoi problem can be solved recursively as follows. Let Tn be the minimum number of steps needed to move an ndisk tower from one post to another. For example, a bit of experimentation shows that T1 = 1 and T2 = 3. For 3 disks, the solution given above proves that T3 ≤ 7. We can generalize the approach used for 3 disks to the following recursive algorithm for n disks. Step 1. Apply this strategy recursively to move the top n − 1 disks from the first post to the third post. This can be done in Tn−1 steps. 1 2 . . . n ⇒ n 1 2 . . . n −1
Step 2. Move the largest disk from the first post to the to the second post. This requires just I step n-1 Step 3. Recursively move the n-1 disks on the third post over to the second post. Again, Tn-I steps are required 2 Q. This algorithm shows that Tn, the number of steps required to move n disks to a dif- rent post, is at most 2Tn-1+ 1. We can use this fact to compute upper bounds on the number of steps required for various numbers of disks 13≤2·T2 74<2·T3+1 The algorithm described above answers our first question: given sufficient time, the monks will finish their task and end the world. which is a shame. After all that effort theyd probably want to smack a few high-fives and go out for burgers and ice cream, but nope--world's over. 1.2 A Lower bound for towers of hanoi We can not yet compute the exact number of steps that the monks need to move the 64 disks; we can only show an upper bound. Perhaps-having pondered the problem since the beginning of time-the monks have devised a better algorithm In fact, there is no better algorithm, and here is why. At some step, the monks must move the n-th disk from the first post to a different post. For this to happen, the n-1 smaller disks must all be stacked out of the way on the only remaining post. Arranging the n- l smaller disks this way requires at least Tn-1 moves. After the largest disk is moved at least another In-1 moves are required to pile the n- l smaller disks on top
Recurrences 3 Step 2. Move the largest disk from the first post to the to the second post. This requires just 1 step. 1 2 . . . ⇒ n n −1 n 1 2 . . . n −1 Step 3. Recursively move the n−1 disks on the third post over to the second post. Again, Tn−1 steps are required. 1 2 . . . ⇒ n n −1 1 2 . . . n This algorithm shows that Tn, the number of steps required to move n disks to a different post, is at most 2Tn−1 + 1. We can use this fact to compute upper bounds on the number of steps required for various numbers of disks: T3 ≤ 2 · T2 + 1 = 7 T4 ≤ 2 · T3 + 1 ≤ 15 The algorithm described above answers our first question: given sufficient time, the monks will finish their task and end the world. (Which is a shame. After all that effort they’d probably want to smack a few highfives and go out for burgers and ice cream, but nope— world’s over.) 1.2 A Lower Bound for Towers of Hanoi We can not yet compute the exact number of steps that the monks need to move the 64 disks; we can only show an upper bound. Perhaps— having pondered the problem since the beginning of time— the monks have devised a better algorithm. In fact, there is no better algorithm, and here is why. At some step, the monks must move the nth disk from the first post to a different post. For this to happen, the n − 1 smaller disks must all be stacked out of the way on the only remaining post. Arranging the n − 1 smaller disks this way requires at least Tn−1 moves. After the largest disk is moved, at least another Tn−1 moves are required to pile the n − 1 smaller disks on top
Recurrences This argument shows that the number of steps required is at least 2Tn-1+ 1. Since we gave an algorithm using exactly that number of steps, we now have a recurrence for Tn, the number of moves required to complete the tower of hanoi problem with n disks T1=1 Tn=21n-1+1 (forn≥2) can use this recurrence to conclude that T2=3, T3=7, T4=15, 1.3 Guess-and-Verify Computing T64 from the recurrence would require a lot of work. It would be nice to have a closed form expression for Tn, so that we could quickly compute the number of steps required to solve the Towers of Hanoi problem for any given number of disks.(For example, we might want to know how much sooner the world would end if the monks melted down one disk to purchase burgers and ice cream before the end of the world There are several different methods for solving recurrences. The simplest method is guess the solution and then to verify that the guess is correct, usually with an induction proof. This method is called guess-and-verify or"substitution". As a basis for a good guess, let's tabulate Tn for small values of n mI T 23 415 531 Based on this table, a natural guess is that Tn= 2n-1 Whenever you guess a solution to a recurrence, you should always verify it with a proof by induction or by some other technique; after all, your guess might be wrong. But why bother to verify in this case? After all, if were wrong, its not the end of the.no, lets check. Claim. If T1=1 Tn=2Tn-1+1 (forn≥2) the
4 Recurrences This argument shows that the number of steps required is at least 2Tn−1 + 1. Since we gave an algorithm using exactly that number of steps, we now have a recurrence for Tn, the number of moves required to complete the Tower of Hanoi problem with n disks: T1 = 1 Tn = 2Tn−1 + 1 (for n ≥ 2) We can use this recurrence to conclude that T2 = 3, T3 = 7, T4 = 15, . . .. 1.3 GuessandVerify Computing T64 from the recurrence would require a lot of work. It would be nice to have a closed form expression for Tn, so that we could quickly compute the number of steps required to solve the Towers of Hanoi problem for any given number of disks. (For example, we might want to know how much sooner the world would end if the monks melted down one disk to purchase burgers and ice cream before the end of the world.) There are several different methods for solving recurrences. The simplest method is to guess the solution and then to verify that the guess is correct, usually with an induction proof. This method is called guessandverify or “substitution”. As a basis for a good guess, let’s tabulate Tn for small values of n: n 1 1 2 3 3 7 4 15 5 31 6 63 Tn n Based on this table, a natural guess is that Tn = 2 − 1. Whenever you guess a solution to a recurrence, you should always verify it with a proof by induction or by some other technique; after all, your guess might be wrong. (But why bother to verify in this case? After all, if we’re wrong, its not the end of the. . . no, let’s check.) Claim. If: T1 = 1 Tn = 2Tn−1 + 1 (for n ≥ 2) then: Tn = 2n − 1
R Proof. The proof is by induction on n. Let P(n) be the proposition that Tn=2n-1. Base case: P(1)is true because T1=1=2-1 Inductive step: Now we assume Tn=2n-1 to prove that T+1=2n+I-l, wherein>1 2Tn+1 2(2-1) 2n+1-1 The first equality is the recurrence relation, and the second equation follows by the as- sumption P(n). The last step is simplification Our guess is now verified. This shows, for example, that the 7-disk puzzle will require 2-1=127 moves to complete. We can also now resolve our remaining questions about the 64-disk puzzle. Since T64=204-l, the monks must complete more than 18 billion billion steps before the world ends. Better study for the final 2 Graduate Student Job Prospects In a new academic field (say, computer science), there are only so many faculty positions available in all the universities of the world. Initially, there were not enough qualified candidates, and many positions were unfilled. But, over time, new graduates are filling the positions, making job prospects for later computer science students ever more bleak Worse, the increasing number of professors are able to train an increasing number of graduate students, causing positions to fill ever more rapidly. Eventually, the universities will be saturated; new computer science graduates will have no chance at an academic career. Our problem is to determine when the universities will stop hiring new computer science faculty and in particular, to answer the question, Are the 6.042 TAs doomed? Here are the details of the problem There are a total of N faculty positions available worldwide. This number never due to budgetary constraints Congress has passed a law forbidding forced retirement in universities, and no one will retire voluntarily.(This is true and a problem! ) In our analysis, therefore, once a faculty position is filled, it never opens up again Each year, every professor trains exactly 1 student who will go on to become a pro- fessor the following year. The only exception is that first year professors do not train students; they are too busy publishing teaching, getting grants, and serving on committees In year 0, there are no computer science professors in the world. In year 1, the first professor is hired
Recurrences 5 n Proof. The proof is by induction on n. Let P(n) be the proposition that Tn = 2 − 1. 1 Base case: P(1) is true because T1 = 1 = 2 − 1. Inductive step: Now we assume Tn = 2n − 1 to prove that Tn+1 = 2n+1 − 1, where n ≥ 1. Tn+1 = 2Tn + 1 = 2(2n − 1) + 1 = 2n+1 − 1 The first equality is the recurrence relation, and the second equation follows by the assumption P(n). The last step is simplification. Our guess is now verified. This shows, for example, that the 7disk puzzle will require 27 − 1 = 127 moves to complete. We can also now resolve our remaining questions about the 64disk puzzle. Since T64 = 264 − 1, the monks must complete more than 18 billion billion steps before the world ends. Better study for the final. 2 Graduate Student Job Prospects In a new academic field (say, computer science), there are only so many faculty positions available in all the universities of the world. Initially, there were not enough qualified candidates, and many positions were unfilled. But, over time, new graduates are filling the positions, making job prospects for later computer science students ever more bleak. Worse, the increasing number of professors are able to train an increasing number of graduate students, causing positions to fill ever more rapidly. Eventually, the universities will be saturated; new computer science graduates will have no chance at an academic career. Our problem is to determine when the universities will stop hiring new computer science faculty and, in particular, to answer the question, “Are the 6.042 TAs doomed?” Here are the details of the problem. • There are a total of N faculty positions available worldwide. This number never changes due to budgetary constraints. • Congress has passed a law forbidding forced retirement in universities, and no one will retire voluntarily. (This is true and a problem!) In our analysis, therefore, once a faculty position is filled, it never opens up again. • Each year, every professor trains exactly 1 student who will go on to become a professor the following year. The only exception is that first year professors do not train students; they are too busy publishing, teaching, getting grants, and serving on committees. • In year 0, there are no computer science professors in the world. In year 1, the first professor is hired