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) the4 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 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 to 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: 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