Show that a sequence $a_n$ is a solution of the given recurrence relation

Question

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.

Answer 1

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!

Answer 2

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$

Answer 3

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

Answer 4

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