CPSC 170 Lab 8: Solving Recurrences

1. T(1) = 1
   T(n) = 1 + 2*T(n/2)

2. T(1) = 1
   T(n) = n + 2*T(n/2)

3. S(1) = 1
   S(n) = 1 + 3*S(n-1)

   Hint: 1 + 3 + 9 + ... + 3^n-1 = (3ⁿ-1)/2

4. Recall the Towers of Hanoi problem that we discussed in class. Given 3 needles and n graduated disks on one of the needles, the goal is to move all of the disks from one needle to another subject to the following rules:
   • Only one disk can be moved at a time.
   • A larger disk can never be placed on top of a smaller disk.

   If M(n) is the number of moves required to move n disks from one needle to another under the rules above,

   1. Write a recurrence relation and initial condition for M.

   2. Use the expand-guess-verify method to find a closed form solution for M.