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$.
Best Answer
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)$.