Proving lower bound for fibonacci sequence

Question

Im trying to prove the lower bound for the following recurrance relation:

$$ T(n) = T(n-1) + T(n-2) + O(1) $$

The question asks to prove $\Omega(k^n)$ for some $k>0$, using a recurrance tree. However I am confused, because it is impossible if $k$ is a big number ex: $k=20$

I've drawn the tree, and noticed that its a full binary tree until half the height, so runtime is minimum $$ \Omega(2^\frac{n}{2}) $$ But I don't know how to generalize this to prove the above statement...

Answer 1

Observe that: $$T(n) \geq 2T(n-2) + O(1)$$

For simplicity, write $T(n) \geq 2T(n-2) + c$, so that we have a variable with which to work. Now to use the tree method:

• The height of the tree $k$ satisfies $n-2k \geq 1$. So $k \leq (n-1)/2$.
• At level $i$ of the tree, we have $2^{i}$ nodes. Each node performs $c$ units of non-recursive work. So the total work at level $i$ is $c \cdot 2^i$.

Now set up the geometric series and evaluate.