Problem set 6 Thus, with this strategy, the total number of moves required to move a stack of k(k+ 1)/2 disks is T(k)=2T(k-1)+2-1 (b)Find a closed form expression equal to Tk Solution. This is an inhomogenous linear equation. Let's begin by trying to find a particular solution. There is both an exponential term(2 )and a constant term,so we might guess something of the form a2+c a2k+c=2(a2k-1+c)+2-1 (a+1)2k+2c-1 0 Evidently, the constant term is c=l, but the exponential part is more complicated Our recipe says we should next try a particular solution of the form a2*+bk2*+ 24+bk2+1=2(a2-1+b(k-1)2k-1+1)+ a-b+1)2+bk2-1 Equating the coefficients of the 2 terms gives a =a-b+l, which implies b=1 Thus, a2*+k2+l is a particular solution for all a. As long as we have this degree of freedom, we might as well choose a so this solution is consistent with the boundary condition T1= l and be done Therefore the solution to the recurrence is Tk 1)2+1 (c) Approximately how many moves are required to solve the four-peg, n-disk Tow- ers of Hanoi puzzle as a function of n? Assume n is a triangular number. (For style points, make correct use of asymptotic notation. Solution. We have k=i(v8n+1-1)=v2n +O(1). So the number of moves required is(√i28 Problem Set 6 Thus, with this strategy, the total number of moves required to move a stack of k k(k + 1)/2 disks is T(k) = 2T(k − 1) + 2 − 1. (b) Find a closed form expression equal to Tk. Solution. This is an inhomogenous linear equation. Let’s begin by trying to find a particular solution. There is both an exponential term (2k) and a constant term, so we might guess something of the form a2k + c: k a2k + c = 2(a2k−1 + c) + 2 − 1 = (a + 1)2k + 2c − 1 ⇒ 0 = 2k + (c − 1) Evidently, the constant term is c = 1, but the exponential part is more complicated. Our recipe says we should next try a particular solution of the form a2k + bk2k + 1: k k a2k + bk2 + 1 = 2(a2k−1 + b(k − 1)2k−1 + 1) + 2 − 1 k = (a − b + 1)2k + bk2 − 1 Equating the coefficients of the 2k terms gives a = a − b + 1, which implies b = 1. Thus, a2k +k2k +1 is a particular solution for all a. As long as we have this degree of freedom, we might as well choose a so this solution is consistent with the boundary condition T1 = 1 and be done: a21 + 1 · 21 + 1 = 1 ⇒ a = −1 Therefore, the solution to the recurrence is Tk = (k − 1)2k + 1. (c) Approximately how many moves are required to solve the four­peg, n­disk Tow￾ers of Hanoi puzzle as a function of n? Assume n is a triangular number. (For style points, make correct use of asymptotic notation.) 1 Solution. We have k = 2 ( √8n + 1 − 1) = √2n + O(1). So the number of moves required is Θ(√n2 √2n)