Use Induction to prove recurrence 
if the above screenshot is not visible, here is the text format:
Question:
Solve the following recurrence and prove your result is correct using induction:
$a_1 = 0$
$a_n = 3(a_{n-1}) + 4^{n}$ for $n>=2$

Use induction to prove this recursive sequence.
So my approach was that, I plug in the $a_1 = 0$ into $a_2 = 3(0) + 4^{2} = 4^{2}$
and then
$a_3 = 3(4^{2}) + 4^{3}$
$a_4 = 3(3(4^{2}) + 4^{3}) + 4^{4} = 3^{2} *4^{2} + 3 * 4^{3} +4^{4}$
$a_5 = 3(3^{2} *4^{2} + 3 * 4^{3} +4^{4}) + 4^{5} = 3^{3} *4^{2} + 3^{2} * 4^{3} +3*4^{4} + 4^{5}$
$a_6 = 3^{4} *4^{2} + 3^{3} * 4^{3} +3^{2}*4^{4} + 3*4^{5} + 4^{6}$
...
$a_n = 3^{n-2} *4^{2} + 3^{n-3} * 4^{3} + ... + 3*4^{n-1} + 4^{n} = \sum_{k=2}^{n} 3^{n-k}*4^{k} $
now through induction, I'm not sure how to get there. So far what I know is that:
$a_{n+1} = 3(a_{n}) + 4^{n+1} = \sum_{k=2}^{n+1} 3^{n+1-k}*4^{k}$
= $3(\sum_{k=2}^{n} 3^{n-k}*4^{k}) + 4^{n+1} = \sum_{k=2}^{n+1} 3^{n+1-k}*4^{k}$
= $(\sum_{k=2}^{n} 3*3^{n-k}*4^{k}) + 4^{n+1} = \sum_{k=2}^{n+1} 3^{n+1-k}*4^{k}$
= $(\sum_{k=2}^{n} 3^{n+1-k}*4^{k}) + 4^{n+1} = \sum_{k=2}^{n+1} 3^{n+1-k}*4^{k}$
but then I'm stuck, because I cannot simplify it to make them equal to each other, or I'm in the wrong direction?

I assume you mean $a_0=0$ and $a_n = 3a_{n-1}+4^n$ for $n\ge 1$ (not $n\ge 2$). And by "prove this recursive sequence", you mean to find a closed formula.
Consider the generating function $f(x)=\sum_{n=0}^\infty a_nx^n$,
then by the initial condition and recursive relation, we have $$3xf(x)+\sum_{n=1}^\infty 4^nx^n = \sum_{n=1}^\infty a_nx^n = f(x)$$
$$3xf(x) + \frac{1}{1-4x}-1=f(x)$$
$$\begin{align} f(x) &= \frac{4x}{(1-4x)(1-3x)} =4x(\sum_{a=0}^\infty (4x)^a)(\sum_{b=0}^\infty (3x)^b) \\ &=\sum_{n=1}^\infty 4(\sum_{a+b=n-1}4^a3^b)x^n =\sum_{n=1}^\infty 4 \sum_{b=0}^{n-1}(\frac{3}{4})^b 4^{n-1} x^n\\&=\sum_{n=1}^\infty 4^{n+1}(1-(\frac{3}{4})^n)x^n\end{align}$$
Hence $a_n = 4^{n+1}(1-(\frac{3}{4})^n)=4(4^n-3^n)$.
The above reasoning is solid. But if you prefer, you may prove this by induction.
