<s>[INST] If $T(n)= T(n-1) + 2T(n-2)$ If $T(n)= T(n-1) + 2T(n-2)$ with $T(0)=0$  and  $T(1) = 1$
What is $T(n)$ (in $Θ$–notation) in terms of $n$?
I am trying to solve by substitution, but I am not sure if I am doing this right, as I get stuck.  Can anybody tell me where to go from here?
$T(n)= T(n-1) + 2T(n-2)$
$T(n-1)= T(n-2) + 2T(n-3)$
$T(n-2)= T(n-3) + 2T(n-4)$
$T(n)= T(n-k) + 2T(n-(k+1))$
Substitute $n$ for $k$
$T(n)= T(n-n) + 2T(n-(n+1))$
$T(n)= T(0) + 2T(1)$
I am not sure where to go from here to find $T(n)$ (in $Θ$–notation) in terms of $n$. 
 [/INST] Generating functions for the win. Let $T(x) = \sum_{n=0}^{\infty}T_nx^n = \sum_{n=1}^{\infty}T_nx^n$, since $T_0 = 0$.
Then:
$$\begin{split}
T(x) &= x + \sum_{n=2}^{\infty}T_nx^n \\
&= x + \sum_{n=2}^{\infty}(T_{n-1} + 2T_{n-2})x^n \\
&= x + \sum_{n=2}^{\infty}T_{n-1}x^n + \sum_{n=2}^{\infty}2T_{n-2}x^n
\end{split}$$
Let's rewrite those sums. The first one:
$$\begin{split}
\sum_{n=2}^{\infty}T_{n-1}x^n &= x\sum_{n=2}^{\infty}T_{n-1}x^{n-1} \\
&= x\sum_{n=1}^{\infty}T_nx^n \\
&= xT(x)
\end{split}$$
Likewise, the second sum works out to $2x^2T(x)$. Thus:
$$T(x) = x + xT(x) + 2x^2T(x)$$
So:
$$\begin{split}
T(x) &= \frac{x}{1 -x - 2x^2} = \frac{x}{(1-2x)(1+x)} \\
&= \frac{\frac{1}{3}}{1-2x} + \frac{-\frac{1}{3}}{1+x} \\
&= \frac13\sum_{n=0}^{\infty}2^nx^n - \frac13\sum_{n=0}^{\infty}(-1)^nx^n \\
&= \sum_{n=0}^{\infty}\left(\frac{2^n - (-1)^n}{3}\right)x^n
\end{split}$$
Which gives us our recurrence: $T_n = \left(\frac{2^n - (-1)^n}{3}\right) = \Theta(2^n)$
</s>