Prove using induction / Strong induction

Question

I have a problem:

Let $a_0=0, a_1=1$, and let $a_{n+2}=6a_{n+1}-9a_n$ for $n\geq 0$. Prove that $a_n=n\cdot 3^{n-1}$ for all $n\geq 0$.

And I am assuming that this can be solved via induction. Only problem is I am not sure how to go about doing this. Do I use induction to prove the first part and then again on the second part?

Sorry for terrible question, I am new to this site. Thank you.

Answer 1

HINT:

If $a_m=m3^{m-1}$ for $m\le n+1$

using strong induction, $a_{n+2}=6(n+1)3^n-9\cdot n3^{n-1}=\cdots=(n+2)3^{(n+2)-1}$