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!