<s>[INST] 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.
 [/INST] Put $U(n) - 1 = T(n)$ and the equation is
$$
U(n+2) = U(n-1) + 2U(n)
$$
let as you do $U(n) = x^n$ and we get
$$
x^{n+2} = x^{n-1}+2x^n
$$ or we need to solve
$$
x^2-x-2 = 0
$$
hence
$$
x = \frac{1}{2} \pm \sqrt{1/4+8/4} = \frac{1 \pm 3}{2}
$$
So
$$
U(n) = A 2^n + B (-1)^n
$$ and
$$
T(n) = A 2^n + B (-1)^n - 1
$$
So
$$
T(0) = A+B-1 = 1
$$ and
$$
T(1) = 2A-B -1 = 0
$$ gives
$$
A = 1, \,B=1
$$
And we conclude
$$
T(n) = 2^n+(-1)^n-1
$$
</s>