<s>[INST] Solving Recurrence Relation $a_n=6a_{n-1} - 9a_{n-2}$ for $n\geqslant2$ So the problem is to solve this recurrence relation with the initial conditions $a_0 = 2, a_1 = 21$.
$a_n=6a_{n-1} - 9a_{n-2}$ for $n\geqslant2$
And also find the value of $a_{2016}.$
Here is my solution but I'm not entirely sure if it's correct. Was wondering if anyone can confirm what I did is valid or perhaps I made a mistake somewhere? Thanks in advance.

 [/INST] Generatingfunctionologically, define $A(z) = \sum_{n \ge 0} a_n z^n$, shift the recurrence by 2, multiply by $z^n$, sum over $n \ge 0$ and recognize resulting sums:
$\begin{align*}
  \sum_{n \ge 0} a_{n + 2} z^n
    &= 6 \sum_{n \ge 0} a_{n + 1} z^n - 9 \sum_{n \ge 0} a_n z^n \\
  \frac{A(z) - a_0 - a_1 z}{z^2}
    &= 6 \frac{A(z) - a_0}{z} - 9 A(z)
\end{align*}$
Solve for $A(z)$ with the given values of $a_0. a_1$, write as partial fractions:
$\begin{align*}
  A(z)
    &= \frac{2 + 9 z}{1 - 6 z + 9 z^2} \\
    &= \frac{5}{(1 - 3 z)^2} - \frac{3}{1 - 3 z}
\end{align*}$
Use the generalized binomial theorem:
$\begin{align*}
  (1 + x)^{-m}
    &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} x^n \\
    &= \sum_{n \ge 0} \binom{n + m - 1}{m - 1} x^n
\end{align*}$
extract the desired coefficient:
$\begin{align*}
  [z^n] A(z)
    &= 5 \cdot \binom{n + 2 - 1}{2 - 1} \cdot 3^n - 3 \cdot 3^n \\
    &= (5 n + 2) \cdot 3^n
\end{align*}$
</s>