Solve the recurrence relation: $a_n = 6a_{n-1} - 9a_{n-2}$

Question

Recurrence relation:$$a_n = 6a_{n-1} - 9a_{n-2}$$

Initial conditions:$$a_1 = 1, a_2 = 9$$

I am having a bit of trouble finishing off this problem. So far I have:

Assume:$$a_n = r^n$$

$$r^n = 6r^{n-1}-9r^{n-2}$$ $$r^2 = 6r - 9$$ $$r^2 - 6r + 9 = 0$$ $$(r-3)^2 = 0$$ This means: $$a_n = A(3)^n+B(n3^n)$$ $$a_1 = A3^1 + B((1)3^1) = 3A + 3B = 1$$ $$a_2 = A3^2 + B((2)3^2) = 9A + 18B = 9$$

From there I can't seem to combine the equations to find out what A and B are equal to correctly. Any help would be appreciated!

Answer 1

$$\begin{align} 9-3\times 1 &=a_2-3a_1 \\ 6 &= (9A+18B)-(9A+9B) \\ 6 &= 9B \end{align}$$ Therefore $B=\frac 23$, substitute this into $A_1$ yields $$ 3A=1-3B=1-3\times(\frac 23)=1-2=-1 $$ so that $A=-\frac 13$, thus $$ A=-\frac 13, B=\frac 23 $$

Answer 2

Another Method. Note that $$a_n - 3a_{n-1} = 3(a_{n-1} - 3 a_{n-2})$$ for $n\geq 2$, so the sequence $(b_n)_{n\geq 2}$ defined by $$ b_n = a_n - 3a_{n-1}\quad\text{and}\quad b_2 = a_2-3a_1 = 6 $$ is geometric with common ratio $r=3$. Thus, for all $n\geq 2$, we have $$b_n = b_2 r^{n-2} = 6\times 3^{n-2}.$$ Now, $$ \sum_{k=2}^{n-2} 3^k b_{n-k} = \sum_{k=2}^{n-2} (3^ka_{n-k} - 3^{k+1}a_{n-k-1}) $$ where the right side is a telescoping series. Simplifying we get $$ 6(n-1)\times 3^{n-2} = a_n - 3^{n-1}, $$ and finally $$ a_n = (2n-1)3^{n-1}. $$