Induction proof on a sequence 
A sequence $a_0,a_1,\dotsc$ is defined by letting $a_0=a_1=1$ and $a_k=a_{k-1}+2a_{k-2}$ for all integers $k>1$. Prove that for all integers $k \geq 0$, $a_k=\frac{2^{k+1}+(-1)^k}{3}$.

Base case:
$S(2)$
Let $k=2$.
Then $a_2 =\frac{2^{2+1}+(-1)^2}{3}=\frac{9}{3}=3$
$S(3)$
Let $k=3$.
Then $a_3 =\frac{2^{3+1}+(-1)^3}{3}=\frac{15}{3}=5$
Base is true.
Induction step:
Assume $S(k)$ and $S(k-1)$ are true.
Then $$S(k)=a_k=\frac{2^{k+1}+(-1)^k}{3}$$
and
$$S(k-1)=a_{k+1}=\frac{2^{k}+(-1)^{k-1}}{3}$$
Since $S(k)=a_k$ and $S(k-1)=a_{k-1}$, by definition $S(k+1)=S(k)+2\cdot S(k-1)$
$$\frac{2^{k+2}+(-1)^{k+1}}{3}=\frac{2^{k+1}+(-1)^k}{3}+2\cdot \frac{2^{k}+(-1)^{k-1}}{3}$$
Solving this should lead to that
$$k=-2$$
Therefore $S(k+1)$ is true.

I think I've got the right idea but I'm not completely sure that I've done this correctly. Any help or suggestions are much appreciated!
 A: Couple of things –

*

*$S(k)$ must have a truth value. In this case it's the statement "$a_k = \frac{2^{k+1} + (-1)^k}{3}$". So you shouldn't write $S(k+1) = S(k)+2S(k-1)$ because that's adding statements!

*The question asks to show $S(k)$ for $k\geq0$. So your base case must include $k=0$. (Note that here I've abbreviated "$S(k)$ is true" to "$S(k)$" – in the same way that I can abbreivate "it's true that it's raining" to "it's raining". But feel free to say "$S(k)$ is true" for clarity.)

*The aim for the induction part is to (as I think you know) assume $S(k-1)$ and $S(k)$, and then show $S(k+1)$. The aim is then to do something like
$$
\begin{eqnarray}
a_{k+1} &=& a_k + 2a_{k-1} &\text{(by definition)}\\
&=& \frac{2^{k+1} + (-1)^k}{3} + \frac{2^{k} + (-1)^{k-1}}{3} &\text{(by inductive hypothesis)} \\
&=& \dots &\text{(some steps for you to work out)} \\
&=& \frac{2^{k+2} + (-1)^{(k+1)}}{3}
\end{eqnarray}
$$
i.e. $S(k+1)$. In your proof you seemed to begin with assuming $S(k+1)$, which is incorrect.

