Show that log $Fib_{n}$ is $\theta(n)$

Question

I need to show log $Fib_{n}$ is $\theta(n)$ by the Fibonacci numbers defined as

$$ F_n=F_{n-1}+F_{n-2}$$ for $$ n \geq 2 $$ $ F_{0} = 0 $ and $ F_{1} = 1 $

I'm not sure how to approach this.

I can see it grows exponentially as I've shown a basecase for $F_{6}$.

Basecase for $F_{6}$:

$$ F_{2} = F_{1} + F_{0} = 1 + 0 $$ $$ F_{3} = F_{2} + F_{1} = 1 + 1 $$ $$ F_{4} = F_{3} + F_{2} = 2 + 1 $$ $$ F_{5} = F_{4} + F_{3} = 3 + 2 $$ $$ F_{6} = F_{5} + F_{4} = 5 + 3 $$

But how I prove it's true for log $Fib_{n}$ is $\theta(n)$ I don't know. Hope someone can help!

Answer 1

First note that $F_n$ is an increasing sequence. This is a simple consequence of the recurrence relation and the fact that $F_0, F_1 \geq 0$.

Now, using this, we have $$F_n = F_{n-1} + F_{n-2} \leq 2F_{n-1}.$$ It is straightforward to verify that the solution to the recurrence, $a_n = 2a_{n-1}, a_1 = 1$, is $a_n = 2^n$, which implies $F_n \leq 2^n$.

On the other side, we also have $$F_n = F_{n-1} + F_{n-2} \geq 2F_{n-2}.$$ Using similar arguments to the previous case we get $F_n \geq (\sqrt{2})^n$.

Putting everything together, $$\frac{n}{2}\log(2) = n\log(\sqrt{2}) \leq \log(F_n) \leq n\log(2).$$

In other words, $F_n = \Theta(n)$.

Answer 2

$$\sum_{n\geq 0} F_n x^n = \frac{x}{1-x-x^2}$$ has a simple pole at $x=\frac{-1-\sqrt{5}}{2}$ and a simple pole at $x=\frac{-1+\sqrt{5}}{2}$. It follows that the radius of convergence of the previous power series is $\rho=\frac{2}{1+\sqrt{5}}$ and $\lim_{n\to +\infty}\frac{\log F_n}{n}=\frac{1+\sqrt{5}}{2}$. See Frobenius method.