0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Wouldn't the known explicit closed formula for $F_n$ help? $\endgroup$
    – Theorem
    Oct 17, 2016 at 15:52
  • 1
    $\begingroup$ $${{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}}~.$$ $\endgroup$
    – Khosrotash
    Oct 17, 2016 at 15:55
  • $\begingroup$ Theoniix. Maybe? Perhaps you see something i don't. Please elaborate. $\endgroup$
    – Nulle
    Oct 17, 2016 at 16:03
  • $\begingroup$ Plz explain this example... $\endgroup$
    – Nulle
    Oct 17, 2016 at 16:43

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ how do you determine that log(1+Fn−1Fn) is equal to Fn-1 ? $\endgroup$
    – Nulle
    Oct 18, 2016 at 7:50
  • $\begingroup$ and how do you determine that A should be log(3/2) and B should be 2 ? $\endgroup$
    – Nulle
    Oct 18, 2016 at 8:35
  • $\begingroup$ 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 $\endgroup$
    – Nulle
    Oct 18, 2016 at 8:53
  • 1
    $\begingroup$ this question asks: shouldn't $F_5=5, $ not $8$? $\endgroup$ Feb 12, 2020 at 3:20
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 12, 2020 at 15:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .