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.
 A: 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
$$
A: 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$$
A: Another way to solve the problem: note that you have
$$
\begin{bmatrix}
a_{n+1}\\ a_n \\ 1
\end{bmatrix}
=
\begin{bmatrix}
1 & 2 & 2 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
a_{n}\\ a_{n-1} \\ 1
\end{bmatrix}
=
\begin{bmatrix}
1 & 2 & 2 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}^n
\begin{bmatrix}
 0 \\ 1 \\ 1
\end{bmatrix}
$$
