Finding closed form of the following recurrence relation

Question

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

Answer 1

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

Answer 2

Let $c_n={3\over 5}n\,3^n.$ Then $$c_n=c_{n-1}+6c_{n-2}+3^n$$ Thus the sequence $b_n=a_n-c_n$ satisfies $$b_n=b_{n-1}+6b_{n-2}$$ Now we may apply classical methods for homogeneous recurrence relations.

Remark A particular solution $c_n$ of nonhomogeneous recurrence relation has been guessed by observing that $1/3$ is a single root of the characteristic equation of the homogeneous recurrence relation. Therefore a natural choice is $c_n=cn3^n.$ Then $c$ can be determined as $3/5.$

Answer 3

The recurrence

$$ a_n-a_{n-1}-6a_{n-2}=3^n $$

is equivalent to

$$ \left(\matrix{a_n^1\\ a_n^2}\right)=\left(\matrix{0&1\\ 6&1}\right)\left(\matrix{a_{n-1}^1\\ a_{n-1}^2}\right)+\left(\matrix{0\\ 3^n}\right) $$

but

$$ \left(\matrix{0&1\\ 6&1}\right) = T\cdot \Lambda\cdot T^{-1}=\left( \begin{array}{cc} 1 & -1 \\ 3 & 2 \\ \end{array} \right)\left( \begin{array}{cc} 3 & 0 \\ 0 & -2 \\ \end{array} \right)\left( \begin{array}{cc} 1 & -1 \\ 3 & 2 \\ \end{array} \right)^{-1} $$

then

$$ T^{-1}A_n = \Lambda T^{-1}A_{n-1}+T^{-1}b_n $$

now calling $\mathcal{A}_n = T^{-1}A_n$ we have the equivalent sequence

$$ \mathcal{A}_n = \Lambda \mathcal{A}_n+T^{-1}b_n $$

so the homogeneous has the solution

$$ \mathcal{A}_n^h = \Lambda^n\cdot c_0 $$

Making the particular as $\mathcal{A}_n^p = \Lambda^n\cdot c_0(n)$ after substitution we have

$$ \Lambda^n\cdot c_0(n) = \Lambda\cdot\Lambda^{n-1}\cdot c_0(n-1)+T^{-1}b_n $$

or

$$ c_0(n) = c_0(n-1) + \Lambda^{-n}\cdot T^{-1}b_n $$

and thus

$$ c_0(n) = \sum_{k=0}^n\Lambda^{-k}\cdot T^{-1}b_k $$

and finally

$$ \mathcal{A}_n = \mathcal{A}_n^h + \mathcal{A}_n^p = \Lambda^n\cdot c_0 + \Lambda^n\cdot\left(\sum_{k=0}^n\Lambda^{-k}\cdot T^{-1}b_k \right) $$

hence

$$ A_n = T\cdot \mathcal{A}_n $$