letting $F(n)$ denote the nth Fibonacci number, prove that $F(n)$ is not $\Omega(2^n)$

Question

Is there a proof that follows directly from the definition of the Fibonacci sequence (i.e., $F(0)=1, F(1)= 1, F(n) = F(n-1)+F(n-2) \text{ for } n \geq 2$), without deferring to the closed-form expression? Or is using the closed-form expression the simplest way?

Answer 1

It suffices to prove that $F_n=o(2^n)$. One way to do this is to take the generating function $\sum_n F_nx^n=1/(1-x-x^2)$ and observe it converges absolutely at $x=1/2$.

For a very low-brow approach, pick a number $a$ with $\frac12(1+\sqrt5)<a<2$, say $a=5/3$. We claim that $F_n\le a^n$. This is OK for $n=0$, $1$. Inductively, $$F_n\le a^{n-1}+a^{n-2}=a^n\left(\frac35+\frac{9}{25}\right) =\frac{24}{25}a^n<a^n.$$ Then $F_n=O(a^n)=o(2^n)$.