# 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.

• For $n=2$ we have $a_2 = 2a_1+3a_0=2+3=5$, and $a_n = 1/2(3^n) +1/2(-1)^n = 10/2 =5$ for $n=2$ : fine. For the induction step (from $k$ to $k+1$) we assume that the relation holds for $a_k$ and $a_{k-1}$ and we have to prove it for $a_{k+1}$. Sep 11 '14 at 12:54

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