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$.
 A: Let's define $f(n)=2^{n+1}+3(-1)^n$. You want to prove that $a_n$, as defined by your recursion, equals $f(n)$.
First, you want to show that $f(0)$ and $f(1)$ give you $a_0$ and $a_1$. That's a straightforward calculation.
Next, you have to show that $f$ satisfies the recursion formula. Does $f(n+2)$ really equal $f(n+1)+2f(n)$? If that works, then you're good.
Consider the statement $P(n)$ to be "$f(n)=a_n$ and $f(n+1)=a_{n+1}$". You've already shown $P(0)$. Checking that $f(n+2)$ satisfies the recursion shows that $P(n)\implies P(n+1)$.
A: $$a_{n+2}=2^{n+2}+3(-1)^{n+1}+2(2^{n+1}+3(-1)^n)=2^{n+3}+3((-1)^{n+1}+2(-1)^n)=$$
$$=2^{n+3}+3(-1)^{n+2}(-1+2)=2^{n+3}+3(-1)^{n+2}.$$
Now, you need to check that $a_0=5$ and $a_1=1$ by this formula.
A: Given $a_{n+2} = a_{n+1} + 2a_n$, and I assume you have done the base case.
Induction hypothesis is : $a_n = 2^{n+1} + 3(-1)^n$  
So, let induction hypothesis be true till $n=k$.
Then,   
$a_{k+1} = 2^{k+2} + 3(-1)^{k+1} = 2(2^{k+1}) - 3(-1)^{k} $  
$=2^{k+1} + 2^{k+1} -3(-1)^{k}=(2^{k+1} + 3(-1)^k) + 2(2^{k} + 3(-1)^{k-1}) $ 
$ =a_{k} + 2a_{k-1}$
A: 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$.
A: You'll need two base cases and you'll need strong induction.  ("strong" means that during the induction step, you assume it is true for all $n \le k$; not just for the single value $n = k$.)
The base cases $n=0; n=1$ are given: $a_0= 2^{0+1}+3(-1)^{0}=2+3 =5; a_1=2^{1+1} + 3(-1)^1 = 2^2 -3 = 4-3 = 1$.
The induction step:  Assume that for all $k \le n$, $a_k = 2^{k+1} + 3(-1)^k$.
Then $a_{k+1} = a_k + 2a_{k-1} =$
$(2^{k+1} + 3(-1)^k) + 2(2^k + 3(-1)^{k+1})$.
You have to prove that:
$(2^{k+1} + 3(-1)^k) + 2(2^k + 3(-1)^{k+1}) = 2^{k+2} + 3(-1)^{k+1}$.
Can you do that?
....
$(2^{k+1} + 3(-1)^k) + 2(2^k + 3(-1)^{k-1})=$
$2^{k+1} +(-1)*3(-1)^{k-1}) + (2^{k+1} + 2*3(-1)^{k-1}) =$
$[2^{k+1} + 2^{k+1}] + [2*3(-1)^{k-1}- 3(-1)^{k-1})]=$
$[2*2^{k+1}]+[-3(-1)^{k-1}]=$
$2^{k+2} + 3(-1)^k$.
