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

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)$.

$$\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.