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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.