Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?
Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form
$$ T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n, $$
for some $A,B$. Note that $|(1-\sqrt{5})/2| &lt; 1$, and so the second term tends to zero as $n \longrightarrow \infty$. Assuming that $T(n)$ tends to infinity, $A &gt; 0$ and so
$$ T(n) = \Theta\left( \left( \frac{1+\sqrt{5}}{2} \right)^n \right). $$
Now $(1+\sqrt{5})/2 &gt; \sqrt{2}$, and so $T(n) = \Omega(2^{n/2})$.



Edit: This part is also covered in this answer (see under "A Shortcut").

More generally, for a recurrence of the form $T(n) = \sum_{i=1}^k a_i T(n-i)$, let
$$ P(t) = t^n - \sum_{i=1}^k a_i t^{n-i}. $$
If $P$ has no repeated roots and the (possibly complex) roots are $\lambda_1,\ldots,\lambda_k$, then the solution is always of the form
$$ T(n) = \sum_{i=1}^k A_i \lambda_i^n. $$
If it does have repeated roots, say the roots are $\lambda_1,\ldots,\lambda_l$ with multiplicities $m_1,\ldots,m_l$, then the solution is always of the form
$$ T(n) = \sum_{i=1}^l A_i(n) \lambda_i^n, $$
where $A_i$ is a (possibly complex) polynomial of degree smaller than $m_i$.

In our case, $P(t) = t^2-t-1$ has no repeated roots, and the two roots are $(1\pm\sqrt{5})/2$.

The $A_i$s depend on the initial values, and can be found by solving linear equations. For example, suppose we are given $T(0)$ and $T(1)$ for our recurrence. Then we can find $A,B$ by solving the system
$$
\begin{align*}
T(0) &amp;= A + B, \\
T(1) &amp;= \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B.
\end{align*}
$$
This works even in the case of repeated roots, and $k$ initial values always suffice. Assuming $a_k \neq 0$, $k$ initial values are also necessary.