# 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.

• Sounds about right. Apr 12 '17 at 21:44
• @IvanNeretin thanks! Apr 12 '17 at 21:46
• Very good. continue. Apr 12 '17 at 22:11
• @Jamie here is an other method. Apr 12 '17 at 22:26

Put $a_n=3^nb_n$.

then

$$3^nb_n=2.3^nb_{n-1}-3^nb_{n-2}$$

or

$b_n-b_{n-1}=b_{n-1}-b_{n-2}$ =constante $$=b_1-b_0=7-2=5$$

thus

$$b_n=5n+2$$

and

$$\boxed {a_n=3^n (5n+2)}$$

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*}