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!

$\endgroup$
4
  • 1
    $\begingroup$ Hint: try to find upper and lower bounds on $F_n$. $\endgroup$
    – Cain
    Oct 25, 2018 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, 2018 at 21:55
  • $\begingroup$ By $\theta(n)$ do you mean Big O notation? $\endgroup$
    – rtybase
    Oct 25, 2018 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, 2018 at 22:50

2 Answers 2

Reset to default
1
$\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)$.

$\endgroup$
2
  • $\begingroup$ THANK YOU, Cain! From all the post this is the only one that made sense to me. $\endgroup$
    – jubibanna
    Nov 5, 2018 at 20:40
  • $\begingroup$ @Cain: (Asking on behalf of @ Emanual, who doesn't have enough reputation to comment...) How can you tell that $F_n\geq(\sqrt{2})^n$? $F_0=0$ is not greather than $(\sqrt{2})^0=1$; $F_1=1$ is not greater than $(\sqrt{2})^1=\sqrt{2}$; $F(2)=1$ is not greater than $(\sqrt{2})^2=2$; $\ldots$ $\endgroup$
    – Blue
    Feb 12, 2020 at 3:45
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.

$\endgroup$
2
  • $\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, 2018 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, 2018 at 22:30

You must log in to answer this question.

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