# Log Fibonacci Equals to Theta

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.

• Wouldn't the known explicit closed formula for $F_n$ help? Oct 17, 2016 at 15:52
• {{F}_{n}}=\frac{{{\varphi }^{n}}-{{\psi }^{n}}}{\varphi -\psi }=\frac{{{\varphi }^{n}}-{{\psi }^{n}}}{\sqrt{5}} \begin{align} & \varphi =\frac{1+\sqrt{5}}{2}\approx 1.6180339887\cdots \\ & \psi =\frac{1-\sqrt{5}}{2}=1-\varphi =-\frac{1}{\varphi }\approx -0.6180339887\cdots \\ \end{align} $$\to {{F}_{n}}=\frac{{{\varphi }^{n}}-{{(-\varphi )}^{-n}}}{\sqrt{5}}=\frac{{{\varphi }^{n}}-{{(-\varphi )}^{-n}}}{2\varphi -1}\\ \to {{F}_{n}}=\frac{1}{\sqrt{5}}\cdot {{\left( \frac{1+\sqrt{5}}{2} \right)}^{n}}-\frac{1}{\sqrt{5}}\cdot {{\left( \frac{1-\sqrt{5}}{2} \right)}^{n}}~.$$ Oct 17, 2016 at 15:55
• Theoniix. Maybe? Perhaps you see something i don't. Please elaborate. Oct 17, 2016 at 16:03
• Plz explain this example... Oct 17, 2016 at 16:43

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.

• how do you determine that log(1+Fn−1Fn) is equal to Fn-1 ? Oct 18, 2016 at 7:50
• and how do you determine that A should be log(3/2) and B should be 2 ? Oct 18, 2016 at 8:35
• and i dont get either that you from that can just assume that that is equal to theta n. The way i have understood it then the only way to calculate that Theta n is to reach the point where you can safely conclude that c1*g(x)=n <= f(x) <= c2*g(x) = n Oct 18, 2016 at 8:53
• this question asks: shouldn't $F_5=5,$ not $8$? Feb 12, 2020 at 3:20
• @J.W.Tanner, thank you for pointing that out. I've fixed my answer to use the OP's numbering convention for the Fibonacci numbers. I had assumed the convention $F_0=F_1=1$, and I'm not sure why I didn't notice the OP had specified otherwise. Feb 12, 2020 at 15:24