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 regions4 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 applica￾tions 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 alco￾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; 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