Show that a sequence $a_n$ is a solution of the given recurrence relation Show that the sequence $a_n=3^{n+4}$ is a solution of the recurrence relation $a_n=4a_{n-1}-3a_{n-2}$.
I'm stuck on this question as I'm having trouble figuring it out when $a_n=3^{n+4}$.
After substituting $3^{n+3}$ for both n's in $4a_{n-1}$ and $3a_{n-2}$, I have no idea where to go from there.
 A: Consider the right hand side of the relation: $4a_{n-1}-3a_{n-2}$.
Since $a_n=3^{n+4}=81\cdot 3^n$, we have $a_{n-1}=81\cdot 3^{n-1},a_{n-2}=81\cdot 3^{n-2}$.
Substitute that in the above term:
$$4\cdot (81\cdot 3^{n-1})-3\cdot (81\cdot 3^{n-2})$$
Taking out $81$ common and writing $4$ as $3+1$, the above transforms to
$$81(3\cdot 3^{n-1}+3^{n-1}-3^{n-1})$$
Now this is nothing but $81\cdot 3^n$ which in turn is equal to $a_n$.
Ta-da!
A: Solution
Using $Su_n=u_{n+1}$, the shift operator on sequences, we can write this relation as
$$
\begin{align}
0
&=\left(I-4S^{-1}+3S^{-2}\right)a_n\tag1\\
&=\underbrace{\left(I-S^{-1}\right)}_{c_11^n}\underbrace{\left(I-3S^{-1}\right)}_{c_33^n}\,a_n\tag2
\end{align}
$$
$\left(I-S^{-1}\right)a_n=0\phantom{3}$ has solutions of the form $c_11^n$ ($a_n-a_{n-1}=0$)
$\left(I-3S^{-1}\right)a_n=0$ has solutions of the form $c_33^n$ ($a_n-3a_{n-1}=0$)
Thus, the general solution to $(1)$ is $a_n=c_1+c_33^n$. Setting $c_1=0$ and $c_3=3^4$, we get your proposed solution.

Verification of the Given Solution
$$
\overbrace{3^{n+4}}^{a_n}=\overbrace{4\cdot3^{n+3}}^{4a_{n-1}}-\overbrace{3\cdot3^{n+2}}^{3a_{n=2}}\tag3
$$
$(3)$ follows from $3^4=4\cdot3^3-3\cdot3^2$
A: $$a_n=3^{n+4}=4\cdot3^{n+3}-3\cdot3^{n+2}$$
$$3\cdot 3^{n+3}=3^{n+3}(4-1)$$
$$3=4-1$$
$$3=3.$$
The solution works.
Addendum:
The general solution of this recurrence relation is
$$a_n=c_1 3^n + c_2$$
Using $c_1=3^4$, $c_2=0$ produces the given solution.
A: To show $a_n=3^{n+4}$ is a solution:
that means $a_{n-1}=3^{n+3}$ and $a_{n-2}=3^{n+2}$,
so
$4 a_{n-1}-3 a_{n-2}=4\cdot3^{n+3}-3\cdot3^{n+2}=(12-3)3^{n+2}=9\cdot3^{n+2}=3^{n+4}$,
which is indeed $a_n$.
