Find the closed form of the following recurrence relation
$$
a_n=a_{n-1}+6a_{n-2}+3^n
$$
where
$$
a_0=5,a_1=0
$$
So I am comfortable finding closed form of these recurrences when it is only two terms. The $3^n$ is what is confusing me. So my question is that is the characteristic polynomial of this problem
$$
\lambda^2=\lambda+6+9
$$
into
$$
\lambda^2-\lambda-15
$$
or am I not working with $3^n$ correctly? IF this is correct, i know we would move into finding the zeroes and subbing them back into the equation, but I am not sure that this is correct
EDIT: Using the comments, I got that $a_n = 2(3)^n+3(-2)^n+3^n $
I believe this works with $a_3$.
Best Answer
The following is a step-by-step solution which reduces the problem to a linear homogeneous recurrence with constant coefficients, which can be solved with standard techniques.
The exponential term can be "absorbed" into the recurrence by dividing by $\,3^{n-2}\,$ and defining $u_n = \dfrac{a_n}{3^n}\,$:
$$ \begin{align} a_n=a_{n-1}+6a_{n-2}+3^n \quad&\iff\quad 9 \cdot \frac{a_n}{3^n} = 3 \cdot \frac{a_{n-1}}{3^{n-1}} + 6 \cdot \frac{a_{n-2}}{3^{n-2}} + 9 \\ &\iff\quad 9 u_n = 3u_{n-1}+6u_{n-2}+ 9 \\ &\iff\quad 3 u_n = u_{n-1} + 2u_{n-2} + 3 \tag{1} \end{align} $$
The constant term can then be "absorbed" by trying a constant translation $\,u_n = v_n + \lambda\,$ in $(1)\,$:
$$ \require{cancel} \begin{align} 3(v_n + \cancel{\lambda}) = (v_{n-1}+\cancel{\lambda}) + 2(v_{n-2}+\cancel{\lambda}) + 3 \quad\iff\quad 3 v_n = v_{n-1} + 2v_{n-2} + 3 \tag{2} \end{align} $$
The resulting recurrence $(2)$ is identical to $(1)$, so this substitution does not work because the constant term cannot be eliminated this way (which actually happens because the characteristic polynomial has $1$ as a root). Next try in such cases is a linear transformation $u_n = v_n + \lambda n\,$:
$$ \require{cancel} \begin{align} 3(v_n+\bcancel{\lambda n}) &= \big(v_{n-1}+ \lambda(\bcancel{n}-1)\big) + 2\big(v_{n-2}+\lambda(\bcancel{n}-2)\big) + 3 \\ \iff\quad\quad\quad\quad 3 v_n &= v_{n-1} + 2 v_{n-2} - 5\lambda + 3 \tag{3} \end{align} $$
This one works, by choosing $\lambda = \dfrac{3}{5}$ to cancel the constant term in $(3)$, so $\,u_n=v_n + \dfrac{3}{5}n\,$ satisfies:
$$ 3 v_n = v_{n-1} + 2 v_{n-2} \tag{4} $$
The latter is a linear homogeneous recurrence with constant coefficients. The characteristic polynomial is $3t^2-t-2$ with roots $\big\{1, -\frac{2}{3}\big\}$, so $v_n = c_1 + c_2 \cdot \dfrac{(-1)^n2^n}{3^n}$ for some constants $c_1, c_2$. By reversing the substitutions, it follows that:
$$ a_n = 3^n u_n = 3^n\left(v_n+\frac{3}{5}n\right) = c_1 \cdot 3^n + c_2 \cdot (-1)^n2^n + \frac{1}{5} \cdot n \cdot 3^{n+1} \tag{5} $$
Finally, the constants $c_1,c_2$ can be determined from the initial conditions by solving the system:
$$ \begin{cases} \begin{align} 5 = a_0 &= c_1 + c_2 \\ 0 = a_1 &= 3c_1 - 2c_2 + \frac{9}{5} \end{align} \end{cases} $$