Homework Assignment #6

To solve non-homogeneous linear recurrence relations with constant coefficients and with initial conditions.

Show all work. i.e., justify your answers.

• Part II (Section 2.2) exercises in the Recurrence Relations notes.
  • You may need to use Gaussian elimination to help you solve multiple equations in multiple unknowns. You may do so by hand or with automated assistance. Whatever method you use, make it clear what you did.

Find the general and specific closed-form solutions for the analysis of the Towers of Hanoi algorithm using the method of recurrence relations: $t_n - 2 t_{n-1} = 1$ and $t_1 = 1$