Strong Induction: Prove $a_n=(-3)^n$

Question

I need help with the following problem.

$a_0=1$

$a_1=-3$

$a_n=-2*a_{n-1}+3*a_{n-2}$, for all $n\ge2$

prove $a_n=(-3)^n$

I understand the base cases, I'm just confused on how to do the strong induction step. I know that we are showing that if P(n) is true then it must hold for P(n+1) but I don't know how to do that with $a_{n+1}$

Answer 1

Substitute in the induction hypothesis for $a_{n}$ and $a_{n-1}$ to get:

\begin{eqnarray} a_{n+1} &=& -2 a_n + 3 a_{n-1}\\ &=& -2(-3)^{n} + 3(-3)^{n-1}\\ &=& -2(-3)^n -(-3)^n\\ &=& -3(-3)^n\\ &=& (-3)^{n+1} \end{eqnarray}

Answer 2

For strong induction, you prove the base case and then assume $P(0), P(1), \ldots, P(n)$ hold and prove $P(n+1)$.

Here, the base cases are $P(0),P(1)$ (which clearly hold). If $P(0), P(1), \ldots, P(n)$ hold, then, in particular $a_{n} = (-3)^{n}, a_{n-1} = (-3)^{n-1}$. Thus \begin{align*} a_{n+1} &= -2 (-3)^n + 3(-3)^{n-1}\\ &= -2 (3^{n}) - 3^n\\ &= (-3)(-3)^n = (-3)^{n+1} \end{align*} which shows that $P(n+1)$ holds.