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

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!

\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$$

• I see it now. Thanks! Just to clarify... can the top part (9-3 X 1) of this be used on all similar cases? (adjusting the numbers accordingly of course) – Tejava Oct 5 '15 at 0:53
• Yes. In general if the equations are of the form $$ax+by=c \\ dx+ey=f$$ you can multiply the first one entirely by $d$, the second by $a$ to get $$adx+bdy=cd \\ adx+aey=af$$ then subtract them to eliminate $x$. – BigbearZzz Oct 5 '15 at 1:08

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}.$$