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?
 A: Here's a useful "trick".
If
$a_n
=ua_{n-1}+v^n
$
then
(here comes the trick),
dividing by $u^n$,
$\dfrac{a_n}{u^n}
=\dfrac{ua_{n-1}}{u^n}+\dfrac{v^n}{u^n}
=\dfrac{a_{n-1}}{u^{n-1}}+(v/u)^n
$.
Let $b_n = \dfrac{a_n}{u^n}$.
Then
$b_n
=b_{n-1}+r^n
$
where $r = v/u$
or
$b_n-b_{n-1}
=r^n
$.
This becomes a telescoping sum,
so
$\begin{array}\\
b_m-b_0
&=\sum_{n=1}^m (b_n-b_{n-1})\\
&=\sum_{n=1}^m r^n\\
&=\dfrac{r-r^{m+1}}{1-r}
\qquad\text{(if } r \ne 1.
\text{ If }r=1, \text{the sum is }m.)\\
&=\dfrac{\frac{v}{u}-(\frac{v}{u})^{m+1}}{1-\frac{v}{u}}\\
&=\dfrac{v-\frac{v^{m+1}}{u^m}}{u-v}\\
\text{so}\\
\dfrac{a_m}{u^m}-a_0
&=\dfrac{v-\frac{v^{m+1}}{u^m}}{u-v}\\
\text{or}\\
a_m
&=u^ma_0+\dfrac{vu^m-v^{m+1}}{u-v}\\
&=u^ma_0+\dfrac{v(u^m-v^{m})}{u-v}\\
\end{array}
$
Note that,
if the $a$s start at $k$
instead of $0$,
we can do
$\begin{array}\\
b_m-b_k
&=\sum_{n=k+1}^m (b_n-b_{n-1})\\
&=\sum_{n=k+1}^m r^n\\
&=\dfrac{r^{k+1}-r^{m+1}}{1-r}
\qquad\text{(if } r \ne 1.
\text{ If }r=1, \text{the sum is }m-k.)\\
&=\dfrac{(\frac{v}{u})^{k+1}-(\frac{v}{u})^{m+1}}{1-\frac{v}{u}}\\
&=\dfrac{\frac{v^{k+1}}{u^k}-\frac{v^{m+1}}{u^m}}{u-v}\\
\text{so}\\
\dfrac{a_m}{u^m}-\dfrac{a_k}{u^k}
&=\dfrac{\frac{v^{k+1}}{u^k}-\frac{v^{m+1}}{u^m}}{u-v}\\
\text{or}\\
a_m
&=u^{m-k}a_k+\dfrac{v^{k+1}u^{m-k}-v^{m+1}}{u-v}\\
&=u^{m-k}a_k+\dfrac{v^{k+1}(u^{m-k}-v^{m-k})}{u-v}\\
\end{array}
$
If this is for
$k=1$,
this becomes
$a_m
=u^{m-1}a_1+\dfrac{v^{2}(u^{m-1}-v^{m-1})}{u-v}
$.
A: 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.
