<s>[INST] Prove $a_n = n 3^{n-1}$, recurrence relation. Let $a_0 = 0, a_1 = 1$, and let $a_{n+2} = 6a_{n+1} - 9a_n$ for $n\geq 0.$ 
Prove $a_n = n 3^{n-1}$ for $n\geq 0.$
attempt: Suppose $a_0 = 0, a_1 = 1$, and let $a_{n+2} = 6a_{n+1} - 9a_n$.
Then notice when $n = 0$, we have $a_2 = 6_{1} - 9a_0 = 6-0 = 6$.
And $a_2 = 2*(3^{2-1}) = 6.$
Suppose as inductive hypothesis this is true for all $n \geq 0.$ 
Then we need to show $a_{n+1} = (n+1) 3^{(n+1)-1}= (n+1)*3^n$.
Then $a_{n+1} = 6a_{n}-9a_{n-1}$ by the recurrence relation. 
So $a_{n+1} = 6a_{n}-9a_{n-1} = 6(n 3^{n-1})- 9a_{n-1} = 3[2(n 3^{n-1})] - 3a_{n-1}]= $ I am stuck after this, I want to show $a_{n+1} =  (n+1)*3^n$.
Can someone please help ? Thank you
 [/INST] Induction. 
True for $n=0,n=1$. 
We will assume true up to $n$, will show holds for $n+1$: 
$$a_{n+1} = 6 a_n -9 a_{n-1} = 6 n 3^{n-1} - 9 (n-1) 3^{n-2}=(2n -(n-1))3^n=(n+1)3^{(n+1)-1}.$$
</s>