Select the correct recurrence relation for Tower of Hanoi?ans.T(n)= 2T(n-2)+2T(n)= 2T(n-1)+1T(n)= 2T(n-1)+2T(n)= 2T(n)+1

Select the correct recurrence relation for Tower of Hanoi?

The recurrence T(n) = 2T(n-1) + n, for n≥2 and T(1) = 1 evaluates to

Consider this recurrence relation: T(1) = 1 T(2) = 1 T(n) = 4 T(n-2) + 2n2 for n>2 The Master Theorem tells us Group of answer choices

The tower of Hanoi is a famous puzzle where we have three rods and N disks. The objective of the puzzle is to move the entire stack to another rod. You are given the number of discs N. Initially, these discs are in the rod 1. You need to write a java program to print all the steps of discs movement so that all the discs reach the 3rd rod. Also, you need to find the total moves and present the output as follows. Let the solution for the problem be a recursive solution.Note: The discs are arranged such that the top disc is numbered 1 and the bottom-most disc is numbered N. Also, all the discs have different sizes and a bigger disc cannot be put on the top of a smaller disc. Input format :The line of input indicates the number of disks.Output format :Refer to the sample output for the output format.Sample test cases :Input 1 :3Output 1 :Move disk 1 from rod A to rod CMove disk 2 from rod A to rod BMove disk 1 from rod C to rod BMove disk 3 from rod A to rod CMove disk 1 from rod B to rod AMove disk 2 from rod B to rod CMove disk 1 from rod A to rod CTotal steps: 7

The recurrence relation T(n) = T(n-1) + 2 is given by, where n > 0 and T(0) = 5.