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$. 
 A: 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)$
A: *

*$\Theta$-notation is?

*The difference equation provided is that which defines the Jacobsthal numbers.

*The general method to define the Jacobsthal numbers is as follows.


Let $T(n) = r^{n}$ in the difference equation $T_{n+2} = T_{n+1} + 2 T_{n}$ to obtain $r^{2} - r - 2 = 0$ which yields the solutions $2r = 1 \pm 3 \in \{4, -2\}$ and leads to the general form
$$T_{n} = A \, 2^{n} + B (-1)^{n}$$.
Using the values $T_{0} = 0$ and $T_{1} = 1$ then
$$T_{n} = \frac{2^{n} - (-1)^{n}}{3}$$
A: we have $$t_n = t_{n-1} + 2t_{n-2}, t_0 = 0, t_1 = 2.$$  here are the first few numbers in the sequence: $$0, 2, 2, 6, 10, \cdots. $$
it looks like you can establish $$t_n > 0 \text{ for all } n \ge 1$$ by induction. once we have that can we use $$t_n \ge 2t_{n-2} $$ to conclude that $t_n = O(2^n)$ without solving the recurrence relation?
A: i thought $2^n$ at first from similarity to Fibonacci #s.
from there it is just 2 trivial inductions to find for what $g(n)$ is $T(n)\in Θ(g(n)),$ because $T(n)\in Θ(g(n))$ when $T(n)\in O(g(n))$ and $T(n)\in$ (big omega)$(g(n))$, if i am not mistaken.  And $T(n)\in O(g(n))$ when for some $c\in N,n_0\in Z$, $T(n)\le cg(n),n\ge n_0$. $T(n)\in $ (big omega)$(g(n))$ when for some $c\in N,n_0\in Z$, $T(n)\ge cg(n),n\ge n_0$.
$c=1,n_0=1$: base case: $T(1)=1\le 2^1$.  Assume $T(n)\le (1)(2^n)$, $n\ge 1$.   $T(n+1)=T(n)+2T(n-1)\le 2^n+2(2^{n-1})=2^n+2^n=2(2^n)=2^{n+1}$.  so it holds by induction.  similar proof for lower bound/big omega.
if i am not mistaken $2^n\Leftrightarrow log_2n$.  $log_2n$ is the inverse of $2^n$ as $2^n$ is one-to-one.
edit: this part is incorrect: so is also $Θ(log_n)$. 
