Induction proof on a sequence

A sequence ${a}_{0},{a}_{1},\dots $ is defined by letting ${a}_{0}={a}_{1}=1$ and ${a}_{k}={a}_{k-1}+2{a}_{k-2}$ for all integers $k>1$. Prove that for all integers $k\ge 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 sequence ${a}_{0},{a}_{1},\dots $ is defined by letting ${a}_{0}={a}_{1}=1$ and ${a}_{k}={a}_{k-1}+2{a}_{k-2}$ for all integers $k>1$. Prove that for all integers $k\ge 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!