4. Applications of Recurrence Relations (4 points) (1) (0.5 points) Count the number of length 2 bit strings that start and end (2) (0.5 points) Count the number of length 3 bit strings that start and end (3) (1.5 points) Find a recurrence relation for the number length n bit strings (4) (1.5 points) Use this recurrence relation to find the number of permuta- in 1 in 1 that start and end in 1 (where n 2 2) tions of a set with n elements using the expansion method. Reminder: We used expansion method in class to generate a guess for the number of moves in the Towers of Hanoi