Proof by induction that $a_0 = 1, a_1 = 1, a_n=2a_{n-1} + 3a_{n-2}$ satisfies $a_n = \frac12 (3^n) + \frac12 (-1)^n$ The question:
The terms of a sequence are given recursively as 
\begin{cases}
a_0 = 1,\\ a_1 = 1 \\a_n=2a_{n-1} + 3a_{n-2} \quad\text{ for } n \geq 2 
\end{cases}
prove by mathematical induction
$a_n = \frac12(3^n) +\frac12(-1)^n$ for all $n \geq 0$
I've started by
proving that the formula works e.g
$$a_0= 1\implies a_0 = \frac12(3^0)+\frac12(-1)^0 = 1 \\a_1=1\implies a_1 = \frac12(3^1) + \frac12(-1)^{1} = 1$$
Therefore $p(1)$ and $p(2)$ are true
Now I have to do the hard part.. the inductive step
suppose $p(1), p(2),\ldots, p(k)$, that is $a_{k+1} = 2a_{k} + 3a_{k-1}$
Im not sure where to really go from here.

We have, by induction hypotheses, that :

$a_k=\frac 12(3^k)+\frac 12(-1)^k$

and :

$a_{k-1}=\frac 12(3^{k-1})+\frac 12(-1)^{k-1}$.

If we "plug them" into :

$a_{k+1}=2a_k+3a_{k-1}$

we get :


$$a_{k+1}=2\left[\frac 12(3^k)+ \frac 12(-1)^k\right]+3\left[\frac 12(3^{k-1})+ \frac 12(-1)^{k-1}\right] =$$
$$= 3^k+(-1)^k+3 \frac 12 3^{k-1}+ \frac 32(-1)^{k-1} =$$
$$=3^k+ \frac 12 3^k+(-1)(-1)^{k-1}+ \frac 32(-1)^{k-1}=\frac 32 3^k+ \frac 12 (-1)^{k-1}=$$
$$=\frac 12 3^{k+1}+ \frac 12 (-1)^{k-1}=\frac 12 3^{k+1}+ \frac 12 (-1)^{k-1}(-1)^2=$$
$$=\frac 12 3^{k+1}+ \frac 12 (-1)^{k+1}$$


