World's most popular travel blog for travel bloggers.

# Comparing $2^{F_n}$ and $2^{\varphi^n}$

, ,
Problem Detail:

if we define $F_n$ be the $n$th fibonacci number and $\varphi$ be golden number then can we say that

$2^{F_n} \in \Theta(2^{\varphi^n})$

or in other word

$2^{\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}} \in \Theta(2^{\varphi^n})$

It's simple to show that $F_n \in \Theta(\varphi^n)$ but about above one I don't have any Idea

###### Answered By : Yuval Filmus

Hint: We have $F_n = [\varphi^n-(-\varphi)^{-n}]/\sqrt{5} = \varphi^n/\sqrt{5} \pm o(1)$, since $|1/\varphi| < 1$. Hence $$2^{F_n} = 2^{\varphi^n/\sqrt{5}} 2^{\pm o(1)} = 2^{\varphi^n/\sqrt{5}} (1\pm o(1)).$$ In particular, $2^{F_n} = \Theta(2^{\varphi^n/\sqrt{5}})$. I'll let you compare $2^{\varphi^n/\sqrt{5}}$ and $2^{\varphi^n}$ yourself.