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$

Question

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.

Answer 1

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}$$