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 successfullyYeah, yeah. lseen that word before. Mathematical in￾duction 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