1
$\begingroup$

I need to show log $Fib_{n}$ is $\theta(n)$ by the Fibonacci numbers defined as

$$ F_n=F_{n-1}+F_{n-2}$$ for $$ n \geq 2 $$ $ F_{0} = 0 $ and $ F_{1} = 1 $

I'm not sure how to approach this.

I can see it grows exponentially as I've shown a basecase for $F_{6}$.

Basecase for $F_{6}$:

$$ F_{2} = F_{1} + F_{0} = 1 + 0 $$ $$ F_{3} = F_{2} + F_{1} = 1 + 1 $$ $$ F_{4} = F_{3} + F_{2} = 2 + 1 $$ $$ F_{5} = F_{4} + F_{3} = 3 + 2 $$ $$ F_{6} = F_{5} + F_{4} = 5 + 3 $$

But how I prove it's true for log $Fib_{n}$ is $\theta(n)$ I don't know. Hope someone can help!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Hint: try to find upper and lower bounds on $F_n$. $\endgroup$ – Cain Oct 25 '18 at 21:53
  • $\begingroup$ Also - if you consult en.wikipedia.org/wiki/Fibonacci_number you will see there is a closed form expression (for the $n$th Fibonacci number) that is pretty helpful... But that might be overkill! @Cain's answer is probably what you want $\endgroup$ – peter a g Oct 25 '18 at 21:55
  • $\begingroup$ By $\theta(n)$ do you mean Big O notation? $\endgroup$ – rtybase Oct 25 '18 at 22:31
  • $\begingroup$ @rtybase fwiw I assumed that jubibanna meant $\Theta (n)$ (as on the Wikipedia page that you linked to) $\endgroup$ – peter a g Oct 25 '18 at 22:50
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ THANK YOU, Cain! From all the post this is the only one that made sense to me. $\endgroup$ – jubibanna Nov 5 '18 at 20:40
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Isn't there a simpler way to understand this? I've been struggling all evening with this. It's my first months at Data Science :( $\endgroup$ – jubibanna Oct 25 '18 at 22:28
  • $\begingroup$ The solutions of recurrences of the form $A_{n+2} = H A_{n+1} + K A_n$ with $H,K\geq 1$ all have an exponential behaviour. This is more or less equivalent to the fundamental theorem of Algebra. Although to know the definition of radius of convergence and the basic properties of meromorphic functions is pretty useful. $\endgroup$ – Jack D'Aurizio Oct 25 '18 at 22:30

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.