<s>[INST] Inductive proof for recursive formula So, I have a recursion in which $$a_0 = 5$$ $$a_1 = 1$$ $$a_{n+2} = a_{n+1} + 2a_n$$ 
I should then prove by induction that the formula $a_n = 2^{n+1} + 3(-1)^n$ works for every number.
Anyway, I generally know how to use induction as proof but doesn't really have a clue on how to use it when it comes to a recursive formula. I have tried to prove the base case but don't really know how to use $k+1$ to my advantage afterwards since I'm not sure how to represent $n = k$ and then that it works for every $n$ by $k + 1$.
 [/INST] Start with
$a_{n+2} = a_{n+1} + 2a_n$
and substitute
the induction assumption
$a_n = 2^{n+1} + 3(-1)^n
$
for $n$ and $n+1$.
This gives
$\begin{array}\\
a_{n+2} 
&= a_{n+1} + 2a_n\\
&= (2^{n+2} + 3(-1)^{n+1}) + 2(2^{n+1} + 3(-1)^n)\\
&= 2^{n+2} + 3(-1)^{n+1} + 2^{n+2} + 6(-1)^n\\
&= 2^{n+3} + 3(-1)^{n+1}  - 6(-1)^{n+1}\\
&= 2^{n+3} - 3(-1)^{n+1}\\
&= 2^{n+3} + 3(-1)^{n+2}\\
\end{array}
$
Therefore,
if 
$a_n = 2^{n+1} + 3(-1)^n
$
is true
for $n$ and $n+1$,
it is true for $n+2$.
Since it is true for
$0$ and $1$
(by direct calculation),
it is true for all $n$.
</s>