Es posible que haya alguna recurrencia que se pueda probar por inducción, pero por el momento no veo ninguna. Sin embargo, es posible obtener una fórmula exacta fea sin usar la inducción.
De la fórmula de Binet no es difícil deducir que
$$F_n= \left\lfloor\frac { \varphi ^n}{ \sqrt5 }+ \frac12\right\rfloor $$
para $n \ge 0$ . Así, $F_n \le m$ si y sólo si
$$ \left\lfloor\frac { \varphi ^n}{ \sqrt5 }+ \frac12\right\rfloor\le m\;,$$
o, de forma equivalente,
$$ \frac { \varphi ^n}{ \sqrt5 }+ \frac12 <m+1\;.$$
Esto a su vez equivale a
$$ \varphi ^n< \sqrt5\left (m+ \frac12\right )$$
y por lo tanto a
$$n< \log_\varphi\sqrt5 + \log_\varphi\left (m+ \frac12\right )\;. \tag {1}$$
Finalmente, ya que $n$ debe ser un número entero, $(1)$ se mantiene si y sólo si
$$n< \left\lceil\log_\varphi\sqrt5 + \log_\varphi\left (m+ \frac12\right ) \right\rceil\ ;, \tag {2}$$
y hay
$$ \left\lceil\log_\varphi\sqrt5 + \log_\varphi\left (m+ \frac12\right ) \right\rceil $$
números enteros no negativos $n$ satisfactoria $(2)$ . Así, el número de números de Fibonacci $F_k$ satisfactoria $2^n<F_k \le 2^{n+1}$ es
$$ \left\lceil\log_\varphi\sqrt5 + \log_\varphi\left (2^{n+1}+ \frac12\right ) \right\rceil - \left\lceil\log_\varphi\sqrt5 + \log_\varphi\left (2^n+ \frac12\right ) \right\rceil\ ;. \tag {3}$$
Tenga en cuenta que para las grandes $n$ tenemos
$$ \sqrt5\left (2^{n+1}+ \frac12\right ) \approx2\cdot\sqrt5\left (2^n+ \frac12\right )\;,$$
así que sin la función de techo la diferencia en $(3)$ sería sobre $ \log_\varphi2\approx 1.44$ y puedes esperar que el valor real sea $1$ o $2$ dependiendo de $n$ .
