Solve the recurrence $T(n) = T(n-1) + 2T(n-2) + 2$ $T(0) = 1,
T(1) = 0$
I ain't able to get answer from any of the methods.
Substitution:
$T(n) = x^n $
\begin{align}
& x^n = x^{n-1} + 2x^{n-2} + 2 \\
& x^2 = x + 2 + 2x^2\\
& x^2 + x  + 2 =0
\end{align}
solving this I will get a complex root.
\begin{align}
x & = \frac{-1 \pm \sqrt{1-8}}{2}
x & = \frac{-1 \pm 7i}{2}
\end{align}
Now how to go further.
General:
\begin{align}
T(2) & = 4\\
T(3) & = 6\\
T(4) & = 16\\
T(5) & = 30\\
T(6) & = 64\\
T(7) & = 126\\
T(8) & = 256
\end{align}
From this i can deduce if $n$ is even then $2^n$.
 I cant deduce for if $n$ is odd.

Hint try to make it homogeneous, from
$$T(n) = T(n-1) + 2T(n-2) + 2$$
$$T(n+1) = T(n) + 2T(n-1) + 2$$
we have 
$$T(n)-T(n+1)=T(n-1) + 2T(n-2) - T(n) - 2T(n-1) \iff \\
T(n+1)-2T(n)-T(n-1)+2T(n-2)=0$$
leading to characteristic polynomial
$$x^3-2x^2-x+2=0 \iff (x-2)(x-1)(x+1)=0$$
