Math 116: Final Exam Study Guide Chapter 4

Chapter 4: Recurrence Relations and Generating Functions
Exercise 1 Solve the recurrence relation:

    \[f(n)=6f(n-1)-11f(n-2)+6f(n-3)\]

where f(0)=2, f(1)=4 and f(2)=10. Hint: The roots of the characteristic polynomial are rational. The characteristic polynomial is \text{ch}(t)=t^3-6t^2+11t-6. Using the Rational Root Test, we obtain that the roots are t=1, t=2, and t=3. The roots of the polynomial are unique, thus the general solution is of the form:

    \[f(n)=c_1(1)^n+c_2(2)^n + c_3(3)^n\]

Therefore, by plugging into the initial conditions f(0)=2, f(1)=4 and f(2)=10, we obtain the system of linear equations:

    \begin{align*} 2&=c_1+c_2+c_3 \\ 4&=c_1+2c_2+3c_3 \\ 10&= c_1+4c_2+9c_3 \end{align*}

The solutions to this system of linear equations is c_1=1, c_2=0 and c_3=1. Therefore, the recurrence relation is given by f(n)=1+3^n.
Exercise 2 Find the general solution to the following recurrence relation.

    \[f(n)=3f(n-2)+2f(n-3)\]

Hint: The roots of the characteristic polynomial are rational. The characteristic polynomial is \text{ch}(t)=t^3-3t-2. Using the Rational Root Test, we obtain that the roots are t=-1 (with multiplicity 2) and t=2 (with multiplicity 1). Therefore, The general solution is of the form:

    \[f(n)=c_1(-1)^n+c_2n(-1)^n+c_3(2)^n\]

Exercise 3 Suppose each of the following permutations are in S_5. Determine which of the following permutations are derangements.
  1. (1\;2\;3\;4\;5)
  2. (1\;2\;3)(4\;5)
  3. (1\;3)(2\;4)
  4. (1\;5\;2\;3\;4)(3\;2)
 (a) (1\;2\;3\;4\;5) is a derangement since i \mapsto i+1 for i\not=5 and 5 \mapsto 1.
(b) (1\;2\;3)(4\;5) is a derangement since 1\mapsto 2, 2\mapsto 3, 3\mapsto 1, 4\mapsto 5 and 5\mapsto 4.
(c) (1\;3)(2\;4) is not a derangement since 5\mapsto 5.
(d) (1\;5\;2\;3\;4)(3\;2) = (1\;4)(1\;3)(1\;2)(1\;5)(3\;2)=(1\;5\;2\;4). Therefore, 3\mapsto 3. Therefore, it is not a derangement.