Log Fibonacci Equals to Theta

Question

I'm trying to prove that $\log F_n = Θ(n)$. Since this is Fibonacci then recursively $F_n = F_{n-1} + F_{n-2}$, $F_1 = 1$, $F_0 = 0$. The only way I can think of to prove this is by proving that $\log F_n$ is equal to $n$ but that I can't either. No matter what Fibonacci sequence I take the $\log$ of it is simply not equal to $n$. So I can honestly say I'm so lost right now that any input would be a appreciated.

Answer 1

You don't need to (and can't anyway) prove that $\log F_n$ is equal to $n$. All you need to show is that for some constants $A$ and $B$,

$$An\le\log F_n\le Bn\quad\text{for all large }n$$

To get started, note that

$$\log F_{n+1}=\log(F_n+F_{n-1})=\log F_n+\log\left(1+{F_{n-1}\over F_n}\right)$$

and the increasing nature of the Fibonacci sequnce, $F_1\le F_2\le F_3\le\cdots$, implies

$${1\over2}={F_{n-1}\over2F_{n-1}}\le{F_{n-1}\over F_{n-1}+F_{n-2}}={F_{n-1}\over F_n}\le1$$

from which it follows that

$$\log(3/2)\le\log\left(1+{F_{n-1}\over F_n}\right)\le\log2$$

So let's let $A=\log(3/2)$ and $B=\log2$. What we've shown is that

$$An\le\log F_n\le Bn\implies A(n+1)\le\log F_{n+1}\le B(n+1)$$

Thus, provided we can establish a base case, induction tells us that $\log F_n=\Theta(n)$. The first value for which $n\log(3/2)\le\log F_n\le n\log2$ (with the OP's convention $F_1=F_2=1$) turns out to be $n=11$; however, it's easier to take $n=12$ as the base case, since $F_{12}=144=12^2$, and we have

$$6\log(3/2)=\log(729/64)\le\log(768/64)=\log12\le\log64=6\log2$$

Remark: In point of fact, $\log F_n\approx n\log\phi$, where $\phi=(1+\sqrt5)/2\approx1.618$, which of course lies between $3/2$ and $2$. The approach I've given here generalizes to settings where the exact asymptotic behavior of the sequence is not so easy to pinpoint.