Reccurence relation $S(n) = S(n-1) + 2S(n-2) +2 S(0)=0 S(1)=2$; $S(n) = S(n-1) + 2S(n-2) +2 S(0)=0 S(1)=2$;
So I am trying to solve this recurrence this way:
$S(n) = Sn-1 + 2S(n-2) S(0) = -2 S(1)=0$   and the add $2$ to the result equation
But the result I get isn't near to the right answer. Any tips how to solve this?
 A: To solve
$$
a_n=a_{n-1}+2a_{n-2}+2\tag{1}
$$
we can introduce $b_n-1=a_n$. Then we get the linear recurrence
$$
b_n=b_{n-1}+2b_{n-2}\tag{2}
$$
Since
$$
x^2-x-2=(x-2)(x+1)\tag{3}
$$
we get the solution to the linear recurrence $(2)$
$$
b_n=c_1(-1)^n+c_22^n\tag{4}
$$
Therefore,
$$
a_n=c_1(-1)^n+c_22^n-1\tag{5}
$$
Plugging the initial conditions, $a_0=0$ and $a_1=2$, into $(5)$ we get
$$
\begin{align}
c_1+c_2&=1\\
-c_1+2c_2&=3
\end{align}\tag{6}
$$
giving $c_1=-\frac13,c_2=\frac43$. Therefore,
$$
a_n=-\frac13(-1)^n+\frac432^n-1\tag{7}
$$
A: I will only give hints, I let you fill the blanks and understand the missing reasoning.
Let $x_n$ be a particular solution, then notice that $u:=(s_n-x_n)$ is solution of $u_n=u_{n-1}+2u_{n-2}$.
The polynomial $x^2-x-2$ has roots $-1$ and $2$, therefore:
$$s_n=x_n+\alpha(-1)^n+\beta2^n.$$
It suffices to chose $\alpha$ and $\beta$ such that $s_0=0$ and $s_1=2$.
A particular solution is given by $x_n=-1$.
A: This a regular non-homogeneous recurrence, and you could of course (or may even be expected to) solve it using the standard methods. That said, just to build upon this idea...

So i am trying to solve this recurrence this way:
S(n) = Sn-1 + 2S(n-2) S(0) = -2 S(1)=0   and the add 2 to the result equasion

That won't work, because $S_n-2$ doesn't satisfy the homogeneous recurrence.
Along that idea, however, you could write the recurrence as:
$$S_n + 1 = S_{n-1} +1 + 2 (S_{n-2} + 1)$$
Then $T_n=S_n +1$ does indeed satisfy $T_n=T_{n-1}+ 2 T_{n-2}$ with $T_0=1, T_1=3\,$.
